Document Open Access Logo

ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

Author Alexandros Eskenazis

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2022.40.pdf
  • Filesize: 0.79 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Random projections and metric embeddings
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Approximation
Keywords
  • Dimension reduction
  • ε-isometric embedding
  • Maurey’s empirical method
  • change of measure

Metrics

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

Abstract

Fix p ∈ [1,∞), K ∈ (0,∞) and a probability measure μ. We prove that for every n ∈ ℕ, ε ∈ (0,1) and x₁,…,x_n ∈ L_p(μ) with ‖max_{i ∈ {1,…,n}}|x_i|‖_{L_p(μ)} ≤ K, there exists d ≤ (32e² (2K)^{2p}log n)/ε² and vectors y₁,…, y_n ∈ 𝓁_p^d such that 
∀i,j∈{1,…,n}, ‖x_i-x_j‖^p_{L_p(μ)}-ε ≤ ‖y_i-y_j‖_{𝓁_p^d}^p ≤ ‖x_i-x_j‖^p_{L_p(μ)}+ε. 
Moreover, the argument implies the existence of a greedy algorithm which outputs {y_i}_{i = 1}ⁿ after receiving {x_i}_{i = 1}ⁿ as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of ε-isometric dimension reduction of the unit ball B_E of a normed space (E,‖⋅‖_E) and we prove that B_{𝓁_p} does not admit ε-isometric dimension reduction by linear operators for any value of p≠2.

Cite As Get BibTex

Alexandros Eskenazis. ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.40

Author Details

Alexandros Eskenazis
  • Trinity College and Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK

Funding

The author was supported by a Junior Research Fellowship from Trinity College, Cambridge.

Acknowledgements

I am grateful to Keith Ball, Assaf Naor and Pierre Youssef for insightful discussions and useful feedback. I also wish to thank the anonymous referees for their constructive comments.

