= Rademacher Johnson–Lindenstrauss transform
{c}
If $A\in\{-1,1\}^{d\times p}$ has independent <Rademacher random variable>[Rademacher] entries, then for fixed $u\ne0$ and $0<t<1$,
$$
\mathbb P\left(\left|\frac{\lVert Au\rVert_2^2}{d\lVert u\rVert_2^2}-1\right|\geq t\right)
\leq2e^{-dt^2/136}.
$$
Applying a <union bound> to all pairwise differences embeds $n$ fixed points into dimension $O(t^{-2}\log(n/\varepsilon))$ while preserving every squared distance within a factor $1\pm t$ with probability at least $1-\varepsilon$.
Back to article page
