# The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2014.

## Built on by (most cited first, 12 of 12)

- [From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit](https://mlsanity.com/paper/2506.03093/) (2025)
- [LLM DNA: Tracing Model Evolution via Functional Representations](https://mlsanity.com/paper/2509.24496/) (2025)
- [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)
- [Why 1 + 1 < 1 in Visual Token Pruning: Beyond Naive Integration via Multi-Objective Balanced Covering](https://mlsanity.com/paper/2505.10118/) (2025)
- [Mysteries of the Deep: Role of Intermediate Representations in Out of Distribution Detection](https://mlsanity.com/paper/2510.05782/) (2025)
- [AFBS:Buffer Gradient Selection in Semi-asynchronous Federated Learning](https://mlsanity.com/paper/2506.12754/) (2025)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [Optimization Can Learn Johnson Lindenstrauss Embeddings](https://mlsanity.com/paper/2412.07242/) (2024)
- [Confidence-Optimal Random Embeddings](https://mlsanity.com/paper/2104.05628/) (2021)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)

## Abstract (arXiv)

For any n>1 and 0<varepsilon<1/2, we show the existence of an nO(1)-point subset X of ℝn such that any linear map from (X,ℓ2) to ℓ2m with distortion at most 1+varepsilon must have m = Omega(minn, varepsilon-2log n). Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma, improving the previous lower bound of Alon by a log(1/varepsilon) factor.