Restricted Isometry Constants where $\ell^p$ sparse recovery can fail for $0 < p \leq 1$

Abstract : This paper investigates conditions under which the solution of an underdetermined linear system with minimal Lp 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 L1 minimisation 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 L1 minimisation 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 Lp 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 L1 minimisation, Lp minimisation recovery failure is shown to be only slightly delayed in terms of the RIC values. Furthermore in this case the minimisation is nonconvex and it is important to consider the specific minimisation algorithm being used. It is shown that when Lp optimisation is attempted using an iterative reweighted L1 scheme, failure can still occur for δ_2m arbitrarily close to 1/√2.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2009, 55 (5), pp.2203--2214. 〈10.1109/TIT.2009.2016030〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00544759
Contributeur : Rémi Gribonval <>
Soumis le : jeudi 27 janvier 2011 - 22:27:44
Dernière modification le : mercredi 21 février 2018 - 01:59:53
Document(s) archivé(s) le : jeudi 28 avril 2011 - 02:31:16

Fichier

2009_IEEE_TIT_DaviesGribonval-...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michael Davies, Rémi Gribonval. Restricted Isometry Constants where $\ell^p$ sparse recovery can fail for $0 < p \leq 1$. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2009, 55 (5), pp.2203--2214. 〈10.1109/TIT.2009.2016030〉. 〈inria-00544759〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

178