mlsanityData to 14 Oct 2026

The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

arXiv 1411.2404 ↗First posted 10 Nov 2014cs.IT cs.CG cs.DScited by 12

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 0; 2023: 3; 2024: 1; 2025: 6.

12 papers.

  1. 2025From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuitcited by 49
  2. 2025LLM DNA: Tracing Model Evolution via Functional Representationscited by 15
  3. 2023TopP&R: Robust Support Estimation Approach for Evaluating Fidelity and Diversity in Generative Modelscited by 14
  4. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  5. 2025Why 1 + 1 < 1 in Visual Token Pruning: Beyond Naive Integration via Multi-Objective Balanced Coveringcited by 11
  6. 2025Mysteries of the Deep: Role of Intermediate Representations in Out of Distribution Detectioncited by 7
  7. 2025AFBS:Buffer Gradient Selection in Semi-asynchronous Federated Learningcited by 2
  8. 2023Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guaranteescited by 1
  9. 2024Optimization Can Learn Johnson Lindenstrauss Embeddingscited by 1
  10. 2021Confidence-Optimal Random Embeddingscited by 0
  11. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  12. 2025Beyond Worst-Case Dimensionality Reduction for Sparse Vectorscited by 0