Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm

ABSTRACT

The method of stable random projections is a useful tool for efficiently computing the lα (0 < α ≤ 2) norms and distances in massive data in one pass. Consider a data matrix A ∈R^nxD. If we multiply A with a projection matrix R ΕR ^Dxk (k« D),whose entries are i.i.d. samples of an α-stable distribution,then the projected matrix B = Ax R Ε R ^nxkx containsenough information to approximately recover the l α properties in A.

We propose very sparse stable random projections, by replacing the α stable distribution with a (much simpler) mixture of a symmetric α Pareto distribution (with probability Β, 0 β Β 1) and a point mass at the origin(with probability 1-Β). This leads to a significant 1 over Β fold speedup for small Β when computing B = AxR and a 1 over Β-fold cost reduction in storing R}. By analyzing the convergence, we show that in"reasonable" datasets Β often can be very small (e.g.,D^1/2 without hurting the estimation accuracy. Some numerical evaluations are conducted, on synthetic data, Web crawldata, and gene expression microarray data.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 2: 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]
• 3: D. Achlioptas, F. McSherry, and B. Schölkopf. Sampling techniques for kernel methods. In NIPS, 335--342, 2001.
• 4: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: 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]
• 6: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 7: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 8: 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]
• 9: 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]
• 10: M. Balcan, A. Blum, and S. Vempala. On kernels, margins, and low-dimensional mappings. In ALT, 194--205, 2004.
• 11: A. Bhattacharjee, W. G. Richards, J. Staunton, C. Li, S. Monti, P. Vasa, C. Ladd, J. Beheshti, R. Bueno, M. Gillette, M. Loda, G. Weber, E. J. Mark, E. S. Lander, W. Wong, B. E. Johnson, T. R. Golub, D. J. Sugarbaker, and M. Meyerson. Classification of human lung carcinomas by mRNA expression profiling reveals distinct adenocarcinoma subclasses. PNAS, 98(24):13790--13795, 2001.
• 12: Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502546]
• 13: 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
• 14: 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]
• 15: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 16: J. Buhler and M. Tompa. Finding motifs using random projections. Journal of Computational Biology, 9(2):225--242, 2002.
• 17: O. Chapelle, P. Haffner, and V. N. Vapnik. Support vector machines for histogram-based image classification. IEEE Trans. Neural Networks, 10(5):1055--1064, 1999.
• 18: 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]
• 19: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), Proceedings of the 28th international conference on Very Large Data Bases, p.335-345, August 20-23, 2002, Hong Kong, China
• 20: 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]
• 21: G. Cormode and S. Muthukrishnan. Estimating dominance norms of multiple data streams. In ESA, 148--160, 2003.
• 22: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 23: 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]
• 24: D. L. Donoho. Unconditional bases are optimal bases for data compression and for statistical estimation. Applied and Computational Harmonic Analysis, 1(1):100--115, 1993.
• 25: D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289--1306, 2006.
• 26: S. T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23(2):229--236, 1991.
• 27: R. Durrett. Probability: Theory and Examples. Duxbury Press, second edition, 1995.
• 28: B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. The Annals of Statistics, 32(2):407--499, 2004.
• 29: M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. In SIGMOD, 251--262, 1999.
• 30: E. F. Fama and R. Roll. Some properties of symmetric stable distributions. Journal of the American Statistical Association, 63(323):817--836, 1968.
• 31: E. F. Fama and R. Roll. Parameter estimates for symmetric stable distributions. Journal of the American Statistical Association, 66(334):331--338, 1971.
• 32: 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
• 33: Marin Ferecatu , Michel Crucianu , Nozha Boujemaa, Retrieval of difficult image classes using svd-based relevance feedback, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026716]
• 34: X. Z. Fern and C. E. Brodley. Random projection for high dimensional data clustering: A cluster ensemble approach. In ICML, 186--193, 2003.
• 35: J. H. Fong and M. Strauss. An approximate l_p difference algorithm for massive data streams. Discrete Mathematics & Theoretical Computer Science, 4(2):301--322, 2001.
• 36: Dmitriy Fradkin , David Madigan, Experiments with random projections for machine learning, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956812]
• 37: 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
• 38: B. V. Gnedenko and A. N. Kolmogorov. Limit Distributions for Sum of Independent Random Variables. Addison Wesley, 1954.
• 39: N. Goel, G. Bebis, and A. Nefian. Face recognition experiments with random projection. In SPIE, 42---437, 2005.
• 40: I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Products. Academic Press, fifth edition, 1994.
• 41: Warren R. Greiff, A theory of term weighting based on exploratory data analysis, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.11-19, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290948]
• 42: M. R. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. American Mathematical Society, 1999.
• 43: 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
• 44: 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
• 45: 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]
• 46: 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]
• 47: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 48: W. B. Johnson and G. Schechtman. Embedding l_p into l1. Acta. Math., 149:71--85, 1982.
• 49: R. Kuske and J. B. Keller. Rate of convergence to a stable law. SIAM Journal of Applied Mathematics, 61(4):1308--1323, 2000.
• 50: Man Lan , Chew-Lim Tan , Hwee-Boon Low , Sam-Yuan Sung, A comprehensive comparative study on term weighting schemes for text categorization with support vector machines, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062854]
• 51: J. R. Lee and A. Naor. Embedding the diamond graph in l_p and dimension reduction in l₁. Geometric And Functional Analysis, 14(4):745--747, 2004.
• 52: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 53: Edda Leopold , Jörg Kindermann, Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?, Machine Learning, v.46 n.1-3, p.423-444, 2002 [doi>10.1023/A:1012491419635]
• 54: H. C. M. Leung, F. Y. L. Chin, S. M. Yiu, R. Rosenfeld, and W. W. Tsang. Finding motifs with insufficient number of strong binding sites. Journal of Computational Biology, 12(6):686--701, 2005.
• 55: P. Li. Very sparse stable random projections, estimators and tail bounds for stable random projections. http://arxiv.org/PS_cache/cs/pdf/0611/0611114v2.pdf, 2006.
• 56: P. Li. Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections. Technical report, Department of Statistics, Stanford University, http://www.stanford.edu/~pingli98/publications/stable.pdf, 2007.
• 57: 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]
• 58: 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]
• 59: P. Li, K. W. Church, and T.J. Hastie. Conditional random sampling: A sketch-based sampling technique for sparse data. In NIPS, 2007.
• 60: P. Li, T. J. Hastie, and K. W. Church. Improving random projections using marginal information. In COLT, 635--649, 2006.
• 61: Ping Li , Trevor J. Hastie , Kenneth W. Church, Very sparse random projections, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150436]
• 62: P. Li, T. J. Hastie, and K. W. Church. Nonlinear estimators and tail bounds for dimensional reduction in l₁ using Cauchy random projections. In COLT, 2007.
• 63: 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
• 64: J. Lin and D. Gunopulos. Dimensionality reduction by random projection and latent semantic indexing. In SDM, 2003.
• 65: Bing Liu , Yiming Ma , Philip S. Yu, Discovering unexpected information from your competitors' web sites, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.144-153, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502534]
• 66: Kun Liu , Hillol Kargupta , Jessica Ryan, Random Projection-Based Multiplicative Data Perturbation for Privacy Preserving Distributed Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.92-106, January 2006 [doi>10.1109/TKDE.2006.14]
• 67: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 68: J. Huston McCulloch. Simple consistent estimators of stable distribution parameters. Communications on Statistics-Simulation, 15(4):1109--1136, 1986.
• 69: M. E. J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 46(5):232--351, 2005.
• 70: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 71: Deepak Ravichandran , Patrick Pantel , Eduard Hovy, Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.622-629, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219917]
• 72: J. D. Rennie, L. Shih, J. Teevan, and D. R. Karger. Tackling the poor assumptions of naive Bayes text classifiers. In ICML, 616--623, 2003.
• 73: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 74: G. Samorodnitsky and M. S. Taqqu. Stable Non-Gaussian Random Processes. Chapman & Hall, 1994.
• 75: R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of Royal Statistical Society B, 58(1):267--288, 1996.
• 76: Santosh Vempala, Random Projection: A New Approach to VLSI Layout, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.389, November 08-11, 1998
• 77: S. Vempala. The Random Projection Method. American Mathematical Society, 2004.
• 78: C. T. Yu , K. Lam , G. Salton, Term Weighting in Information Retrieval Using the Term Precision Model, Journal of the ACM (JACM), v.29 n.1, p.152-170, Jan. 1982 [doi>10.1145/322290.322300]
• 79: J. Zhu, S. Rosset, T. J. Hastie, and R, Tibshirani. 1-norm support vector machines. In NIPS, 2003.
• 80: V. M. Zolotarev. One-dimensional Stable Distributions. American Mathematical Society, 1986.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Performance, Theory

Keywords:
asymptotic analysis, convergence, dimension reductions, random projections, sparse projections, stable Ddistributions