= Gaussian Johnson–Lindenstrauss transform
{c}
{title2=$T(x)=k^{-1/2}Gx$}
Draw a $k\times D$ <random matrix> $G$ whose entries are <independent random variables> with the <standard normal distribution>, and set
$$
T(x)=\frac1{\sqrt k}Gx.
$$
The factor $1/\sqrt k$ makes the <expected value> of the squared <L2 norm> equal to the original squared <L2 norm>. This <Gaussian Johnson–Lindenstrauss transform> is a <linear map>, generally not an <orthogonal projection>: its rows are not required to be <orthogonal vectors>. <Lecture notes on metric embeddings by Jiří Matoušek>[Lecture notes on metric embeddings, §2.1(b), p. 21, and Lemma 2.3.1, p. 24: independent Gaussian coefficients and normalization]{ref}
For the fixed <finite set> $S$, let $0<\delta<1$ be an allowed failure <probability>, and define
$$
c(\varepsilon)=\frac{\varepsilon^2}{4}-\frac{\varepsilon^3}{6}>0.
$$
With $\log$ denoting the <natural logarithm>, a sufficient <integer> target <dimension> is
$$
k\geq\left\lceil\frac{\log\bigl(n(n-1)/\delta\bigr)}{c(\varepsilon)}\right\rceil.
$$
Then one draw of this specified <random matrix> satisfies all the squared <Euclidean distance> bounds simultaneously with <probability> at least $1-\delta$. Since $c(\varepsilon)\geq\varepsilon^2/12$, the simpler sufficient bound $k\geq\lceil12\varepsilon^{-2}\log(n(n-1)/\delta)\rceil$ also works. Both are sufficient bounds for this argument; they do not claim the smallest possible target <dimension>.
This is a <probability> statement about a map drawn independently of the fixed <finite set>. It implies existence because the success <probability> is positive, but permits failed draws. The set cannot be chosen after inspecting the map with this same guarantee. In particular, no single draw preserves every possible <finite set> in the ambient <Euclidean space> when $k<D$.
Back to article page
