The matrix $A:mathbb{R}^n to mathbb{R}^m$ is $(delta,k)$-regular if for any $k$-sparse vector $x$, $$ left| |Ax|_2^2-|x|_2^2right| leq delta sqrt{k} |x|_2^2. $$ We show that if $A$ is $(delta,k)$-regular for $1 leq k leq 1/delta^2$, then by multiplying the columns of $A$ by independent random signs, the resulting random ensemble $A_epsilon$ acts on an arbitrary subset $T subset mathbb{R}^n$ (almost) as if it were gaussian, and with the optimal probability estimate: if $ell_*(T)$ is the gaussian mean-width of $T$ and $d_T=sup_{t in T} |t|_2$, then with probability at least $1-2exp(-c(ell_*(T)/d_T)^2)$, $$ sup_{t in T} left| |A_epsilon t|_2^2-|t|_2^2 right| leq Cleft(Lambda d_T deltaell_*(T)+(delta ell_*(T))^2 right), $$ where $Lambda=max{1,delta^2log(ndelta^2)}$. This estimate is optimal for $0<delta leq 1/sqrt{log n}$.
Download