Johnson–Lindenstrauss lemma | Aseem Raj Baranwal

Take $n$ points in a Euclidean space of any dimension $D$ , and fix a tolerance $\varepsilon \in (0, 1)$ . The Johnson–Lindenstrauss lemma says there is a linear map into dimension

k \;=\; O\!\left(\frac{\log n}{\varepsilon^2}\right)

that changes every pairwise distance by a factor of at most $1 \pm \varepsilon$ . Two features deserve a double take. The target dimension $k$ does not involve the source dimension $D$ at all: a million points in $D = 10^9$ compress exactly as well as a million points in $D = 10^3$ . And the dependence on $n$ is only logarithmic: squaring the number of points merely doubles $k$ .

Better still, the map is oblivious: it is a random projection drawn without looking at the data, and it works for any point set with high probability. This is a different contract from PCA, which studies the data first and preserves global variance directions with no guarantee for any individual pair; the lemma guarantees every pair, and never reads the data. The proof below is the elementary one of Dasgupta and Gupta, and it is two moves long: a tail bound for a single vector, then a union bound.

The statement

Let $A$ be a random $k \times D$ matrix with independent $\mathcal{N}(0, 1/k)$ entries. For $n$ points $x_1, \ldots, x_n \in \mathbb{R}^D$ and

k \;\ge\; \frac{4 \ln n}{\varepsilon^2/2 - \varepsilon^3/3},

with positive probability the map $f(x) = Ax$ satisfies, for every pair $i, j$ ,

(1 - \varepsilon)\, \|x_i - x_j\|^2 \;\le\; \|f(x_i) - f(x_j)\|^2 \;\le\; (1 + \varepsilon)\, \|x_i - x_j\|^2 .

One vector at a time

The map is linear, so $f(x_i) - f(x_j) = A(x_i - x_j)$ : the lemma’s requirement is exactly that $A$ preserve the squared norms of the $\binom{n}{2}$ vectors $x_i - x_j$ up to the factor $1 \pm \varepsilon$ . Rescaling changes nothing, since $A(cv) = c\,Av$ multiplies $\|Av\|^2$ and $\|v\|^2$ by the same $c^2$ , so each of these vectors may be divided by its length. Everything then rests on a single claim: for one fixed unit vector $u \in \mathbb{R}^D$ , the squared image $\|Au\|^2$ lies within $\varepsilon$ of 1 with high probability.

Each coordinate of $Au$ is a Gaussian linear combination, $(Au)_i = \sum_j A_{ij} u_j \sim \mathcal{N}(0, 1/k)$ , and the $k$ coordinates are independent since they come from disjoint rows. This is the 2-stability of the Gaussian: projecting any unit vector, in any dimension, produces the same distribution, which is the source of the lemma’s indifference to $D$ . Consequently

k\,\|Au\|^2 \;\sim\; \chi^2_k,

a chi-square with $k$ degrees of freedom: mean $k$ , so $\mathbb{E}\|Au\|^2 = 1$ , exactly the right scale. What remains is concentration, and the chi-square is generous with its moment generating function: $\mathbb{E}\,e^{tZ} = (1 - 2t)^{-k/2}$ for $Z \sim \chi^2_k$ , $t < 1/2$ . The Chernoff recipe, exponentiate, apply Markov, optimize $t$ , runs in closed form. For the upper tail, $t = \tfrac{\varepsilon}{2(1+\varepsilon)}$ gives

\mathbb{P}\bigl(Z \ge (1+\varepsilon)k\bigr) \;\le\; \bigl[(1+\varepsilon)\,e^{-\varepsilon}\bigr]^{k/2},

and symmetrically $\mathbb{P}(Z \le (1-\varepsilon)k) \le [(1-\varepsilon)\,e^{\varepsilon}]^{k/2}$ . The elementary inequalities $\ln(1+\varepsilon) \le \varepsilon - \varepsilon^2/2 + \varepsilon^3/3$ and $\ln(1-\varepsilon) \le -\varepsilon - \varepsilon^2/2$ turn both brackets into a single clean exponential:

\mathbb{P}\Bigl( \bigl|\, \|Au\|^2 - 1 \,\bigr| > \varepsilon \Bigr) \;\le\; 2 \exp\!\left( -\frac{k}{2} \left( \frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3} \right) \right).

One unit vector survives projection except with exponentially small probability in $k$ .

The union bound and the constant

A union bound turns the single-vector tail into a statement about all pairs. There are $\binom{n}{2} \le n^2/2$ vectors $x_i - x_j$ to preserve, so the probability that any pair is distorted beyond $1 \pm \varepsilon$ is at most

n^2 \exp\!\left( -\frac{k}{2} \left( \frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3} \right) \right),

