Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares - Analyse et Décision en Traitement du Signal et Images Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Information Theory Année : 2013

Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares

Résumé

Tropp's analysis of Orthogonal Matching Pursuit (OMP) using the Exact Recovery Condition (ERC) is extended to a first exact recovery analysis of Orthogonal Least Squares (OLS). We show that when the ERC is met, OLS is guaranteed to exactly recover the unknown support in at most k iterations where k denotes the support cardinality. Moreover, we provide a closer look at the analysis of both OMP and OLS when the ERC is not fulfilled. The existence of dictionaries for which some subsets are never recovered by OMP is proved. This phenomenon also appears with basis pursuit where support recovery depends on the sign patterns, but it does not occur for OLS. Finally, numerical experiments show that none of the considered algorithms is uniformly better than the other but for correlated dictionaries, guaranteed exact recovery may be obtained after fewer iterations for OLS than for OMP.
Fichier principal
Vignette du fichier
erc_ols.pdf (848.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00637003 , version 1 (28-10-2011)
hal-00637003 , version 2 (13-11-2012)

Identifiants

Citer

Charles Soussen, Rémi Gribonval, Jérôme Idier, Cédric Herzet. Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares. IEEE Transactions on Information Theory, 2013, 59 (5), pp.3158-3174. ⟨10.1109/TIT.2013.2238606⟩. ⟨hal-00637003v2⟩
862 Consultations
579 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More