On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions

Sjoerd Dirksen, Guillaume Lecue, Holger Rauhut

Research output: Contribution to journalArticleAcademicpeer-review


We consider the problem of recovering sparse vectors from underdetermined linear measurements via ℓ p -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 ℓ q /ℓ 1 -recovery guarantees for ℓ p -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.
Original languageEnglish
Pages (from-to)5478-5487
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number8
Publication statusPublished - 1 Aug 2018
Externally publishedYes


  • Standards
  • Robustness
  • Sparse matrices
  • Noise reduction
  • Atmospheric measurements
  • Particle measurements
  • Compressed sensing
  • Restricted isometry property
  • compressive sensing
  • lp-constrained basis pursuit
  • Gaussian random matrix
  • quantized compressive sensing


Dive into the research topics of 'On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions'. Together they form a unique fingerprint.

Cite this