On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions

Sjoerd Dirksen, Guillaume Lecué, Holger RauhutIEEE Trans. Information Theory 2018 · DOI · OpenReview

Abstract

We consider the problem of recovering sparse vectors from underdetermined linear measurements via ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -constrained basis pursuit. Previous analyses of this problem based on generalized restricted isometry properties have suggested that two phenomena occur if p ≠ 2. First, one may need substantially more than s log(en/s) measurements (optimal for p = 2) for uniform recovery of all s-sparse vectors. Second, the matrix that achieves recovery with the optimal number of measurements may not be Gaussian (as for p = 2). We present a new, direct analysis, which shows that in fact neither of these phenomena occur. Via a suitable version of the null space property, we show that a standard Gaussian matrix provides ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> /ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -recovery guarantees for ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -constrained basis pursuit in the optimal measurement regime. Our result extends to several heavier-tailed measurement matrices. As an application, we show that one can obtain a consistent reconstruction from uniform scalar quantized measurements in the optimal measurement regime.
BibTeX
@article{dirksen2018gap,
  author = {Sjoerd Dirksen and Guillaume Lecué and Holger Rauhut},
  title = {{On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  doi = {10.1109/tit.2016.2570244},
}

Loading related content...

Figure