On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions

Dirksen, Sjoerd; Lecue, Guillaume und Rauhut, Holger (2018): On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions. In: IEEE Transactions on Information Theory, Bd. 64, Nr. 8: S. 5478-5487

Abstract

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.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik > Lehrstuhl für Mathematik der Informationsverarbeitung
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 0018-9448
• Sprache: Englisch