Enhanced Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay

Cédric Herzet 1 Charles Soussen 2
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
Abstract : In this paper, we focus on two popular instances of greedy algorithms, namely orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). The suboptimal nature of OMP and OLS has led many researchers to study conditions under which these procedures succeed in recovering the true sparse vector. This question has been widely addressed for OMP in the recent years, including worst-case uniform and probabilisticanalyses. Although OLS has been known in the literature for a few decades (under different names, exact recovery analysis for OLS have only appeared very recently. Most of the existing works deal with uniform guarantees: these conditions ensure the success of OMP/OLS for a given sparsity level (or a given support) irrespective of the magnitude of the non-zero coefficients. In contrast with these works, we derive new guarantees of success accounting for the decay of the non-zero elements of the sparse vector. Our conditions are expressed in terms of the mutual coherence of the dictionary $\mu$ and encompass, as particular cases, some well-known results of the literature.
Type de document :
Communication dans un congrès
international - Traveling Workshop on Interactions between Sparse models and Technology (iTwist'14), Aug 2014, Namur, Belgium. pp.36-37, 〈http://arxiv.org/abs/1410.0719〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01096266
Contributeur : Cedric Herzet <>
Soumis le : mercredi 17 décembre 2014 - 10:18:44
Dernière modification le : mercredi 11 avril 2018 - 01:51:17
Document(s) archivé(s) le : lundi 23 mars 2015 - 14:45:43

Fichier

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

Identifiants

  • HAL Id : hal-01096266, version 1

Citation

Cédric Herzet, Charles Soussen. Enhanced Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay. international - Traveling Workshop on Interactions between Sparse models and Technology (iTwist'14), Aug 2014, Namur, Belgium. pp.36-37, 〈http://arxiv.org/abs/1410.0719〉. 〈hal-01096266〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

100