which drops below 1 exactly when $k > 4\ln n \,/\, (\varepsilon^2/2 - \varepsilon^3/3)$ , and below $n^{-2\gamma}$ when $k$ carries the extra factor $(1+\gamma)$ . That is the whole proof, and it exposes the anatomy of the constant: the per-pair failure probability must be pushed below $1/n^2$ , an exponential tail converts that demand into $2 \ln n$ in the exponent, and the $\varepsilon^2$ in the tail is the curvature of the chi-square around its mean. The $\log n$ in the lemma is not geometry; it is the price of a union bound, paid in dimensions.

The numbers

The bound is explicit, so it can be evaluated at concrete values of $n$ and $\varepsilon$ :

For $n = 10^6$ points at $\varepsilon = 0.1$ the bound asks for $k \approx 11{,}800$ dimensions, and the $\varepsilon^{-2}$ factor is the term that controls the cost: halving the tolerance quadruples $k$ , while relaxing it to $\varepsilon = 0.2$ brings the same million points down to about $3{,}200$ . In the other direction, the figures hold whether the points live in a thousand dimensions or a billion, and pushing $n$ from a million to a trillion only doubles them. The bound is also worst-case over all point sets and demands every pair simultaneously; practice routinely uses smaller $k$ and measures the distortion it actually gets, which for natural data is usually gentler than the guarantee.

There is a pleasant symmetry with the usual complaints about high dimensions. Concentration of measure is the villain in the story where nearest-neighbor distances stop being informative and the reason Gaussian samples crowd onto a thin spherical shell; here the same phenomenon is the entire mechanism, harnessed rather than suffered: the projection works precisely because a chi-square with $k$ degrees of freedom concentrates hard around its mean.

Variants and the lower bound

The Gaussian matrix is the cleanest to analyze, not the cheapest to use, and a line of work has replaced it while preserving the guarantee. Achlioptas showed entries drawn uniformly from $\pm 1$ work, as does a version with two thirds of the entries zero: no Gaussian sampling, integer arithmetic, the same $k$ up to constants. Ailon and Chazelle’s fast transform preconditions with a randomized Hadamard matrix so the projection takes roughly $D \log D$ time instead of $kD$ . Kane and Nelson pushed sparsity to a handful of nonzeros per column. On the applications side, the lemma is a workhorse wherever pairwise Euclidean geometry must survive compression: approximate nearest-neighbor search, where it entered algorithm design through Indyk and Motwani; sketching and streaming; and, through the restricted isometry property, the recovery guarantees of compressed sensing, where a JL-style bound applied to all sparse vectors at once plays the starring role.

For thirty years the nagging question was whether the $\varepsilon^{-2} \log n$ was an artifact of the union-bound proof. It is not. Larsen and Nelson proved in 2017 that for every $n$ and $\varepsilon$ there are point sets for which any embedding into $k$ dimensions with distortion $1 \pm \varepsilon$ , linear or not, requires $k = \Omega(\varepsilon^{-2} \log n)$ . The elementary argument above is optimal up to the constant: two moves, and no cleverness left on the table.

A little history

The lemma was never meant to headline. Johnson and Lindenstrauss proved it in a 1984 paper on a question in functional analysis, whether Lipschitz maps defined on $n$ -point subsets of a metric space extend to the whole space into Hilbert space with controlled norm growth, and the dimension-reduction statement was a lemma en route, proved there with random orthogonal projections. Frankl and Maehara tightened the constants in 1988. The result crossed into computer science in the late 1990s, most visibly through Indyk and Motwani’s 1998 work on approximate nearest neighbors, and Dasgupta and Gupta’s 2003 note stripped the proof down to the chi-square computation given above. Larsen and Nelson’s 2017 optimality theorem closed the gap between what the union bound pays and what geometry demands, a rare case of a two-step argument from the 1980s being the final word.

References

William B. Johnson, Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189–206, 1984. The original paper; the lemma is the tool, not the theorem.
Peter Frankl, Hiroshi Maehara. The Johnson–Lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Series B, 44(3):355–362, 1988. Sharpened constants and an early application.
Piotr Indyk, Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. Proceedings of STOC, 604–613, 1998. The lemma as an algorithmic workhorse.
Sanjoy Dasgupta, Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures and Algorithms, 22(1):60–65, 2003. The chi-square proof followed above.
Dimitris Achlioptas. Database-friendly random projections: Johnson–Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687, 2003. The ±1 and sparse constructions.
Nir Ailon, Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on Computing, 39(1):302–322, 2009. The Hadamard-preconditioned fast transform.
Daniel M. Kane, Jelani Nelson. Sparser Johnson–Lindenstrauss transforms. Journal of the ACM, 61(1):1–23, 2014. Near-optimal sparsity per column.
Kasper Green Larsen, Jelani Nelson. Optimality of the Johnson–Lindenstrauss lemma. Proceedings of FOCS, 633–638, 2017. The matching lower bound.