# Optimality of the Johnson-Lindenstrauss Lemma

arXiv: https://arxiv.org/abs/1609.02094 · HTML: https://mlsanity.com/paper/1609.02094/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2016.

## Built on by (most cited first, 30 of 42)

- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [TopP&R: Robust Support Estimation Approach for Evaluating Fidelity and Diversity in Generative Models](https://mlsanity.com/paper/2306.08013/) (2023)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Cross-Modal Redundancy and the Geometry of Vision-Language Embeddings](https://mlsanity.com/paper/2602.06218/) (2026)
- [Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey](https://mlsanity.com/paper/2108.04172/) (2021)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Nonlinear SVD with Asymmetric Kernels: feature learning and asymmetric Nystr"om method](https://mlsanity.com/paper/2306.07040/) (2023)
- [Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel](https://mlsanity.com/paper/2202.02031/) (2022)
- [Data Encoding For Healthcare Data Democratisation and Information Leakage Prevention](https://mlsanity.com/paper/2305.03710/) (2023)
- [Lambda: Learning Matchable Prior For Entity Alignment with Unlabeled Dangling Cases](https://mlsanity.com/paper/2403.10978/) (2024)
- [Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nystr"om method](https://mlsanity.com/paper/2406.08748/) (2024)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Dimensionality Reduction for General KDE Mode Finding](https://mlsanity.com/paper/2305.18755/) (2023)
- [Understanding and Leveraging the Learning Phases of Neural Networks](https://mlsanity.com/paper/2312.06887/) (2023)
- [Statistical optimality conditions for compressive ensembles](https://mlsanity.com/paper/2106.01092/) (2021)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)
- [Sparse Models for Machine Learning](https://mlsanity.com/paper/2308.13960/) (2023)
- [Intermediate Outputs Are More Sensitive Than You Think](https://mlsanity.com/paper/2412.00696/) (2024)
- [Optimization Can Learn Johnson Lindenstrauss Embeddings](https://mlsanity.com/paper/2412.07242/) (2024)
- [Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch](https://mlsanity.com/paper/2605.03346/) (2026)
- [A Unifying Framework for Concept-Based Representational Similarity](https://mlsanity.com/paper/2606.09653/) (2026)
- [Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures](https://mlsanity.com/paper/2107.06626/) (2021)
- [The learning phases in NN: From Fitting the Majority to Fitting a Few](https://mlsanity.com/paper/2202.08299/) (2022)
- [Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise](https://mlsanity.com/paper/2209.01006/) (2022)

## 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).