2026-07-26T02:54:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6203 2024-03-06T10:37:48Z ddc:004 open_access

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction Larsen, Kasper Green Nelson, Jelani dimensionality reduction lower bounds Johnson-Lindenstrauss 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kasper Green Larsen and Jelani Nelson 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.82 urn:nbn:de:0030-drops-62032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.82 eng https://creativecommons.org/licenses/by/3.0/legalcode