 Johnson–Lindenstrauss lemma

For $0<\epsilon <1$ and any $n$ points in a Hilbert space, there is a linear map into Euclidean dimension $O({\epsilon }^{-2}\log n)$ that multiplies every pairwise distance by a factor between $1-\epsilon$ and $1+\epsilon$.

The striking feature is that the target dimension depends on the number of points and the allowed error, independently of the ambient dimension. Fix a finite set $S=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^D$, with $n\ge 2$, and $0<\epsilon <1$. An equivalent sufficient statement uses squared Euclidean distances: a linear map $T:{\mathbb{R}}^D\to {\mathbb{R}}^k$ exists, with $k=O({\epsilon }^{-2}\log n)$, such thatThe finite-set theorem cited here supplies an explicit sufficient target dimension for this squared-distance formulation. ^[ref]

Taking square roots gives distance factors $\sqrt{1-\epsilon }$ and $\sqrt{1+\epsilon }$, which lie inside $[1-\epsilon ,1+\epsilon ]$. Conversely, bounds $1\pm \epsilon$ on distances only give squared-distance bounds $(1\pm \epsilon {)}^2$; the same numerical tolerance should not be silently used for both. Under the squared-distance bounds, the bi-Lipschitz distortion is at most $\sqrt{(1+\epsilon )/(1-\epsilon )}$.

The Johnson–Lindenstrauss lemma preserves this fixed finite set, rather than every vector in the ambient Euclidean space. A linear map with $k<D$ has a nonzero kernel by the rank-nullity theorem, so some nonzero vectors collapse completely. For finitely many points in a real Hilbert space, apply the finite-dimensional argument on their linear span and extend by orthogonal projection onto that linear span. If the sufficient target dimension exceeds the ambient dimension, the identity map already preserves every Euclidean distance exactly, with zero padding if a larger target is requested.

The Johnson–Lindenstrauss (JL) lemma is a result in mathematics and computer science that states that a set of high-dimensional points can be embedded into a lower-dimensional space in such a way that the distances between the points are approximately preserved. More formally, the lemma asserts that for any set of points in a high-dimensional Euclidean space, there exists a mapping to a lower-dimensional Euclidean space that maintains the pairwise distances between points within a small factor.