The Johnson–Lindenstrauss Lemma

A complete proof that random projection to O(log N / eps^2) dimensions preserves all pairwise distances, with the dimension requirement, the geometry and the limits of the result.

High-Dim ProbabilityGraduate⏱ 3 hours13 min readjohnson-lindenstraussrandom projectiondimension reductiondistortionembeddings

6 problems →

AssumesHigh-Dimensional Geometry and Concentration of the Norm · Nets, Covering Numbers and Metric Entropy

The single-vector statement

Everything follows from one lemma about one vector.

LemmaDistributional Johnson–Lindenstrauss lemma

Let $A \in \R^{k\times d}$ have i.i.d. $\Ncal(0,1/k)$ entries. For any fixed $x \in \R^d$ and any $\eps \in (0,1)$ ,

\P\Big( \big|\norm{Ax}_2^2 - \norm{x}_2^2\big| \ge \eps\norm{x}_2^2 \Big) \le 2\exp\left(-\frac{k\eps^2}{8}\right) .

The lemma

TheoremJohnson–Lindenstrauss lemma

Let $x_1,\dots,x_N \in \R^d$ and $\eps \in (0,1)$ . If

k \ge \frac{24\log N}{\eps^2},

and $A\in\R^{k\times d}$ has i.i.d. $\Ncal(0,1/k)$ entries, then with probability at least $1 - 1/N$ ,

(1-\eps)\norm{x_i - x_j}_2^2 \;\le\; \norm{Ax_i - Ax_j}_2^2 \;\le\; (1+\eps)\norm{x_i-x_j}_2^2 \qquad\text{for all } i,j .

Assumptions

The points are fixed in advance (the map is chosen after the points, but the points may not depend on the map); $A$ is a Gaussian random matrix with the stated variance; $\eps < 1$ . Nothing is assumed about $d$ , $N$ or the geometry of the point set.

Key idea

Count the exponents. Each pair fails with probability $e^{-k\eps^2/8}$ ; there are $\approx N^2$ pairs; so we need $e^{-k\eps^2/8} \ll N^{-2}$ , i.e. $k\eps^2 \gtrsim \log N$ . The $\eps^{-2}$ comes from the Gaussian shape of the concentration — a bound of the form $e^{-k\eps}$ would have given $\eps^{-1}$ — and the $\log N$ comes from the union bound, which is why the dependence is on the number of points and not on the dimension they started in.

Run it: Johnson–Lindenstrauss distortionPairwise distance distortion under a random Gaussian projection, as a function of the target dimension k.

Is the bound tight?

TheoremOptimality of the dimension bound

For every $\eps \in (0,1/2)$ and $N$ large enough there exist $N$ points in $\R^{O(\log N)}$ such that any map (linear or not) achieving distortion $1\pm\eps$ on all pairs must have target dimension

k = \Omega\!\left(\frac{\log N}{\eps^2\log(1/\eps)}\right).

This is the theorem of Larsen and Nelson, quoted from the reference. Its content is that the $\eps^{-2}\log N$ shape of the lemma is not an artefact of the proof technique — no cleverer construction can do essentially better. A weaker and much older observation goes the same way: an $\eps$ -distortion embedding of $N$ mutually near-orthogonal points needs $k \gtrsim \log N$ simply because $\R^k$ cannot hold more than $e^{O(k\eps^2)}$ points at pairwise distance $\ge (1-\eps)$ — a packing bound.

CorollaryInner products are preserved too

If the conclusion of the lemma holds for the point set $\{x_i\} \cup \{x_i \pm x_j\}$ , then for all $i,j$ ,

\big|\ip{Ax_i}{Ax_j} - \ip{x_i}{x_j}\big| \le \frac{\eps}{2}\left(\norm{x_i}_2^2+\norm{x_j}_2^2\right).

In particular unit vectors have their inner products preserved to additive $\eps$ .

This corollary is the version that matters for machine learning: it says a random projection approximately preserves the Gram matrix, hence approximately preserves every kernel method, every linear classifier's margins, and every cosine similarity used in retrieval.

What the lemma does not give you

Empirical observationDistance preservation is not neighbour preservation

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

A $1\pm\eps$ guarantee on all pairwise distances does not guarantee that the nearest neighbour of a query is preserved.

What this does not say

Suppose the nearest neighbour is at distance $1$ and the second nearest at distance $1 + \eps/2$ . After projection the first may be at $1+\eps$ and the second at $(1+\eps/2)(1-\eps) < 1 + \eps$ : the order has flipped, while every pairwise distance is within the guarantee. Nearest-neighbour preservation requires the relative gap between the true neighbour and its competitors to exceed $2\eps$ or so, which is an assumption about the data, not a consequence of the lemma.

Three further limits worth stating explicitly:

The lemma is about a fixed point set. If the query is chosen adversarially after seeing $A$ , all guarantees are void. This is why one cannot reuse a single projection matrix across an adaptively-chosen sequence of queries without care.
$\eps^{-2}$ is brutal in practice. Distortion $\eps = 0.01$ on $N = 10^6$ points needs $k \approx 24\log(10^6)/10^{-4} \approx 3.3\times10^6$ — larger than any plausible ambient dimension. The lemma is a statement about the regime $\eps$ constant, $N$ large.
No sparsity, no structure. A dense Gaussian $A$ costs $O(kd)$ per point to apply. Sparse and fast variants (the subsampled Hadamard transform, CountSketch, sparse JL) achieve similar guarantees with better runtime, and are what actual systems use.

Problems

Prove the Johnson–Lindenstrauss lemmaProof · Graduate · 3 hours The chi-squared moment generating function and its Chernoff boundProof · Intermediate · 30 min Johnson–Lindenstrauss dimension arithmeticNumerical · Beginner · 15 min Rademacher projections work tooProof · Advanced · 1 hour Implement random projection and measure the distortionCoding · Intermediate · 1 hour From distance preservation to inner-product preservationProof · Intermediate · 30 min

References

PaperWilliam B. Johnson and Joram Lindenstrauss (1984). Extensions of Lipschitz mappings into a Hilbert spaceThe original paper; the lemma appears as a tool in a functional-analysis argument.
PaperSanjoy Dasgupta and Anupam Gupta (2003). An elementary proof of a theorem of Johnson and LindenstraussThe proof strategy used below follows the standard elementary route this paper popularised; the exposition here is written independently.
PaperKasper Green Larsen and Jelani Nelson (2017). Optimality of the Johnson–Lindenstrauss lemmaEstablishes that the O(eps^{-2} log N) bound is tight.
BookRoman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data Science

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

LemmaDistributional Johnson–Lindenstrauss lemmaproof includedA random Gaussian projection preserves the norm of any single fixed vector to within a factor 1 ± eps with probability 1 − 2exp(−c k eps^2).
TheoremJohnson–Lindenstrauss lemmaproof includedAny N points in Euclidean space embed into O(eps^{-2} log N) dimensions with all pairwise distances preserved to within 1 ± eps.
TheoremOptimality of the dimension boundThe eps^{-2} log N dependence cannot be improved in general.
CorollaryInner products are preserved tooproof includedDistance preservation for a point set closed under differences implies inner-product preservation.
Empirical observationDistance preservation is not neighbour preservationA 1 ± eps distortion guarantee does not preserve the identity of the nearest neighbour when the gap to the runner-up is smaller than eps.

Experiments

Johnson–Lindenstrauss distortion
Pairwise distance distortion under a random Gaussian projection, as a function of the target dimension k.

Problems (6)

All problems

Papers that use this mathematics

Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, Douwe Kiela · 2020