| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Exact recovery conditions for sparse representations with partial support information
Abstract : We address the exact recovery of a $k$-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including wrong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on $\ell_p$-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence $\mu$ of the dictionary and relaxes the well-known condition $\mu<1/(2k-1)$ ensuring the recovery of any $k$-sparse vector in the non-informed setup. It reads $\mu<1/(2k-g+b-1)$ when the informed support is composed of $g$ good atoms and $b$ wrong atoms. We emphasize that our condition is complementary to some restricted-isometry based conditions by showing that none of them implies the other. Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of $\ell_p$-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when $p$ is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed $\ell_1$ problem, and the truncated NSP for $p<1$.
Cited literature [46 references]
https://hal.inria.fr/hal-00907646
Contributor : Cédric Herzet <>
Submitted on : Thursday, November 21, 2013 - 3:21:40 PM
Last modification on : Monday, May 18, 2020 - 2:33:52 PM
Document(s) archivé(s) le : Saturday, February 22, 2014 - 4:40:57 AM
Contributor : Cédric Herzet <>
Submitted on : Thursday, November 21, 2013 - 3:21:40 PM
Last modification on : Monday, May 18, 2020 - 2:33:52 PM
Document(s) archivé(s) le : Saturday, February 22, 2014 - 4:40:57 AM
File
main_v2.pdf
Files produced by the author(s)