| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Restricted Isometry Property and lp sparse recovery failure
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} \) .
Cited literature [17 references]
https://hal.inria.fr/inria-00370402
Contributor : Ist Rennes <>
Submitted on : Tuesday, March 24, 2009 - 12:18:09 PM
Last modification on : Tuesday, June 15, 2021 - 4:26:19 PM
Long-term archiving on: : Friday, October 12, 2012 - 2:15:37 PM
Contributor : Ist Rennes <>
Submitted on : Tuesday, March 24, 2009 - 12:18:09 PM
Last modification on : Tuesday, June 15, 2021 - 4:26:19 PM
Long-term archiving on: : Friday, October 12, 2012 - 2:15:37 PM
File
15.pdf
Files produced by the author(s)