{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:42Z","timestamp":1740109602075,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T00:00:00Z","timestamp":1697846400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T00:00:00Z","timestamp":1697846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Fix<jats:inline-formula><jats:alternatives><jats:tex-math>$$p\\in [1,\\infty )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>p<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mo>[<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>,<\/mml:mo><mml:mi>\u221e<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>,<jats:inline-formula><jats:alternatives><jats:tex-math>$$K\\in (0,\\infty )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>K<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mo>(<\/mml:mo><mml:mn>0<\/mml:mn><mml:mo>,<\/mml:mo><mml:mi>\u221e<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a probability measure<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03bc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We prove that for every<jats:inline-formula><jats:alternatives><jats:tex-math>$$n\\in \\mathbb {N}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>N<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>,<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon \\in (0,1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03b5<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mo>(<\/mml:mo><mml:mn>0<\/mml:mn><mml:mo>,<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and<jats:inline-formula><jats:alternatives><jats:tex-math>$$x_1,\\ldots ,x_n\\in L_p(\\mu )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>x<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>\u2208<\/mml:mo><mml:msub><mml:mi>L<\/mml:mi><mml:mi>p<\/mml:mi><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>\u03bc<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>with<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\big \\Vert \\max _{i\\in \\{1,\\ldots ,n\\}} |x_i| \\big \\Vert _{L_p(\\mu )} \\le K$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mrow><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:msub><mml:mo>max<\/mml:mo><mml:mrow><mml:mi>i<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mo>{<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>}<\/mml:mo><\/mml:mrow><\/mml:msub><mml:mrow><mml:mo>|<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>|<\/mml:mo><\/mml:mrow><mml:msub><mml:mrow><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:mrow><mml:msub><mml:mi>L<\/mml:mi><mml:mi>p<\/mml:mi><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>\u03bc<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:msub><mml:mo>\u2264<\/mml:mo><mml:mi>K<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, there exist<jats:inline-formula><jats:alternatives><jats:tex-math>$$d\\le \\frac{32e^2 (2K)^{2p}\\log n}{\\varepsilon ^2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>d<\/mml:mi><mml:mo>\u2264<\/mml:mo><mml:mfrac><mml:mrow><mml:mn>32<\/mml:mn><mml:msup><mml:mi>e<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:msup><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>2<\/mml:mn><mml:mi>K<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><mml:mrow><mml:mn>2<\/mml:mn><mml:mi>p<\/mml:mi><\/mml:mrow><\/mml:msup><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mrow><mml:msup><mml:mi>\u03b5<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><\/mml:mfrac><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and vectors<jats:inline-formula><jats:alternatives><jats:tex-math>$$y_1,\\ldots , y_n \\in \\ell _p^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>y<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:msub><mml:mi>y<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>\u2208<\/mml:mo><mml:msubsup><mml:mi>\u2113<\/mml:mi><mml:mi>p<\/mml:mi><mml:mi>d<\/mml:mi><\/mml:msubsup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>such that<jats:disp-formula><jats:alternatives><jats:tex-math>$$\\begin{aligned} {\\forall }\\,\\,i,j\\in \\{1,\\ldots ,n\\}, \\quad \\Vert x_i-x_j\\Vert ^p_{L_p(\\mu )}-\\varepsilon\\le &amp; {} \\Vert y_i-y_j\\Vert _{\\ell _p^d}^p\\le \\Vert x_i-x_j\\Vert ^p_{L_p(\\mu )}+\\varepsilon . \\end{aligned}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mrow><mml:mo>\u2200<\/mml:mo><mml:mspace\/><mml:mspace\/><mml:mi>i<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>j<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mrow><mml:mo>{<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>}<\/mml:mo><\/mml:mrow><mml:mo>,<\/mml:mo><mml:mspace\/><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:msub><mml:mi>x<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>-<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>j<\/mml:mi><\/mml:msub><mml:msubsup><mml:mrow><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:mrow><mml:msub><mml:mi>L<\/mml:mi><mml:mi>p<\/mml:mi><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>\u03bc<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><mml:mi>p<\/mml:mi><\/mml:msubsup><mml:mo>-<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>\u2264<\/mml:mo><\/mml:mrow><\/mml:mtd><mml:mtd><mml:mrow><mml:mrow><mml:mrow\/><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:msub><mml:mi>y<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>-<\/mml:mo><mml:msub><mml:mi>y<\/mml:mi><mml:mi>j<\/mml:mi><\/mml:msub><mml:msubsup><mml:mrow><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:mrow><mml:msubsup><mml:mi>\u2113<\/mml:mi><mml:mi>p<\/mml:mi><mml:mi>d<\/mml:mi><\/mml:msubsup><\/mml:mrow><mml:mi>p<\/mml:mi><\/mml:msubsup><mml:mo>\u2264<\/mml:mo><mml:msubsup><mml:mrow><mml:mo>\u2016<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>-<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>j<\/mml:mi><\/mml:msub><mml:mo>\u2016<\/mml:mo><\/mml:mrow><mml:mrow><mml:msub><mml:mi>L<\/mml:mi><mml:mi>p<\/mml:mi><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>\u03bc<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><mml:mi>p<\/mml:mi><\/mml:msubsup><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>.<\/mml:mo><\/mml:mrow><\/mml:mtd><\/mml:mtr><\/mml:mtable><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:disp-formula>Moreover, the argument implies the existence of a greedy algorithm which outputs<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{y_i\\}_{i=1}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msubsup><mml:mrow><mml:mo>{<\/mml:mo><mml:msub><mml:mi>y<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>}<\/mml:mo><\/mml:mrow><mml:mrow><mml:mi>i<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>after receiving<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{x_i\\}_{i=1}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msubsup><mml:mrow><mml:mo>{<\/mml:mo><mml:msub><mml:mi>x<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:mo>}<\/mml:mo><\/mml:mrow><mml:mrow><mml:mi>i<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>as input. The proof relies on a derandomized version of Maurey\u2019s 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<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b5<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-isometric dimension reduction of the unit ball<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textbf {B}}_E$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>B<\/mml:mi><mml:mi>E<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>of a normed space<jats:inline-formula><jats:alternatives><jats:tex-math>$$(E,\\Vert \\cdot \\Vert _E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>E<\/mml:mi><mml:mo>,<\/mml:mo><mml:mo>\u2016<\/mml:mo><mml:mo>\u00b7<\/mml:mo><mml:msub><mml:mo>\u2016<\/mml:mo><mml:mi>E<\/mml:mi><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and we prove that<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textbf {B}}_{\\ell _p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>B<\/mml:mi><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mi>p<\/mml:mi><\/mml:msub><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>does not admit<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b5<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-isometric dimension reduction by linear operators for any value of<jats:inline-formula><jats:alternatives><jats:tex-math>$$p\\ne 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>p<\/mml:mi><mml:mo>\u2260<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00454-023-00587-w","type":"journal-article","created":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T22:01:44Z","timestamp":1697925704000},"page":"160-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\varepsilon $$-Isometric Dimension Reduction for Incompressible Subsets of $$\\ell _p$$"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1601-8307","authenticated-orcid":false,"given":"Alexandros","family":"Eskenazis","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,21]]},"reference":[{"key":"587_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson\u2013Lindenstrauss with binary coins. J.\u00a0Comput. Syst. Sci. 66, 671\u2013687 (2003)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"587_CR2","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N Ailon","year":"2009","unstructured":"Ailon, N., Chazelle, B.: The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39(1), 302\u2013322 (2009)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Ailon, N., Liberty, E.: An almost optimal unrestricted fast Johnson\u2013Lindenstrauss transform. ACM Trans. Algorithms 9(3), # 21 (2013)","key":"587_CR3","DOI":"10.1145\/2483699.2483701"},{"issue":"2","key":"587_CR4","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1112\/S0025579300014182","volume":"45","author":"J Arias-de Reyna","year":"1998","unstructured":"Arias-de Reyna, J., Ball, K., Villa, R.: Concentration of the distance in finite-dimensional normed spaces. Mathematika 45(2), 245\u2013252 (1998)","journal-title":"Mathematika"},{"doi-asserted-by":"crossref","unstructured":"Arriaga, R.I., Vempala, S.: An algorithmic theory of learning: robust concepts and random projection. In: 40th Annual Symposium on Foundations of Computer Science (New York 1999), pp. 616\u2013623. IEEE Computer Society, Los Alamitos (1999)","key":"587_CR5","DOI":"10.1109\/SFFCS.1999.814637"},{"issue":"4","key":"587_CR6","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","volume":"11","author":"K Ball","year":"1990","unstructured":"Ball, K.: Isometric embedding in $$l_p$$-spaces. Eur. J. Combin. 11(4), 305\u2013311 (1990)","journal-title":"Eur. J. Combin."},{"issue":"3","key":"587_CR7","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1137\/15M1050574","volume":"47","author":"S Barman","year":"2018","unstructured":"Barman, S.: Approximating Nash equilibria and dense subgraphs via an approximate version of Carath\u00e9odory\u2019s theorem. SIAM J. Comput. 47(3), 960\u2013981 (2018)","journal-title":"SIAM J. Comput."},{"key":"587_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2018.07.011","volume":"757","author":"Y Bartal","year":"2019","unstructured":"Bartal, Y., Gottlieb, L.-A.: Approximate nearest neighbor search for $$\\ell _p$$-spaces $$(2<p<\\infty )$$ via embeddings. Theor. Comput. Sci. 757, 27\u201335 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"587_CR9","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1007\/s00039-015-0332-9","volume":"25","author":"J Bourgain","year":"2015","unstructured":"Bourgain, J., Dirksen, S., Nelson, J.: Toward a unified theory of sparse dimensionality reduction in Euclidean space. Geom. Funct. Anal. 25(4), 1009\u20131088 (2015)","journal-title":"Geom. Funct. Anal."},{"issue":"5","key":"587_CR10","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B Brinkman","year":"2005","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in $$l_1$$. J. ACM 52(5), 766\u2013788 (2005)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Combettes, C.W., Pokutta, S.: Revisiting the approximate Carath\u00e9odory problem via the Frank\u2013Wolfe algorithm. Math. Program. 197(1), 191\u2013214 (2023)","key":"587_CR11","DOI":"10.1007\/s10107-021-01735-x"},{"issue":"1","key":"587_CR12","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"587_CR13","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1007\/s10208-015-9280-x","volume":"16","author":"S Dirksen","year":"2016","unstructured":"Dirksen, S.: Dimensionality reduction with subgaussian matrices: a unified theory. Found. Comput. Math. 16(5), 1367\u20131396 (2016)","journal-title":"Found. Comput. Math."},{"issue":"3","key":"587_CR14","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P Frankl","year":"1988","unstructured":"Frankl, P., Maehara, H.: The Johnson\u2013Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B 44(3), 355\u2013362 (1988)","journal-title":"J. Combin. Theory Ser. B"},{"doi-asserted-by":"crossref","unstructured":"Gordon, Y.: On Milman\u2019s inequality and random subspaces which escape through a mesh in $${R}^n$$. In: Geometric Aspects of Functional Analysis (1986\/1987). Lecture Notes in Mathematics, vol. 1317, pp. 84\u2013106. Springer, Berlin (1988)","key":"587_CR15","DOI":"10.1007\/BFb0081737"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: 30th Annual ACM Symposiumon Theory of Computing (Dallas 1998), pp. 604\u2013613. ACM, New York (1999)","key":"587_CR16","DOI":"10.1145\/276698.276876"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), # 31 (2007)","key":"587_CR17","DOI":"10.1145\/1273340.1273347"},{"issue":"1","key":"587_CR18","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s00454-019-00130-w","volume":"66","author":"G Ivanov","year":"2021","unstructured":"Ivanov, G.: Approximate Carath\u00e9odory\u2019s theorem in uniformly smooth Banach spaces. Discrete Comput. Geom. 66(1), 273\u2013280 (2021)","journal-title":"Discrete Comput. Geom."},{"issue":"9","key":"587_CR19","doi-asserted-by":"publisher","first-page":"5012","DOI":"10.1109\/TIT.2015.2453355","volume":"61","author":"L Jacques","year":"2015","unstructured":"Jacques, L.: A quantized Johnson\u2013Lindenstrauss lemma: the finding of Buffon\u2019s needle. IEEE Trans. Inf. Theory 61(9), 5012\u20135027 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"587_CR20","first-page":"5477","volume":"63","author":"L Jacques","year":"2017","unstructured":"Jacques, L.: Small width, low distortions: quantized random embeddings of low-complexity sets. IEEE Trans. Inf. Theory 63(9), 5477\u20135495 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability (New Haven 1982). Contemporary Mathematics, vol. 26, pp. 189\u2013206. American Mathematical Society, Providence (1984)","key":"587_CR21","DOI":"10.1090\/conm\/026\/737400"},{"issue":"3","key":"587_CR22","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/s00454-009-9193-z","volume":"43","author":"WB Johnson","year":"2010","unstructured":"Johnson, W.B., Naor, A.: The Johnson\u2013Lindenstrauss lemma almost characterizes Hilbert space, but not quite. Discrete Comput. Geom. 43(3), 542\u2013553 (2010)","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Schechtman, G.: Finite dimensional subspaces of $$L_p$$. In: Handbook of the Geometry of Banach Spaces, vol. I, pp. 837\u2013870. North-Holland, Amsterdam (2001)","key":"587_CR23","DOI":"10.1016\/S1874-5849(01)80021-8"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J.: Sparser Johnson\u2013Lindenstrauss transforms. J. ACM 61(1), #\u00a04 (2014)","key":"587_CR24","DOI":"10.1145\/2559902"},{"doi-asserted-by":"crossref","unstructured":"Kashin, B., Kosov, E., Limonova, I., Temlyakov, V.: Sampling discretization and related problems. J. Complex. 71, #\u00a0101653 (2022)","key":"587_CR25","DOI":"10.1016\/j.jco.2022.101653"},{"issue":"1","key":"587_CR26","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.jfa.2004.10.009","volume":"225","author":"B Klartag","year":"2005","unstructured":"Klartag, B., Mendelson, S.: Empirical processes and random projections. J. Funct. Anal. 225(1), 229\u2013245 (2005)","journal-title":"J. Funct. Anal."},{"issue":"3","key":"587_CR27","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1137\/100810447","volume":"43","author":"F Krahmer","year":"2011","unstructured":"Krahmer, F., Ward, R.: New and improved Johnson\u2013Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal. 43(3), 1269\u20131281 (2011)","journal-title":"SIAM J. Math. Anal."},{"doi-asserted-by":"crossref","unstructured":"Ledoux, M., Talagrand, M.: Probability in Banach Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol.\u00a023. Springer, Berlin (1991)","key":"587_CR28","DOI":"10.1007\/978-3-642-20212-4"},{"issue":"8","key":"587_CR29","doi-asserted-by":"publisher","first-page":"1180","DOI":"10.1016\/j.ejc.2004.07.002","volume":"26","author":"JR Lee","year":"2005","unstructured":"Lee, J.R., Mendel, M., Naor, A.: Metric structures in $$L_1$$: dimension, snowflakes, and average distortion. Eur. J. Combin. 26(8), 1180\u20131190 (2005)","journal-title":"Eur. J. Combin."},{"issue":"4","key":"587_CR30","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s00039-004-0473-8","volume":"14","author":"JR Lee","year":"2004","unstructured":"Lee, J.R., Naor, A.: Embedding the diamond graph in $$L_p$$ and dimension reduction in $$L_1$$. Geom. Funct. Anal. 14(4), 745\u2013747 (2004)","journal-title":"Geom. Funct. Anal."},{"doi-asserted-by":"crossref","unstructured":"Liaw, C., Mehrabian, A., Plan, Y., Vershynin, R.: A simple tool for bounding the deviation of random matrices on geometric sets. In: Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 2169, pp. 277\u2013299. Springer, Cham (2017)","key":"587_CR31","DOI":"10.1007\/978-3-319-45282-1_18"},{"key":"587_CR32","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333\u2013344 (1996)","journal-title":"Israel J. Math."},{"issue":"2","key":"587_CR33","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1002\/rsa.20218","volume":"33","author":"J Matou\u0161ek","year":"2008","unstructured":"Matou\u0161ek, J.: On variants of the Johnson\u2013Lindenstrauss lemma. Random Struct. Algorithms 33(2), 142\u2013156 (2008)","journal-title":"Random Struct. Algorithms"},{"unstructured":"Maurey, B.: Th\u00e9or\u00e8mes de factorisation pour les op\u00e9rateurs lin\u00e9aires \u00e0 valeurs dans les espaces $$L^{p}$$. Ast\u00e9risque, vol. 11. Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris (1974)","key":"587_CR34"},{"unstructured":"Mirrokni, V., Leme, R.P., Vladu, A., Wong, S.-C.: Tight bounds for approximate Carath\u00e9odory and beyond. In: 34th International Conference on Machine Learning (Sydney 2017). Proceedings of Machine Learning Research, vol. 70, pp. 2440\u20132448 (2017). http:\/\/JMLR.org","key":"587_CR35"},{"doi-asserted-by":"crossref","unstructured":"Naor, A.: Metric dimension reduction: a snapshot of the Ribe program. In: International Congress of Mathematicians (Rio de Janeiro 2018), vol. I. Plenary Lectures, pp. 759\u2013837. World Scientific, Hackensack (2018)","key":"587_CR36","DOI":"10.1142\/9789813272880_0029"},{"issue":"2","key":"587_CR37","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00454-019-00162-2","volume":"63","author":"A Naor","year":"2020","unstructured":"Naor, A., Pisier, G., Schechtman, G.: Impossibility of dimension reduction in the nuclear norm. Discrete Comput. Geom. 63(2), 319\u2013345 (2020)","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Ostrovskii, M.I.: Metric Embeddings: Bilipschitz and Coarse Embeddings into Banach Spaces. De Gruyter Studies in Mathematics, vol. 49. De Gruyter, Berlin (2013)","key":"587_CR38","DOI":"10.1515\/9783110264012"},{"unstructured":"Pisier, G.: Remarques sur un r\u00e9sultat non publi\u00e9 de B. Maurey. In: Seminar on Functional Analysis, 1980\u20131981, #\u00a05. \u00c9cole Polytech., Palaiseau (1981)","key":"587_CR39"},{"issue":"2","key":"587_CR40","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/s00454-013-9561-6","volume":"51","author":"Y Plan","year":"2014","unstructured":"Plan, Y., Vershynin, R.: Dimension reduction by random hyperplane tessellations. Discrete Comput. Geom. 51(2), 438\u2013461 (2014)","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Regev, O., Vidick, T.: Bounds on dimension reduction in the nuclear norm. In: Geometric Aspects of Functional Analysis, vol. II. Lecture Notes in Mathematics, vol. 2266, pp. 279\u2013299. Springer, Cham (2020)","key":"587_CR41","DOI":"10.1007\/978-3-030-46762-3_13"},{"issue":"1","key":"587_CR42","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.aim.2004.11.003","volume":"200","author":"G Schechtman","year":"2006","unstructured":"Schechtman, G.: Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200(1), 125\u2013135 (2006)","journal-title":"Adv. Math."},{"issue":"1","key":"587_CR43","first-page":"217","volume":"110","author":"G Schechtman","year":"1990","unstructured":"Schechtman, G., Zinn, J.: On the volume of the intersection of two $$L^n_p$$ balls. Proc. Am. Math. Soc. 110(1), 217\u2013224 (1990)","journal-title":"Proc. Am. Math. Soc."},{"unstructured":"Vershynin, R.: High-Dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics, vol.\u00a047. Cambridge University Press, Cambridge (2018)","key":"587_CR44"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00587-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00587-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00587-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T16:02:24Z","timestamp":1730390544000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00587-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,21]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["587"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00587-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,10,21]]},"assertion":[{"value":"13 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}