Subgaussian concentration of the absolute Gaussian average

For a standard normal variable $Y$ and $\beta =\mathbb{E}|Y|=\sqrt{2/\pi }$,The exponential Markov inequality consequently gives Gaussian concentration for averages of independent copies of $|Y|$.

The random matrixsatisfiesA net argument shows that $k\ge C_{\epsilon }n$ permits a linear embedding of distortion below $1+\epsilon$.

Every $n$-point metric space embeds into ${\ell }_1^{O(\log n)}$ with distortion $O(\log n)$. Apply the Bourgain embedding theorem, reduce its Euclidean dimension to $O(\log n)$ with the Johnson–Lindenstrauss lemma, and use an Almost-isometric Gaussian embedding from l2 into l1.