Restricted Isometry Property and lp sparse recovery failure - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Restricted Isometry Property and lp sparse recovery failure

Résumé

This paper considers conditions based on the restricted isometry constant (RIC) under which the solution of an underdetermined linear system with minimal lp norm, 0 < p [\leq] 1, is guaranteed to be also the sparsest one. Specifically matrices are identified that have RIC, [\delta_{2m}], arbitrarily close to 1/[{ \sqrt{2} \) \approx 0.707] where sparse recovery with p = 1 fails for at least one m-sparse vector. This indicates that there is limited room for improvement over the best known positive results of Foucart and Lai, which guarantee that `1-minimisation recovers all m-sparse vectors for any matrix with [\delta_{2m} <2(3-{ \sqrt{2})/7 \approx 0.4531]. We also present results that show, compared to [l~{1}] minimisation, [l~{p}] minimisation recovery failure is only slightly delayed in terms of the RIC values. Furthermore when `p optimisation is attempted using an iterative reweighted [l~{p}] scheme, failure can still occur for [\delta_{2m}] arbitrarily close to 1[{ \sqrt{2} \) .
Fichier principal
Vignette du fichier
15.pdf (100.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00370402 , version 1 (24-03-2009)

Identifiants

  • HAL Id : inria-00370402 , version 1

Citer

Mike Davies, Rémi Gribonval. Restricted Isometry Property and lp sparse recovery failure. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes - Bretagne Atlantique, Apr 2009, Saint Malo, France. ⟨inria-00370402⟩
159 Consultations
405 Téléchargements

Partager

Gmail Facebook X LinkedIn More