= Gaussian Johnson–Lindenstrauss concentration argument
{c}
{title2=$\mathbb P(|R_u-1|\geq\varepsilon)\leq2e^{-kc(\varepsilon)}$}
A short <concentration inequality> argument explains the bound. For a fixed nonzero <vector> $u$, the normalized row products $\langle G_a,u\rangle/\|u\|_2$ are <independent random variables> with the <standard normal distribution>, so
$$
R_u=\frac{\|Tu\|_2^2}{\|u\|_2^2}\ \sim\ \frac{\chi_k^2}{k},
\qquad\mathbb E R_u=1,\qquad\operatorname{Var}(R_u)=\frac2k.
$$
Use the <moment-generating function of a chi-squared distribution> and the <Chernoff bound> to obtain
$$
\begin{aligned}
\mathbb P(R_u\geq1+\varepsilon)
&\leq\exp\!\left[-\frac k2\bigl(\varepsilon-\log(1+\varepsilon)\bigr)\right],\\
\mathbb P(R_u\leq1-\varepsilon)
&\leq\exp\!\left[-\frac k2\bigl(-\varepsilon-\log(1-\varepsilon)\bigr)\right].
\end{aligned}
$$
For $0<\varepsilon<1$, elementary <logarithm> inequalities bound their sum by $2e^{-kc(\varepsilon)}$. Apply the <union bound> to the $\binom n2$ nonzero pair differences to get failure <probability> at most $n(n-1)e^{-kc(\varepsilon)}\leq\delta$. Independence of different pairs is unnecessary; they use the same map. This combines fixed-<vector> concentration with a finite-set <union bound>. <Lecture notes on metric embeddings by Jiří Matoušek>[Lecture notes on metric embeddings, §2.1, pp. 20–21, and proof of Lemma 2.3.1, pp. 25–26: fixed-vector concentration and union bound over pair differences]{ref}
Back to article page
