Document Open Access Logo

Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures

Authors Yair Bartal, Ora Nova Fandina, Kasper Green Larsen

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.13.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Author Details

Yair Bartal
  • Hebrew University, Jerusalem, Israel
Ora Nova Fandina
  • Aarhus University, Denmark
Kasper Green Larsen
  • Aarhus University, Denmark

Funding

  • Bartal, Yair: Supported in part by a grant from the Israeli Science Foundation (1817/17).
  • Larsen, Kasper Green: Supported by Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B.

Cite AsGet BibTex

Yair Bartal, Ora Nova Fandina, and Kasper Green Larsen. Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.13

Abstract

It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on their performance. The question of whether the JL method is optimal for practical measures of distortion was recently raised in [Yair Bartal et al., 2019] (NeurIPS'19). They provided upper bounds on its quality for a wide range of practical measures and showed that indeed these are best possible in many cases. Yet, some of the most important cases, including the fundamental case of average distortion were left open. In particular, they show that the JL transform has 1+ε average distortion for embedding into k-dimensional Euclidean space, where k = O(1/ε²), and for more general q-norms of distortion, k = O(max{1/ε²,q/ε}), whereas tight lower bounds were established only for large values of q via reduction to the worst case. In this paper we prove that these bounds are best possible for any dimensionality reduction method, for any 1 ≤ q ≤ O((log (2ε² n))/ε) and ε ≥ 1/(√n), where n is the size of the subset of Euclidean space. Our results also imply that the JL method is optimal for various distortion measures commonly used in practice, such as stress, energy and relative error. We prove that if any of these measures is bounded by ε then k = Ω(1/ε²), for any ε ≥ 1/(√n), matching the upper bounds of [Yair Bartal et al., 2019] and extending their tightness results for the full range moment analysis. Our results may indicate that the JL dimensionality reduction method should be considered more often in practical applications, and the bounds we provide for its quality should be served as a measure for comparison when evaluating the performance of other methods and heuristics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random projections and metric embeddings
  • Theory of computation → Computational geometry
  • Theory of computation → Unsupervised learning and clustering
Keywords
  • average distortion
  • practical dimensionality reduction
  • JL transform

Metrics

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

Related Versions

References

  1. Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins. Metric embeddings with relaxed guarantees. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 83-100, USA, 2005. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.2005.51.
  2. Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 502-511, USA, 2007. Society for Industrial and Applied Mathematics. Google Scholar
  3. Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms, SODA '07, pages 502-511, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://portal.acm.org/citation.cfm?id=1283383.1283437.
  4. Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. URL: https://doi.org/10.1016/j.aim.2011.08.003.
  5. Noga Alon. Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability & Computing, 18(1-2):3-15, 2009. URL: https://doi.org/10.1017/S0963548307008917.
  6. Noga Alon and Bo'az Klartag. Optimal compression of approximate inner products and dimension reduction. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 639-650, 2017. URL: https://doi.org/10.1109/FOCS.2017.65.
  7. Ehsan Amid and Manfred K. Warmuth. Trimap: Large-scale dimensionality reduction using triplets, 2019. URL: http://arxiv.org/abs/1910.00204.
  8. Yair Bartal, Nova Fandina, and Ofer Neiman. Dimensionality reduction: theoretical perspective on practical measures. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10576-10588, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/94f4ede62112b790c91d5e64fdb09cb8-Abstract.html.
  9. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. Annals of Mathematics, 162(2):643-709, 2005. URL: http://www.jstor.org/stable/20159927.
  10. A. Censi and D. Scaramuzza. Calibration by correlation using metric embedding from nonmetric similarities. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(10):2357-2370, October 2013. URL: https://doi.org/10.1109/TPAMI.2013.34.
  11. Leena Chennuru Vankadara and Ulrike von Luxburg. Measures of distortion for machine learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 4891-4900. Curran Associates, Inc., 2018. Google Scholar
  12. Leena Chennuru Vankadara and Ulrike von Luxburg. Measures of distortion for machine learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL: https://proceedings.neurips.cc/paper/2018/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf.
  13. Russ Cox, Frank Dabek, Frans Kaashoek, Jinyang Li, and Robert Morris. Practical, distributed network coordinates. SIGCOMM Comput. Commun. Rev., 34(1):113-118, January 2004. URL: https://doi.org/10.1145/972374.972394.
  14. Michael Elkin, Arnold Filtser, and Ofer Neiman. Prioritized metric structures and embedding. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 489-498, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2746539.2746623.
  15. Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 242-264, 2015. Google Scholar
  16. Patrick J. F. Groenen, Rudolf Mathar, and Willem J. Heiser. The majorization approach to multidimensional scaling for minkowski distances. Journal of Classification, 12(1):3-19, 1995. Google Scholar
  17. W. J Heiser. Multidimensional scaling with least absolute residuals. In In H. H. Bock (Ed.) Classification and related methods, pages 455-462. Amsterdam: NorthHolland, 1988a. Google Scholar
  18. P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS '01, page 10, USA, 2001. IEEE Computer Society. Google Scholar
  19. Piotr Indyk and Jiri Matousek. Low-distortion embeddings of finite metric spaces. In in Handbook of Discrete and Computational Geometry, pages 177-196. CRC Press, 2004. Google Scholar
  20. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, pages 604-613, New York, NY, USA, 1998. ACM. URL: https://doi.org/10.1145/276698.276876.
  21. William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189-206. American Mathematical Society, Providence, RI, 1984. Google Scholar
  22. Jon Kleinberg, Aleksandrs Slivkins, and Tom Wexler. Triangulation and embedding using small sets of beacons. J. ACM, 56(6):32:1-32:37, September 2009. URL: https://doi.org/10.1145/1568318.1568322.
  23. Deepanshu Kush, Aleksandar Nikolov, and Haohua Tang. Near neighbor search via efficient average distortion embeddings. In 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), pages 50:1-50:14, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.50.
  24. Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638, 2017. URL: https://doi.org/10.1109/FOCS.2017.64.
  25. N. Linial. Finite metric spaces- combinatorics, geometry and algorithms. In Proceedings of the ICM, 2002. Google Scholar
  26. Jiří Matoušek. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Commentat. Math. Univ. Carol., 31(3):589-600, 1990. Google Scholar
  27. Jiří Matoušek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. Google Scholar
  28. Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger. Umap: Uniform manifold approximation and projection. Journal of Open Source Software, 3(29):861, 2018. URL: https://doi.org/10.21105/joss.00861.
  29. Assaf Naor. Comparison of metric spectral gaps. Analysis and Geometry in Metric Spaces, 2:2:1-52, 2014. Google Scholar
  30. Assaf Naor. An average John theorem. Geometry and Topology, 25(4):1631-1717, 2021. URL: https://doi.org/10.2140/gt.2021.25.1631.
  31. Puneet Sharma, Zhichen Xu, Sujata Banerjee, and Sung-Ju Lee. Estimating network proximity and latency. Computer Communication Review, 36(3):39-50, 2006. URL: https://doi.org/10.1145/1140086.1140092.
  32. Yuval Shavitt and Tomer Tankel. Big-bang simulation for embedding network distances in euclidean space. IEEE/ACM Trans. Netw., 12(6):993-1006, December 2004. URL: https://doi.org/10.1109/TNET.2004.838597.
  33. Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(86):2579-2605, 2008. URL: http://jmlr.org/papers/v9/vandermaaten08a.html.
  34. Santosh Srinivas Vempala. The random projection method, volume 65 of DIMACS series in discrete mathematics and theoretical computer science. Providence, R.I. American Mathematical Society, 2004. URL: http://opac.inria.fr/record=b1101689.
  35. J. Fernando Vera, Willem J. Heiser, and Alex Murillo. Global optimization in any minkowski metric: A permutation-translation simulated annealing algorithm for multidimensional scaling. J. Classif., 24(2):277-301, September 2007. Google Scholar
  36. Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: An empirical approach to deciphering t-sne, umap, trimap, and pacmap for data visualization, 2020. URL: http://arxiv.org/abs/2012.04456.
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