mlsanityData to 7 Oct 2026

An Introduction to Johnson-Lindenstrauss Transforms

arXiv 2103.00564 ↗First posted 28 Feb 2021cs.DS cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Johnson--Lindenstrauss Transforms are powerful tools for reducing the dimensionality of data while preserving key characteristics of that data, and they have found use in many fields from machine learning to differential privacy and more. This note explains what they are; it gives an overview of their use and their development since they were introduced in the 1980s; and it provides many references should the reader wish to explore these topics more deeply.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 39 of its 197 references that are in the map. First posted on arXiv 28 Feb 2021.

Builds on

39 of 197 references.

References · 39

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  2. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  3. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  4. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  5. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  6. 2015Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Samplingcited by 46
  7. 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 41
  8. 2015Differentially Private Ordinary Least Squarescited by 36
  9. 2015Random-projection ensemble classificationcited by 29
  10. 2013Experiments with Random Projectioncited by 27
  11. 2014Randomized Sketches of Convex Programs with Sharp Guaranteescited by 25
  12. 2020Projection & Probability-Driven Black-Box Attackcited by 19
27 more
  1. 2013Statistical mechanics of complex neural systems and high dimensional datacited by 15
  2. 2013Toward a unified theory of sparse dimensionality reduction in Euclidean spacecited by 15
  3. 2019Defending against adversarial attacks by randomized diversificationcited by 14
  4. 2019Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noisecited by 13
  5. 2018Fully Understanding the Hashing Trickcited by 11
  6. 2019Understanding Sparse JL for Feature Hashingcited by 9
  7. 2015DUAL-LOCO: Distributing Statistical Estimation Using Random Projectionscited by 7
  8. 2017Practical Hash Functions for Similarity Estimation and Dimensionality Reductioncited by 7
  9. 2019Random projections: data perturbation for classification problemscited by 7
  10. 2020Randomized spectral co-clustering for large-scale directed networkscited by 7
  11. 2014Dimensionality reduction with subgaussian matrices: a unified theorycited by 6
  12. 2017On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transformscited by 6
  13. 2020Projection-Cost-Preserving Sketches: Proof Strategies and Constructionscited by 6
  14. 2014Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensingcited by 4
  15. 2014Johnson-Lindenstrauss Compression with Neuroscience-Based Constraintscited by 4
  16. 2020Improved Subsampled Randomized Hadamard Transform for Linear SVMcited by 4
  17. 2020SUOD: Toward Scalable Unsupervised Outlier Detectioncited by 4
  18. 2017Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Setscited by 3
  19. 2019On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problemscited by 3
  20. 2020Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminantscited by 3
  21. 2020High-dimensional outlier detection using random projectionscited by 3
  22. 2014An Analysis of Random Projections in Cancelable Biometricscited by 2
  23. 2014Subspace clustering of dimensionality-reduced datacited by 2
  24. 2016Comparison among dimensionality reduction techniques based on Random Projection for cancer classificationcited by 2
  25. 2019Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projectionscited by 2
  26. 2019On the reconstruction accuracy of multi-coil MRI with orthogonal projectionscited by 2
  27. 2015Using the Johnson-Lindenstrauss lemma in linear and integer programmingcited by 1

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 3; 2025: 4.

10 papers.

  1. 2024APOLLO: SGD-like Memory, AdamW-level Performancecited by 50
  2. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  3. 2025The Blessing and Curse of Dimensionality in Safety Alignmentcited by 9
  4. 2022FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Searchcited by 4
  5. 2025Graph Random Features for Scalable Gaussian Processescited by 4
  6. 2025Computationally-efficient Graph Modeling with Refined Graph Random Featurescited by 2
  7. 2022Parametrized Power-Iteration Clustering for Directed Graphscited by 1
  8. 2023Exact Non-Oblivious Performance of Rademacher Random Embeddingscited by 0
  9. 2024Preserving Angles Improves Feature Distillationcited by 0
  10. 2025FedRP: A Communication-Efficient Approach for Differentially Private Federated Learning Using Random Projectioncited by 0