Restricted Isometry Property of Matrices with Independent Columns and Neighborly Polytopes by Random Sampling

By Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann. 2009

152 citations recorded by the source corpus.

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ±X1,…,±XN∈ℝn, (N≥n). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a subexponential tail inequality possess the restricted isometry property 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/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⊂ℝn 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/log 2(cN/n).

Subfields: Applied Mathematics, Biomedical Engineering, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/22f22e8ded8af32841e32f3c10be0679d60b9300

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Biomedical Engineering

In Computational Mechanics

Citations in the corpus

Sub‐Weibull distributions: Generalizing sub‐Gaussian and sub‐Exponential properties to heavier tailed distributions (2019, result): “A version of this result also appears in Lemma 3.5 of Adamczak et al. (2011).”
Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression (2018, background): “direct corollaries of the results in Section3. In any case, (4.9) at least shows n˛k2(logp)2=suces for RIP n(k) to go to 0. Both (4.9) and (4.10) seem to compare slightly unfavorably to the works ofAdamczak et al. (2011) andGuedon et al.(2014,2015). However, there are some important dierences in the”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, unknown): “17) The following Lemma is similar to [2][Th.”
Restricted Eigenvalue Properties for Correlated Gaussian Designs (2010, background): “subexponential random matrices (Adamczak et al., 2009) provided that n = Ω(k log2(p/k)).”