The Johnson–Lindenstrauss lemma · 15-minute mathematical summary
CS 574 · University of Illinois, Urbana-Champaign · Fall 2026
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\).
\[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.
\[f(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2},\qquad X\sim N(0,1).\]
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.
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\).
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.
\[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\)?
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.
\[\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.
\[\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.
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.
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.
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.\]
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.
\[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.
\[\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.
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\).
CS 574 · Dimension reduction · Notes 26