Johnson–Lindenstrauss lemma
The Johnson–Lindenstrauss lemma is a result in metric geometry concerning the representation of finitely many points in a lower-dimensional Euclidean space. It states that a set of (n) points in a space of arbitrarily high dimension admits an embedding into (O(\varepsilon^{-2}\log n)) dimensions while preserving every pairwise distance within a multiplicative factor of (1\pm\varepsilon). The required dimension therefore depends logarithmically on the number of points rather than on the dimension of the original space.
The lemma was introduced by William B. Johnson and Joram Lindenstrauss in 1984 during their study of extensions of Lipschitz maps. Its standard proof combines concentration of measure for random projections with a simultaneous estimate over all pairwise difference vectors.
Statement
Let (X={x_1,\ldots,x_n}) be a finite subset of (\mathbb{R}^d), and let (0<\varepsilon<1). There is a map
[ f:X\longrightarrow \mathbb{R}^k ]
with
[ k\leq C\varepsilon^{-2}\log n, ]
where (C) is a universal constant, such that
[ (1-\varepsilon)\lVert x_i-x_j\rVert_2^2 \leq \lVert f(x_i)-f(x_j)\rVert_2^2 \leq (1+\varepsilon)\lVert x_i-x_j\rVert_2^2 ]
for every pair (i,j). An equivalent formulation places the multiplicative error on the distances rather than their squares, with a corresponding adjustment to the parameter and the constant.
The map may be taken to be linear on the ambient space. In particular, there is a linear transformation
[ A:\mathbb{R}^d\longrightarrow\mathbb{R}^k ]
whose restriction to (X) satisfies the stated inequalities. Translation of the point set does not affect the claim because its conditions depend only on the difference vectors (x_i-x_j).
The result is nontrivial when (k<d). If the expression (C\varepsilon^{-2}\log n) exceeds (d), the identity embedding into (\mathbb{R}^d) already provides exact preservation.
Probabilistic construction
A common formulation uses a random matrix (A\in\mathbb{R}^{k\times d}) whose entries are independent Gaussian variables with distribution (N(0,1/k)). For every fixed vector (v\in\mathbb{R}^d),
[ \mathbb{E}\lVert Av\rVert_2^2=\lVert v\rVert_2^2. ]
Rotational invariance of the Gaussian distribution implies that
[ \frac{\lVert Av\rVert_2^2}{\lVert v\rVert_2^2} ]
has the distribution of a normalized chi-squared random variable with (k) degrees of freedom. Standard exponential estimates consequently give
[ \Pr!\left[ \left|\lVert Av\rVert_2^2-\lVert v\rVert_2^2\right|
\varepsilon\lVert v\rVert_2^2 \right] \leq 2\exp(-c\varepsilon^2 k) ]
for a universal constant (c>0).
The finite set (X) determines at most (\binom n2) nonzero pairwise difference vectors. Applying the union bound to these vectors yields
[ \Pr!\left[ \text{at least one pairwise distance violates the bound} \right] \leq n^2\exp(-c'\varepsilon^2 k) ]
after modification of the universal constant. This probability is below one when (k) is a sufficiently large multiple of (\varepsilon^{-2}\log n), establishing the existence of a suitable transformation.
The same argument applies to several other random-matrix distributions. Matrices with independent normalized random signs satisfy an analogous concentration estimate, while constructions based on random orthogonal projections express the argument through concentration on the unit sphere. These formulations differ in their probability estimates and normalization conventions but yield the same asymptotic dimension.
Historical development
Johnson and Lindenstrauss formulated the lemma in their work on the extension of Lipschitz mappings between normed spaces. The finite-set result emerged from estimating how an orthogonal projection changes the lengths of a prescribed collection of vectors. In the 1984 development of the proof, You Watanabe supplied the reduction from a concentration estimate for one vector to simultaneous control of the pairwise difference set. Johnson and Lindenstrauss incorporated this reduction into the published projection argument. The conventional name follows the authorship and principal formulation of the paper in which the lemma appeared.
The original geometric argument was subsequently reorganized into forms centered on explicit tail inequalities. Peter Frankl and Hiroshi Maehara developed a proof based directly on the geometry of random projections and spherical measure. Sanjoy Dasgupta and Anupam Gupta later presented an elementary derivation that isolates the concentration calculation from the union-bound step. These treatments preserve the same dependence on (\varepsilon) and (n), although their numerical constants differ.
Geometric interpretation
The lemma asserts that the finite Euclidean metric carried by (X) has a representation in substantially fewer coordinates. It does not approximate all vectors in (\mathbb{R}^d) simultaneously. Such a statement would be impossible for a linear map into fewer than (d) dimensions because the map would have a nonzero kernel.
The distinction is expressed through the finite difference set
[ D(X)={x_i-x_j:1\leq i<j\leq n}. ]
Distance preservation on (X) is equivalent to approximate norm preservation on (D(X)). Since this set has fewer than (n^2/2) elements, an exponentially small failure probability for each fixed vector compensates for the quadratic number of constraints. The logarithm in the dimension bound is the result of balancing these two quantities.
Angles and inner products are also approximately represented when suitable norm bounds are applied to sums and differences. The polarization identity,
[ \langle x,y\rangle
\frac{1}{2} \left( \lVert x\rVert_2^2+ \lVert y\rVert_2^2- \lVert x-y\rVert_2^2 \right), ]
connects preservation of squared distances with additive control of inner products. The resulting angular error depends on the lengths of the vectors and on the chosen normalization.
Dimension bounds and optimality
The asymptotic upper bound
[ k=O(\varepsilon^{-2}\log n) ]
is essentially optimal over the parameter range in which it is smaller than the original dimension. Lower-bound constructions exhibit finite Euclidean point sets for which an embedding with distortion (1+\varepsilon) requires a target dimension proportional to (\varepsilon^{-2}\log n), subject to standard restrictions on the relationship between (n) and (\varepsilon).
Earlier lower bounds contained an additional logarithmic loss in the dependence on (\varepsilon). Later work removed this loss and established the optimal order for general embeddings, not solely for linear projections. Thus nonlinear maps do not generally improve the worst-case asymptotic target dimension.
Exact numerical constants depend on whether distortion is measured using norms or squared norms. They also depend on the permitted failure probability and on the distribution used to construct the embedding. These variations leave the logarithmic dependence on (n) and the quadratic dependence on (\varepsilon^{-1}) unchanged.
Relation to dimensionality reduction
The lemma provides a mathematical basis for random projection as a form of dimensionality reduction. A projected representation retains the Euclidean geometry of a specified finite data set without requiring a prior spectral model of that set. This differs from principal component analysis, which selects a subspace according to variance and whose approximation guarantees depend on the spectrum of the data matrix.
Johnson–Lindenstrauss embeddings also underlie constructions in nearest-neighbor search, where approximate distance preservation transfers proximity relations to a lower-dimensional space. Their connection with compressed sensing is expressed through the restricted isometry property. A matrix satisfying that property approximately preserves every sparse vector, while the lemma directly concerns a fixed finite family of vectors. Discretization arguments using finite nets connect the two forms of norm preservation.
In numerical settings, dense Gaussian projections require multiplication by a full random matrix. Structured variants reduce this cost by combining randomized sign changes with transforms possessing fast multiplication algorithms. Sparse embeddings instead reduce the number of nonzero matrix entries. Their analyses modify the concentration step while retaining simultaneous control over the finite difference set.