Mathematics – Probability
Scientific paper
2009-04-30
Mathematics
Probability
Scientific paper
This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors $\pm X_1,...,\pm X_N\in\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 \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)$.
Adamczak Radosław
Litvak Alexander E.
Pajor Alain
Tomczak-Jaegermann Nicole
No associations
LandOfFree
Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-442507