Dimension Reduction

The Johnson–Lindenstrauss lemma · 15-minute mathematical summary

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign · Fall 2026

The desired guarantee

For \(P=\{p_1,\ldots,p_n\}\subseteq\mathbb R^d\), find images \(h(p_i)\in\mathbb R^k\) such that, for every \(i,j\),

\[ (1-\varepsilon)\|p_i-p_j\| \leq\|h(p_i)-h(p_j)\| \leq(1+\varepsilon)\|p_i-p_j\|. \]

Throughout the proof, \(n\geq2\) and \(0<\varepsilon<1/2\).

Matrix form

\[A=\frac1{\sqrt k} \begin{pmatrix}u_1^\top\\u_2^\top\\\vdots\\u_k^\top\end{pmatrix} \in\mathbb R^{k\times d},\qquad h(p)=Ap.\]

Take independent standard Gaussian vectors \(u_i\) and set \(k=\lceil24\varepsilon^{-2}\ln n\rceil\). Use the same \(A\) for all points.

The standard normal density

\[f(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2},\qquad X\sim N(0,1).\]

Standard normal density, symmetric about zero.

A Gaussian vector in \(d\) dimensions

Take independent \(X_1,\ldots,X_d\sim N(0,1)\) and set \(u=(X_1,\ldots,X_d)\).

\[g_d(x)=\prod_{j=1}^d f(x_j) =(2\pi)^{-d/2}\exp\left(-\frac12\sum_{j=1}^d x_j^2\right).\]

Its density integrates to one by the product structure.

Projection onto a unit direction

Fix \(v\in\mathbb R^d\) with \(\|v\|=1\). Choose a rotation \(R\) with \(Rv=e_1\).

\[\langle v,u\rangle=\langle Rv,Ru\rangle =\langle e_1,Ru\rangle\sim N(0,1).\]

The first coordinate of \(Ru\) has the same distribution as \(X_1\).

One fixed unit vector

Fix \(v\) independently of the sampled matrix, with \(\|v\|=1\).

Set \(X_i=\langle u_i,v\rangle\). Then \[Av=\frac1{\sqrt k}(X_1,\ldots,X_k),\qquad X_i\sim N(0,1).\]

The \(X_i\) are independent because the rows \(u_i\) are independent.

Squared length

\[Y=\sum_{i=1}^k X_i^2,\qquad Z=\frac Yk=\|Av\|^2.\]

\(Y\) has the chi-square distribution with \(k\) degrees of freedom.

The question is now one-dimensional: how concentrated is \(Z\) around \(1\)?

Exponential Markov inequality

For \(0<t<1/2\),

\[\begin{aligned} \Pr[Z\geq1+\varepsilon] &=\Pr[e^{tkZ}\geq e^{tk(1+\varepsilon)}]\\ &\leq e^{-tk(1+\varepsilon)}\mathbb E[e^{tkZ}]. \end{aligned}\]

We need the exponential moment of a squared normal variable.

Rescale to a normal density

\[\begin{aligned} \mathbb E[e^{tX^2}] &=\frac1{\sqrt{1-2t}}\, \frac1{\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-y^2/2}\,dy\\ &=(1-2t)^{-1/2}. \end{aligned}\]

The remaining integral is one by normalization.

Upper-tail conclusion

\[\boxed{\Pr[Z\geq1+\varepsilon]\leq e^{-k\varepsilon^2/16}.}\]

If \(k\geq16\varepsilon^{-2}\ln(2/\delta)\), the bound is at most \(\delta/2\).

This controls expansion. We still need to control contraction.

Two-sided chi-square tails

For \(Z=k^{-1}\sum_i X_i^2\) and any \(x>0\),

\[\Pr\left[Z\leq1-2\sqrt{x/k}\right]\leq e^{-x},\] \[\Pr\left[Z\geq1+2\sqrt{x/k}+2x/k\right]\leq e^{-x}.\]

Laurent–Massart, Lemma 1 (Laurent & Massart, 2000). Stated without proof, as in the notes.

Concentration corollary

If \(0<\delta<1\), \(0<\varepsilon<1/2\), and

\[k\geq\left\lceil8\varepsilon^{-2}\ln(2/\delta)\right\rceil,\]

then \[\boxed{\Pr[1-\varepsilon\leq Z\leq1+\varepsilon]\geq1-\delta.}\]

This is the two-sided estimate used in the JL proof.

Squared length to length

For \(0<\varepsilon<1\),

\[1-\varepsilon\leq\sqrt{1-\varepsilon}, \qquad\sqrt{1+\varepsilon}\leq1+\varepsilon.\]

Thus \(1-\varepsilon\leq\|Av\|^2\leq1+\varepsilon\) implies \[1-\varepsilon\leq\|Av\|\leq1+\varepsilon.\]

Failure budget for one direction

Set \(\delta=1/n^2\).

For \(n\geq2\), \[8\varepsilon^{-2}\ln(2n^2) \leq24\varepsilon^{-2}\ln n.\]

Our choice \(k=\lceil24\varepsilon^{-2}\ln n\rceil\) is sufficient.

Linearity preserves differences

\[Ap-Aq=A(p-q)=\|p-q\|Av_{pq}.\]

Therefore \[\frac{\|Ap-Aq\|}{\|p-q\|}=\|Av_{pq}\|.\]

Here \(v_{pq}=(p-q)/\|p-q\|\) for distinct \(p,q\). Distance distortion equals length distortion in this unit direction.

Union bound over all pairs

\[\Pr\left[\bigcup_{\{p,q\}\subseteq P}B_{pq}\right] \leq\sum_{\{p,q\}\subseteq P}\Pr[B_{pq}] \leq\binom n2\frac1{n^2} =\frac{n-1}{2n}<\frac12.\]

Here \(B_{pq}\) is the failure event for pair \(p,q\), with probability at most \(1/n^2\). Independence between pair events is unnecessary.

The Johnson–Lindenstrauss lemma

Given \(n\) points in \(\mathbb R^d\) and \(0<\varepsilon<1/2\), there is a map into

\[\mathbb R^k,\qquad k=O(\varepsilon^{-2}\log n),\]

that preserves every pairwise distance within a factor \(1\pm\varepsilon\).

The Gaussian construction succeeds with probability at least \(1/2\).

References

Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 604–613. https://doi.org/10.1145/276698.276876
Johnson, W. B., & Lindenstrauss, J. (1984). Extensions of lipschitz mapping into hilbert space. Contemporary Mathematics, 26, 189–206.
Laurent, B., & Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5), 1302–1338. https://doi.org/10.1214/aos/1015957395