Document Open Access Logo

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction

Authors Kasper Green Larsen, Jelani Nelson

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.82.pdf
  • Filesize: 461 kB
  • 11 pages

Document Identifiers

Author Details

Kasper Green Larsen
Jelani Nelson

Cite AsGet BibTex

Kasper Green Larsen and Jelani Nelson. The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 82:1-82:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.82

Abstract

For any n > 1, 0 < epsilon < 1/2, and N > n^C for some constant C > 0, we show the existence of an N-point subset X of l_2^n such that any linear map from X to l_2^m with distortion at most 1 + epsilon must have m = Omega(min{n, epsilon^{-2}*lg(N)). This improves a lower bound of Alon [Alon, Discre. Mathem., 1999], in the linear setting, by a lg(1/epsilon) factor. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, Contem. Mathem., 1984].
Keywords
  • dimensionality reduction
  • lower bounds
  • Johnson-Lindenstrauss

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Radosław Adamczak and Paweł Wolff. Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order. CoRR, abs/1304.1826, 2013. Google Scholar
  2. Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. New characterizations in turnstile streams with applications. In Proceedings of the 31st Annual Conference on Computational Complexity (CCC), 2016. Google Scholar
  3. Noga Alon. Problems and results in extremal combinatorics-I. Discrete Mathematics, 273(1-3):31-53, 2003. Google Scholar
  4. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. Google Scholar
  5. Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, and Chinmay Hegde. Model-based compressive sensing. IEEE Trans. Inf. Theory, 56:1982-2001, 2010. Google Scholar
  6. Emmanuel Candès and Terence Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51(12):4203-4215, 2005. Google Scholar
  7. Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, (STOC), pages 205-214, 2009. Google Scholar
  8. David Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4):1289-1306, 2006. Google Scholar
  9. David L. Donoho and Carrie Grimes. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. PNAS, 100(10):5591-5596, 2003. Google Scholar
  10. Lee-Ad Gottlieb and Robert Krauthgamer. A nonlinear approach to dimension reduction. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 888-899, 2011. Google Scholar
  11. David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist., 42(3):1079-1083, 1971. Google Scholar
  12. Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages 10-33, 2001. Google Scholar
  13. T. S. Jayram and David P. Woodruff. Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. ACM Transactions on Algorithms, 9(3):26, 2013. Google Scholar
  14. Jr. John W. Sammon. A nonlinear mapping for data structure analysis. IEEE Transactions on Computers, 18:401-409, 1969. Google Scholar
  15. William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189-206, 1984. Google Scholar
  16. Daniel M. Kane, Raghu Meka, and Jelani Nelson. Almost optimal explicit Johnson-Lindenstrauss families. In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM), pages 628-639, 2011. Google Scholar
  17. Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1161-1178, 2010. Google Scholar
  18. Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 41-52, 2010. Google Scholar
  19. Rafał Latała. Tail and moment estimates for some types of chaos. Studia Math., 135:39-53, 1999. Google Scholar
  20. Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), pages 174-183, 2014. Google Scholar
  21. Jirí Matousek. On variants of the Johnson-Lindenstrauss lemma. Random Struct. Algorithms, 33(2):142-156, 2008. Google Scholar
  22. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. Google Scholar
  23. Jelani Nelson, Huy L. Nguŷẽn, and David P. Woodruff. On deterministic sketching and streaming for sparse recovery and norm estimation. Linear Algebra and its Applications, Special Issue on Sparse Approximate Solution of Linear Systems, 441:152-167, 2014. Google Scholar
  24. Gilles Pisier. Probabilistic methods in the geometry of Banach spaces. Probability and Analysis, Lecture Notes in Math., 1206:167-241, 1986. Google Scholar
  25. Gilles Pisier. The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics. Cambridge University Press, 1989. Google Scholar
  26. Sam Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323-2326, 2000. Google Scholar
  27. Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319-2323, 2000. Google Scholar
  28. Santosh Vempala. The random projection method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact