2009/04/30 by Adamczak, Radosław, Litvak, Alexander E., Pajor, Alain +1 · 2 citations
#41A45 #46B09 (Primary) 15A52 #52A20 #52B12 #94A12 #94B75 (Secondary) #FOS: Mathematics #Metric Geometry (math.MG) #Probability (math.PR)
paper · doi:10.48550/arxiv.0904.4723
This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ± X1,...,± XN∈\Rn, (N≥ 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 ℓ1 minimization with m≤ Cn/log2 (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⊂ \Rn is a convex body and X1,..., XN∈ 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∼ n/log2 (cN/n).