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
IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE, Inria Rennes – Bretagne Atlantique
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
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2013, 59 (11), pp.7509-7524. 〈10.1109/TIT.2013.2278179〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00907646
Contributeur : Cedric Herzet <>
Soumis le : jeudi 21 novembre 2013 - 15:21:40
Dernière modification le : mercredi 19 décembre 2018 - 15:02:02
Document(s) archivé(s) le : samedi 22 février 2014 - 04:40:57

Fichier

main_v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

1874

Téléchargements de fichiers

335

Contact


archive-ouverte@inria.fr