Exact recovery conditions for sparse representations with partial support information - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Information Theory Year : 2013

Exact recovery conditions for sparse representations with partial support information

(1) , (2) , (3) , (4)
1
2
3
4

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$.
Fichier principal
Vignette du fichier
main_v2.pdf (234.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00907646 , version 1 (21-11-2013)

Identifiers

Cite

Cédric Herzet, Charles Soussen, Jérôme Idier, Rémi Gribonval. Exact recovery conditions for sparse representations with partial support information. IEEE Transactions on Information Theory, 2013, 59 (11), pp.7509-7524. ⟨10.1109/TIT.2013.2278179⟩. ⟨hal-00907646⟩
977 View
528 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More