Skip to Main content Skip to Navigation
Journal articles

Exact recovery conditions for sparse representations with partial support information

Cédric Herzet 1 Charles Soussen 2 Jérôme Idier 3 Rémi Gribonval 4
1 FLUMINANCE - Fluid Flow Analysis, Description and Control from Image Sequences
IRSTEA - Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture, Inria Rennes – Bretagne Atlantique
4 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
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$.
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
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


Files produced by the author(s)



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, Institute of Electrical and Electronics Engineers, 2013, 59 (11), pp.7509-7524. ⟨10.1109/TIT.2013.2278179⟩. ⟨hal-00907646⟩



Record views


Files downloads