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
2 CRAN - Centre de Recherche en Automatique de Nancy
3 IRCCyN - Institut de Recherche en Communications et en Cybernétique de Nantes
4 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
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$.
Keywords : $ell _{p}$ relaxation $k$-step analysis exact support recovery mutual coherence orthogonal least squares orthogonal matching pursuit partial support information
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
https://hal.inria.fr/hal-00907646
Contributor : Cédric Herzet <>
Submitted on : Thursday, November 21, 2013 - 3:21:40 PM
Last modification on : Friday, April 26, 2019 - 8:58:09 AM
Long-term archiving on : Saturday, February 22, 2014 - 4:40:57 AM

File

main_v2.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA | EC-NANTES | IRSTEA | IRISA | UNAM | CRAN | UNIV-NANTES | IRCCYN-ADTSI | IRCCYN | INSTITUT-TELECOM | IRISA-D5 | UNIV-RENNES1 | UNIV-LORRAINE | UR1-UFR-ISTIC | CRAN-BIOSIS | UNIV-RENNES

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

1934

Files downloads

401

Contact


archive-ouverte@inria.fr