Random polytopes obtained by matrices with heavy tailed entries

Abstract

Let $\Gamma$ be an $N\times n$ random matrix with independent entries and such that in each row entries are i.i.d. Assume also that the entries are symmetric, have unit variances, and satisfy a small ball probabilistic estimate uniformly. We investigate properties of the corresponding random polytope ${\Gamma }^{\ast }{B}_1^N$ in $\mathbb{R}$ (the absolute convex hull of rows of $\Gamma$). In particular, we show that $$\Gamma B_1^N\supset b^{-1}\left(B_{\infty }^n\cap \sqrt{\ln (N/n)}{B}_2^n\right).$$ where $b$ depends only on parameters in small ball inequality. This extends results of \cite{LPRT} and recent results of \cite{KKR}. This inclusion is equivalent to so-called ${\ell }_1$-quotient property and plays an important role in compressive sensing (see \cite{KKR} and references therein).

Last version, to appear in Communications in Contemporary Mathematics