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} \) .
Origine : Fichiers produits par l'(les) auteur(s)
Loading...