Almost-isometric Gaussian embedding from l2 into l1
= Almost-isometric Gaussian embedding from l2 into l1
{c}
{title2=$\ell_2^n\hookrightarrow\ell_1^k$}
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$.