Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Abstract

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors $\pm X_1,...,\pm X_N\in {\mathbb{R}}^n$, ($N\ge n$). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property (RIP) with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a sub-exponential tail inequality possess this property RIP with overwhelming probability. We show that such "sensing" matrices are valid for the exact reconstruction process of $m$-sparse vectors via ${\ell }_1$ minimization with $m\le Cn/{\log }^2(cN/n)$. The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if $K\subset {\mathbb{R}}^n$ is a convex body and $X_1,...,X_N\in K$ are i.i.d. random vectors uniformly distributed on $K$, then, with overwhelming probability, the symmetric convex hull of these points is an $m$-centrally-neighborly polytope with $m\sim n/{\log }^2(cN/n)$.

References in corpus (1)

• A probabilistic approach to the geometry of the \ell_p^n-ball

Cited by in corpus (1)

• Various thresholds for ${\ell }_1$-optimization in compressed sensing