# The Fast Johnson-Lindenstrauss Transform is Even Faster

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 4 Apr 2022.

## Builds on (most cited first, 7 of 7)

- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables](https://mlsanity.com/paper/1810.09006/) (2018)
- [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)
- [On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/1706.10110/) (2017)
- [Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets](https://mlsanity.com/paper/1712.01774/) (2017)
- [Fast and memory-optimal dimension reduction using Kac's walk](https://mlsanity.com/paper/2003.10069/) (2020)

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

- [The Blessing and Curse of Dimensionality in Safety Alignment](https://mlsanity.com/paper/2507.20333/) (2025)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [DiffRed: Dimensionality Reduction guided by stable rank](https://mlsanity.com/paper/2403.05882/) (2024)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)
- [On the Pseudo-Mixing of Kac's Walk](https://mlsanity.com/paper/2608.17374/) (2026)

## Abstract (arXiv)

The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of n points in d-dimensional Euclidean space into optimal k=O(varepsilon-2 ln n) dimensions, while preserving all pairwise distances to within a factor (1 ± varepsilon). The Fast JL transform supports computing the embedding of a data point in O(d ln d +k ln2 n) time, where the d ln d term comes from multiplication with a d × d Hadamard matrix and the k ln2 n term comes from multiplication with a sparse k × d matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between varepsilon, d and n. In this work, we give a surprising new analysis of the Fast JL transform, showing that the k ln2 n term in the embedding time can be improved to (k ln2 n)/α for an α = Omega(minvarepsilon-1ln(1/varepsilon), ln n). The improvement follows by using an even sparser matrix. We also complement our improved analysis with a lower bound showing that our new analysis is in fact tight.