Restricted isometry constants where ℓp sparse recovery can fail for 0 < p ≤ 1

Michael Evans Davies*, Rémi Gribonval

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper investigates conditions under which the solution of an underdetermined linear system with minimal ℓp norm, 0 < p ≤ 1, is guaranteed to be also the sparsest one. Matrices are constructed with restricted isometry constants (RIC) δ2m arbitrarily close to 1 / √ 2 ≈ 0.707 where sparse recovery with p = 1 fails for at least one m-sparse vector, as well as matrices with δ2m arbitrarily close to one where ℓ1 minimization succeeds for any m-sparse vector. This highlights the pessimism of sparse recovery prediction based on the RIC, and indicates that there is limited room for improving over the best known positive results of Foucart and Lai, which guarantee that ℓ1 minimization recovers all m-sparse vectors for any matrix with δ2m < 2(3-√2)/7 ≈ 0.4531. These constructions are a by-product of tight conditions for ℓp recovery (0 ≤ p ≤ 1) with matrices of unit spectral norm, which are expressed in terms of the minimal singular values of 2m-column submatrices. Compared to ℓ1 minimization, ℓp minimization recovery failure is shown to be only slightly delayed in terms of the RIC values. Furthermore in this case the minimization is nonconvex and it is important to consider the specific minimization algorithm being used. It is shown that when ℓp optimization is attempted using an iterative reweighted ℓ1 scheme, failure can still occur for δ 2m arbitrarily close to 1/√2.

Original languageEnglish
Pages (from-to)2203-2214
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number5
Publication statusPublished - 27 May 2009

Keywords / Materials (for Non-textual outputs)

  • Compressed sensing
  • Convex optimization
  • Inverse problem
  • Iterative reweighted optimization
  • Nonconvex optimization
  • Overcomplete dictionary
  • Sparse representation
  • Testricted isometry property
  • uUnderdetermined linear system


Dive into the research topics of 'Restricted isometry constants where ℓp sparse recovery can fail for 0 < p ≤ 1'. Together they form a unique fingerprint.

Cite this