# An Introduction to Johnson-Lindenstrauss Transforms

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

## Key facts

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

## Builds on (most cited first, 30 of 39)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Projection & Probability-Driven Black-Box Attack](https://mlsanity.com/paper/2005.03837/) (2020)
- [Statistical mechanics of complex neural systems and high dimensional data](https://mlsanity.com/paper/1301.7115/) (2013)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Defending against adversarial attacks by randomized diversification](https://mlsanity.com/paper/1904.00689/) (2019)
- [Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise](https://mlsanity.com/paper/1902.04688/) (2019)
- [Fully Understanding the Hashing Trick](https://mlsanity.com/paper/1805.08539/) (2018)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Dimensionality reduction with subgaussian matrices: a unified theory](https://mlsanity.com/paper/1402.3973/) (2014)
- [DUAL-LOCO: Distributing Statistical Estimation Using Random Projections](https://mlsanity.com/paper/1506.02554/) (2015)
- [Practical Hash Functions for Similarity Estimation and Dimensionality Reduction](https://mlsanity.com/paper/1711.08797/) (2017)
- [Random projections: data perturbation for classification problems](https://mlsanity.com/paper/1911.10800/) (2019)
- [Randomized spectral co-clustering for large-scale directed networks](https://mlsanity.com/paper/2004.12164/) (2020)
- [On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/1706.10110/) (2017)
- [Projection-Cost-Preserving Sketches: Proof Strategies and Constructions](https://mlsanity.com/paper/2004.08434/) (2020)
- [Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing](https://mlsanity.com/paper/1410.2470/) (2014)
- [Johnson-Lindenstrauss Compression with Neuroscience-Based Constraints](https://mlsanity.com/paper/1411.5383/) (2014)
- [Improved Subsampled Randomized Hadamard Transform for Linear SVM](https://mlsanity.com/paper/2002.01628/) (2020)
- [SUOD: Toward Scalable Unsupervised Outlier Detection](https://mlsanity.com/paper/2002.03222/) (2020)
- [Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets](https://mlsanity.com/paper/1712.01774/) (2017)

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

- [APOLLO: SGD-like Memory, AdamW-level Performance](https://mlsanity.com/paper/2412.05270/) (2024)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [The Blessing and Curse of Dimensionality in Safety Alignment](https://mlsanity.com/paper/2507.20333/) (2025)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.11408/) (2022)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Parametrized Power-Iteration Clustering for Directed Graphs](https://mlsanity.com/paper/2210.00310/) (2022)
- [Exact Non-Oblivious Performance of Rademacher Random Embeddings](https://mlsanity.com/paper/2303.11774/) (2023)
- [Preserving Angles Improves Feature Distillation](https://mlsanity.com/paper/2411.15239/) (2024)
- [FedRP: A Communication-Efficient Approach for Differentially Private Federated Learning Using Random Projection](https://mlsanity.com/paper/2509.10041/) (2025)
- [Privacy-Preserving EHR Data Transformation via Geometric Operators: A Human-AI Co-Design Technical Report](https://mlsanity.com/paper/2603.22954/) (2026)

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