References

  1. D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System Sci., 66(4):671-687, 2003. Special issue on PODS 2001 (Santa Barbara, CA). URL: https://doi.org/10.1016/S0022-0000(03)00025-4.
  2. N. Ailon and B. Chazelle. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput., 39(1):302-322, 2009. URL: https://doi.org/10.1137/060673096.
  3. N. Ailon and E. Liberty. An almost optimal unrestricted fast Johnson-Lindenstrauss transform. ACM Trans. Algorithms, 9(3):Art. 21, 12, 2013. URL: https://doi.org/10.1145/2483699.2483701.
  4. J. Arias-de Reyna, K. Ball, and R. Villa. Concentration of the distance in finite-dimensional normed spaces. Mathematika, 45(2):245-252, 1998. URL: https://doi.org/10.1112/S0025579300014182.
  5. R. I. Arriaga and S. Vempala. An algorithmic theory of learning: robust concepts and random projection. In 40th Annual Symposium on Foundations of Computer Science (New York, 1999), pages 616-623. IEEE Computer Soc., Los Alamitos, CA, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814637.
  6. K. Ball. Isometric embedding in l_p-spaces. European J. Combin., 11(4):305-311, 1990. URL: https://doi.org/10.1016/S0195-6698(13)80131-X.
  7. S. Barman. Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem. SIAM J. Comput., 47(3):960-981, 2018. URL: https://doi.org/10.1137/15M1050574.
  8. Y. Bartal and L.-A. Gottlieb. Approximate nearest neighbor search for 𝓁_p-spaces (2 < p < ∞) via embeddings. In LATIN 2018: Theoretical informatics, volume 10807 of Lecture Notes in Comput. Sci., pages 120-133. Springer, Cham, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_1.
  9. J. Bourgain, S. Dirksen, and J. Nelson. Toward a unified theory of sparse dimensionality reduction in Euclidean space. Geom. Funct. Anal., 25(4):1009-1088, 2015. URL: https://doi.org/10.1007/s00039-015-0332-9.
  10. B. Brinkman and M. Charikar. On the impossibility of dimension reduction in l₁. J. ACM, 52(5):766-788, 2005. URL: https://doi.org/10.1145/1089023.1089026.
  11. S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures Algorithms, 22(1):60-65, 2003. URL: https://doi.org/10.1002/rsa.10073.
  12. S. Dirksen. Dimensionality reduction with subgaussian matrices: a unified theory. Found. Comput. Math., 16(5):1367-1396, 2016. URL: https://doi.org/10.1007/s10208-015-9280-x.
  13. P. Frankl and H. Maehara. The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B, 44(3):355-362, 1988. URL: https://doi.org/10.1016/0095-8956(88)90043-3.
  14. Y. Gordon. On Milman’s inequality and random subspaces which escape through a mesh in Rⁿ. In Geometric aspects of functional analysis (1986/87), volume 1317 of Lecture Notes in Math., pages 84-106. Springer, Berlin, 1988. URL: https://doi.org/10.1007/BFb0081737.
  15. P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC '98 (Dallas, TX), pages 604-613. ACM, New York, 1999. Google Scholar
  16. P. Indyk and A. Naor. Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms, 3(3):Art. 31, 12, 2007. URL: https://doi.org/10.1145/1273340.1273347.
  17. G. Ivanov. Approximate Carathéodory’s Theorem in Uniformly Smooth Banach Spaces. Discrete Comput. Geom., 66(1):273-280, 2021. URL: https://doi.org/10.1007/s00454-019-00130-w.
  18. L. Jacques. A quantized Johnson-Lindenstrauss lemma: the finding of Buffon’s needle. IEEE Trans. Inform. Theory, 61(9):5012-5027, 2015. URL: https://doi.org/10.1109/TIT.2015.2453355.
  19. L. Jacques. Small width, low distortions: quantized random embeddings of low-complexity sets. IEEE Trans. Inform. Theory, 63(9):5477-5495, 2017. Google Scholar
  20. W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189-206. Amer. Math. Soc., Providence, RI, 1984. URL: https://doi.org/10.1090/conm/026/737400.
  21. W. B. Johnson and A. Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. Discrete Comput. Geom., 43(3):542-553, 2010. URL: https://doi.org/10.1007/s00454-009-9193-z.
  22. W. B. Johnson and G. Schechtman. Finite dimensional subspaces of L_p. In Handbook of the geometry of Banach spaces, Vol. I, pages 837-870. North-Holland, Amsterdam, 2001. URL: https://doi.org/10.1016/S1874-5849(01)80021-8.
  23. D. M. Kane and J. Nelson. Sparser Johnson-Lindenstrauss transforms. J. ACM, 61(1):Art. 4, 23, 2014. URL: https://doi.org/10.1145/2559902.
  24. B. Klartag and S. Mendelson. Empirical processes and random projections. J. Funct. Anal., 225(1):229-245, 2005. URL: https://doi.org/10.1016/j.jfa.2004.10.009.
  25. F. Krahmer and R. Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal., 43(3):1269-1281, 2011. URL: https://doi.org/10.1137/100810447.
  26. M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes. URL: https://doi.org/10.1007/978-3-642-20212-4.
  27. J. R. Lee, M. Mendel, and A. Naor. Metric structures in L₁: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180-1190, 2005. URL: https://doi.org/10.1016/j.ejc.2004.07.002.
  28. J. R. Lee and A. Naor. Embedding the diamond graph in L_p and dimension reduction in L₁. Geom. Funct. Anal., 14(4):745-747, 2004. URL: https://doi.org/10.1007/s00039-004-0473-8.
  29. C. Liaw, A. Mehrabian, Y. Plan, and R. Vershynin. A simple tool for bounding the deviation of random matrices on geometric sets. In Geometric aspects of functional analysis, volume 2169 of Lecture Notes in Math., pages 277-299. Springer, Cham, 2017. Google Scholar
  30. J. Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math., 93:333-344, 1996. URL: https://doi.org/10.1007/BF02761110.
  31. J. Matoušek. On variants of the Johnson-Lindenstrauss lemma. Random Structures Algorithms, 33(2):142-156, 2008. URL: https://doi.org/10.1002/rsa.20218.
  32. B. Maurey. Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L^p. Astérisque, No. 11. Société Mathématique de France, Paris, 1974. With an English summary. Google Scholar
  33. A. Naor. Metric dimension reduction: a snapshot of the Ribe program. In Proceedings of the International Congress of Mathematicians - Rio de Janeiro 2018. Vol. I. Plenary lectures, pages 759-837. World Sci. Publ., Hackensack, NJ, 2018. Google Scholar
  34. A. Naor, G. Pisier, and G. Schechtman. Impossibility of dimension reduction in the nuclear norm. Discrete Comput. Geom., 63(2):319-345, 2020. URL: https://doi.org/10.1007/s00454-019-00162-2.
  35. M. I. Ostrovskii. Metric embeddings, volume 49 of De Gruyter Studies in Mathematics. De Gruyter, Berlin, 2013. Bilipschitz and coarse embeddings into Banach spaces. URL: https://doi.org/10.1515/9783110264012.
  36. G. Pisier. Remarques sur un résultat non publié de B. Maurey. In Seminar on Functional Analysis, 1980-1981, pages Exp. No. V, 13. École Polytech., Palaiseau, 1981. Google Scholar
  37. Y. Plan and R. Vershynin. Dimension reduction by random hyperplane tessellations. Discrete Comput. Geom., 51(2):438-461, 2014. URL: https://doi.org/10.1007/s00454-013-9561-6.
  38. O. Regev and T. Vidick. Bounds on dimension reduction in the nuclear norm. In Geometric aspects of functional analysis. Vol. II, volume 2266 of Lecture Notes in Math., pages 279-299. Springer, Cham, [2020] (c)2020. URL: https://doi.org/10.1007/978-3-030-46762-3_13.
  39. G. Schechtman. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math., 200(1):125-135, 2006. URL: https://doi.org/10.1016/j.aim.2004.11.003.
  40. G. Schechtman and J. Zinn. On the volume of the intersection of two Lⁿ_p balls. Proc. Amer. Math. Soc., 110(1):217-224, 1990. URL: https://doi.org/10.2307/2048262.
  41. J. Spencer. Ten lectures on the probabilistic method, volume 64 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 1994. URL: https://doi.org/10.1137/1.9781611970074.
  42. R. Vershynin. High-dimensional probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. An introduction with applications in data science, With a foreword by Sara van de Geer. URL: https://doi.org/10.1017/9781108231596.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact