Random embeddings with an almost Gaussian distortion

Abstract

Let $X$ be a symmetric, isotropic random vector in ${\mathbb{R}}^m$ and let $X_1...,X_n$ be independent copies of $X$. We show that under mild assumptions on $\Vert X{\Vert }_2$ (a suitable thin-shell bound) and on the tail-decay of the marginals $⟨X,u⟩$, the random matrix $A$, whose columns are $X_i/\sqrt{m}$ exhibits a Gaussian-like behaviour in the following sense: for an arbitrary subset of $T\subset {\mathbb{R}}^n$, the distortion ${\sup }_{t\in T}|\Vert At{\Vert }_2^2-\Vert t{\Vert }_2^2|$ is almost the same as if $A$ were a Gaussian matrix. A simple outcome of our result is that if $X$ is a symmetric, isotropic, log-concave random vector and $n\le m\le c_1(\alpha )n^{\alpha }$ for some $\alpha >1$, then with high probability, the extremal singular values of $A$ satisfy the optimal estimate: $1-c_2(\alpha )\sqrt{n/m}\le {\lambda }_{\min }\le {\lambda }_{\max }\le 1+c_2(\alpha )\sqrt{n/m}$.