= Almost-isometric Gaussian embedding from l2 into l1
{c}
{title2=$\ell_2^n\hookrightarrow\ell_1^k$}
Let $Z_{ij}$ be independent standard <Gaussian random variables>, let $\beta=\mathbb E|Z_{ij}|=\sqrt{2/\pi}$, and let $0<\delta<1$. For a fixed nonzero <vector> $x\in\mathbb R^n$, the random matrix
$$
(Tx)_i=\frac1{\beta k}\sum_{j=1}^nZ_{ij}x_j
$$
satisfies
$$
\mathbb P\bigl((1-\delta)\|x\|_2\leq\|Tx\|_1\leq(1+\delta)\|x\|_2\bigr)
\geq1-2e^{-c\delta^2k}.
$$
A net argument shows that $k\geq C_\varepsilon n$ permits a linear embedding of distortion below $1+\varepsilon$.
Back to article page
