mlsanityData to 7 Oct 2026

Optimality of the Johnson-Lindenstrauss Lemma

arXiv 1609.02094 ↗First posted 7 Sep 2016cs.IT cs.CG cs.DScited by 41

Not on the map. Why?

Abstract (arXiv)

For any integers d, n ≥ 2 and 1/(minn,d)0.4999 < varepsilon<1, we show the existence of a set of n vectors Xsubset ℝd such that any embedding f:Xrightarrow ℝm satisfying forall x,y∈ X, (1-varepsilon)|x-y|22≤ |f(x)-f(y)|22 ≤ (1+varepsilon)|x-y|22 must have m = Omega(varepsilon-2 lg n). This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of varepsilon of interest, since there is always an isometric embedding into dimension mind, n (either the identity map, or projection onto mathopspan(X)). Previously such a lower bound was only known to hold against linear maps f, and not for such a wide range of parameters varepsilon, n, d [LN16]. The best previously known lower bound for general f was m = Omega(varepsilon-2lg n/lg(1/varepsilon)) [Wel74, Lev83, Alo03], which is suboptimal for any varepsilon = o(1).

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Sep 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 10; 2023: 12; 2024: 4; 2025: 5; 2026: 5.

41 papers.

Sort:

By area:

  1. 2023Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddingscited by 24
  2. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  3. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  4. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  5. 2023TopP&R: Robust Support Estimation Approach for Evaluating Fidelity and Diversity in Generative Modelscited by 13
  6. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  7. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 10
  8. 2026Cross-Modal Redundancy and the Geometry of Vision-Language Embeddingscited by 9
  9. 2021Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Surveycited by 8
  10. 2022Differentially Private Learning with Margin Guaranteescited by 7
  11. 2022The Fast Johnson-Lindenstrauss Transform is Even Fastercited by 5
  12. 2023Nonlinear SVD with Asymmetric Kernels: feature learning and asymmetric Nystr"om methodcited by 5
29 more
  1. 2022Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernelcited by 3
  2. 2023Data Encoding For Healthcare Data Democratisation and Information Leakage Preventioncited by 3
  3. 2024Lambda: Learning Matchable Prior For Entity Alignment with Unlabeled Dangling Casescited by 3
  4. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  5. 2023Dimensionality Reduction for General KDE Mode Findingcited by 2
  6. 2023Understanding and Leveraging the Learning Phases of Neural Networkscited by 2
  7. 2024Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nystr"om methodcited by 2
  8. 2021Statistical optimality conditions for compressive ensemblescited by 1
  9. 2022On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝNcited by 1
  10. 2023Sparse Dimensionality Reduction Revisitedcited by 1
  11. 2023Sparse Models for Machine Learningcited by 1
  12. 2024Intermediate Outputs Are More Sensitive Than You Thinkcited by 1
  13. 2024Optimization Can Learn Johnson Lindenstrauss Embeddingscited by 1
  14. 2026Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatchcited by 1
  15. 2026A Unifying Framework for Concept-Based Representational Similaritycited by 1
  16. 2021Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measurescited by 0
  17. 2022The learning phases in NN: From Fitting the Majority to Fitting a Fewcited by 0
  18. 2022Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noisecited by 0
  19. 2022Efficient NTK using Dimensionality Reductioncited by 0
  20. 2023Random Separating Hyperplane Theorem and Learning Polytopescited by 0
  21. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  22. 2023Mental Health Diagnosis in the Digital Age: Harnessing Sentiment Analysis on Social Media Platforms upon Ultra-Sparse Feature Contentcited by 0
  23. 2025Beyond Worst-Case Dimensionality Reduction for Sparse Vectorscited by 0
  24. 2025Almost Right: Making First-Layer Kernels Nearly Orthogonal Improves Model Generalizationcited by 0
  25. 2025Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learningcited by 0
  26. 2025Balancing Utility and Privacy: Dynamically Private SGD with Random Projectioncited by 0
  27. 2025Linear Causal Representation Learning by Topological Ordering, Pruning, and Disentanglementcited by 0
  28. 2026Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guaranteecited by 0
  29. 2026Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Modelscited by 0