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

Simple item page
dc.creatorAdamczak, Radosław
dc.creatorLitvak, Alexander E.
dc.creatorPajor, Alain
dc.creatorTomczak-Jaegermann, Nicole
dc.date2009-04-30
dc.date.accessioned2026-07-07T13:10:05Z
dc.date.available2026-07-07T13:10:05Z
dc.descriptionThis 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)$.
dc.identifierhttps://arxiv.org/abs/0904.4723
dc.identifierhttp://arxiv.org/abs/0904.4723
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228948
dc.subjectProbability
dc.subjectMetric Geometry
dc.subject52A20, 94A12, 52B12, 46B09 (Primary) 15A52, 41A45, 94B75 (Secondary)
dc.titleRestricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
dc.typetext

Files

Collections

arXiv