# Restricted Isometry Property and lp sparse recovery failure

2 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : 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} \) .
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Domaine :

Littérature citée [17 références]

https://hal.inria.fr/inria-00370402
Contributeur : Ist Rennes <>
Soumis le : mardi 24 mars 2009 - 12:18:09
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 14:15:37

### Fichier

15.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00370402, version 1

### Citation

Mike Davies, Rémi Gribonval. Restricted Isometry Property and lp sparse recovery failure. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00370402〉

### Métriques

Consultations de la notice

## 305

Téléchargements de fichiers