Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections

ABSTRACT

The method of stable random projections is popular in data stream computations, data mining, information retrieval, and machine learning, for efficiently computing the lα (0 < α ≤ 2) distances using a small (memory) space, in one pass of the data.

We propose algorithms based on (1) the geometric mean estimator, for all 0 <α ≤ 2, and (2) the harmonic mean estimator, only for small α (e.g., α < 0.344). Compared with the previous classical work [27], our main contributions include:

• The general sample complexity bound for α ≠ 1,2.

For α = 1, [27] provided a nice argument based on the inverse of Cauchy density about the median, leading to a sample complexity bound, although they did not provide the constants and their proof restricted ε to be "small enough."

For general α ≠ 1, 2, however, the task becomes much more difficult. [27] provided the "conceptual promise" that the sample complexity bound similar to that for α = 1 should exist for general α, if a "non-uniform algorithm based on t-quantile" could be implemented. Such a conceptual algorithm was only for supporting the arguments in [27], not a real implementation. We consider this is one of the main problems left open in [27]. In this study, we propose a practical algorithm based on the geometric mean estimator and derive the sample complexity bound for all 0 < α ≤ 2.

• The practical and optimal algorithm for α = 0+

The l₀ norm is an important case. Stable random projections can provide an approximation to the l₀ norm using α → 0+. We provide an algorithm based on the harmonic mean estimator, which is simple and statistically optimal. Its tail bounds are sharper than the bounds derived based on the geometric mean. We also discover a (possibly surprising) fact: in boolean data, stable random projections using α = 0+ with the harmonic mean estimator will be about twice as accurate as (l₂) normal random projections. Because high-dimensional boolean data are common, we expect this fact will be practically quite useful.

• The precise theoretical analysis and practical implications We provide the precise constants in the tail bounds for both the geometric mean and harmonic mean estimators. We also provide the variances (either exact or asymptotic) for the proposed estimators. These results can assist practitioners to choose sample sizes accurately.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003 [doi>10.1016/S0022-0000(03)00025-4]
• 2: Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132597]
• 3: Rosa I. Arriaga , Santosh Vempala, An algorithmic theory of learning: Robust concepts and random projection, Machine Learning, v.63 n.2, p.161-182, May 2006 [doi>10.1007/s10994-006-6265-7]
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: M. S. Bartlett. Approximate confidence intervals, II. Biometrika, 40(3/4):306--317, 1953.
• 6: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 7: Bo Brinkman , Moses Charikar, On the impossibility of dimension reduction in l₁, Journal of the ACM (JACM), v.52 n.5, p.766-788, September 2005 [doi>10.1145/1089023.1089026]
• 8: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 9: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 10: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 11: Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493--507, 1952.
• 12: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March 2003 [doi>10.1109/TKDE.2003.1198388]
• 13: Graham Cormode and S. Muthukrishnan. Estimating dominance norms of multiple data streams. In ESA, pages 148--160, 2003.
• 14: N. Cressie. A note on the behaviour of the stable distributions for small index. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 31(1):61--64, 1975.
• 15: Sanjoy Dasgupta , Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures & Algorithms, v.22 n.1, p.60-65, January 2003 [doi>10.1002/rsa.10073]
• 16: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 17: David L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289--1306, 2006.
• 18: Eugene F. Fama and Richard Roll. Some properties of symmetric stable distributions. Journal of the American Statistical Association, 63(323):817--836, 1968.
• 19: Eugene F. Fama and Richard Roll. Parameter estimates for symmetric stable distributions. Journal of the American Statistical Association, 66(334):331--338, 1971.
• 20: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 21: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 22: Sumit Ganguly and Graham Cormode. On estimating frequency moments of data streams. In APPROX-RANDOM, pages 479--493, 2007.
• 23: I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Products. Academic Press, sixth edition, 2000.
• 24: Monika R. Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. American Mathematical Society, 1999.
• 25: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 26: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 27: Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006 [doi>10.1145/1147954.1147955]
• 28: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 29: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 30: W. B. Johnson and G. Schechtman. Embedding l_p into l₁. Acta. Math., 149:71--85, 1982.
• 31: James R. Lee and Assaf Naor. Embedding the diamond graph in l_p and dimension reduction in l₁. Geometric And Functional Analysis, 14(4): 745--747, 2004.
• 32: Erich L. Lehmann and George Casella. Theory of Point Estimation. Springer, second edition, 1998.
• 33: Ping Li, Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281241]
• 34: Ping Li , Kenneth W. Church, Using sketches to estimate associations, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.708-715, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220664]
• 35: Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007 [doi>10.1162/coli.2007.33.3.305]
• 36: Ping Li, Kenneth W. Church, and Trevor J. Hastie. Conditional random sampling: A sketch-based sampling technique for sparse data. In NIPS, pages 873--880, 2007.
• 37: Ping Li, Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 20-22, 2008, San Francisco, California
• 38: Ping Li, Trevor J. Hastie, and Kenneth W. Church. Improving random projections using marginal information. In COLT, pages 635--649, 2006.
• 39: Ping Li, Trevor J. Hastie, and Kenneth W. Church. Nonlinear estimators and tail bounds for dimensional reduction in l₁ using Cauchy random projections. In COLT, 2007.
• 40: Ping Li , Trevor J. Hastie , Kenneth W. Church, Nonlinear Estimators and Tail Bounds for Dimension Reduction in l₁ Using Cauchy Random Projections, The Journal of Machine Learning Research, 8, p.2497-2532, 12/1/2007
• 41: J. Huston McCulloch. Simple consistent estimators of stable distribution parameters. Communications on Statistics-Simulation, 15(4): 1109--1136, 1986.
• 42: L. R. Shenton and K. Bowman. Higher moments of a maximum-likelihood estimate. Journal of Royal Statistical Society B, 25(2):305--317, 1963.
• 43: Santosh Vempala. The Random Projection Method. American Mathematical Society, Providence, RI, 2004.
• 44: V. M. Zolotarev. One-dimensional Stable Distributions. American Mathematical Society, Providence, RI, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory