Coherence-based Partial Exact Recovery Condition for OMP/OLS

Cedric 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
CEMAGREF, 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 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We address the exact recovery of the support of a k-sparse vector with Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS) in a noiseless setting. We consider the scenario where OMP/OLS have selected good atoms during the first l iterations (l < k) and derive a new sufficient and worst-case necessary condition for their success in k steps. Our result is based on the coherence of the dictionary and relaxes Tropp's well-known condition < 1=(2k 1) to the case where OMP/OLS have a partial knowledge of the support.
Type de document :
Pré-publication, Document de travail
IRIS, SBS. A revised version of this preprint appeared in the IEEE Trans. on Information Theory, vol 59, nr .. 2012
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00759433
Contributeur : Cedric Herzet <>
Soumis le : vendredi 30 novembre 2012 - 15:57:06
Dernière modification le : mercredi 16 mai 2018 - 11:48:03
Document(s) archivé(s) le : vendredi 1 mars 2013 - 03:56:34

Fichier

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

Identifiants

  • HAL Id : hal-00759433, version 1

Collections

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

Citation

Cedric Herzet, Charles Soussen, Jérôme Idier, Rémi Gribonval. Coherence-based Partial Exact Recovery Condition for OMP/OLS. IRIS, SBS. A revised version of this preprint appeared in the IEEE Trans. on Information Theory, vol 59, nr .. 2012. 〈hal-00759433〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

1388

Téléchargements de fichiers

145

Contact


archive-ouverte@inria.fr