Gaussian Johnson–Lindenstrauss transform ($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 setThe 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. ^[ref]

For the fixed finite set $S$, let $0<\delta <1$ be an allowed failure probability, and defineWith $\log$ denoting the natural logarithm, a sufficient integer target dimension isThen one draw of this specified random matrix satisfies all the squared Euclidean distance bounds simultaneously with probability at least $1-\delta$. Since $c(\epsilon )\ge {\epsilon }^2/12$, the simpler sufficient bound $k\ge \lceil 12{\epsilon }^{-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$.