= Johnson–Lindenstrauss lemma
{c}
{wiki}
For $0<\varepsilon<1$ and any $n$ points in a Hilbert space, there is a linear map into Euclidean dimension $O(\varepsilon^{-2}\log n)$ that multiplies every pairwise distance by a factor between $1-\varepsilon$ and $1+\varepsilon$.
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,\ldots,x_n\}\subset\mathbb R^D$, with $n\geq2$, and $0<\varepsilon<1$. An equivalent sufficient statement uses squared <Euclidean distances>: a <linear map> $T:\mathbb R^D\to\mathbb R^k$ exists, with $k=O(\varepsilon^{-2}\log n)$, such that
$$
(1-\varepsilon)\|x_i-x_j\|_2^2
\leq\|Tx_i-Tx_j\|_2^2
\leq(1+\varepsilon)\|x_i-x_j\|_2^2
\qquad(1\leq i<j\leq n).
$$
The finite-set theorem cited here supplies an explicit sufficient target <dimension> for this squared-distance formulation. <An elementary proof of a theorem of Johnson and Lindenstrauss by Sanjoy Dasgupta and Anupam Gupta>[An elementary proof of a theorem of Johnson and Lindenstrauss, Theorem 2.1, p. 61: bounds for squared distances]{ref}
Taking <square roots> gives distance factors $\sqrt{1-\varepsilon}$ and $\sqrt{1+\varepsilon}$, which lie inside $[1-\varepsilon,1+\varepsilon]$. Conversely, bounds $1\pm\varepsilon$ on distances only give squared-distance bounds $(1\pm\varepsilon)^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+\varepsilon)/(1-\varepsilon)}$.
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.
Back to article page
