K-step analysis of orthogonal greedy algorithms for non-negative sparse representations - Ecole Centrale de Nantes Accéder directement au contenu
Article Dans Une Revue Signal Processing Année : 2021

K-step analysis of orthogonal greedy algorithms for non-negative sparse representations

Résumé

This paper proposes an exact recovery analysis of greedy algorithms for non-negative sparse representations. Orthogonal greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS) consist of gradually increasing the solution support and updating the nonzero coefficients in the least squares sense. From a theoretical viewpoint, greedy algorithms have been extensively studied in terms of exact support recovery. In contrast, the exact recovery analysis of their non-negative extensions (NNOMP, NNOLS) remains an open problem. We show that when the mutual coherence mu is lower than 1/(2K-1), the iterates of NNOMP / NNOLS coincide with those of OMP / OLS, respectively, the latter being known to reach K-step exact recovery. Our analysis heavily relies on a sign preservation property satisfied by OMP and OLS. This property is of stand-alone interest and constitutes our second important contribution. Finally, we provide an extended discussion of the main challenges of deriving improved analyses for correlated dictionaries.
Fichier principal
Vignette du fichier
main.pdf (511.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01971697 , version 1 (07-01-2019)
hal-01971697 , version 2 (30-07-2020)
hal-01971697 , version 3 (24-02-2021)
hal-01971697 , version 4 (06-06-2021)
hal-01971697 , version 5 (20-07-2021)

Identifiants

Citer

Thi Thanh Nguyen, Charles Soussen, Jérôme Idier, El-Hadi Djermoune. K-step analysis of orthogonal greedy algorithms for non-negative sparse representations. Signal Processing, 2021, ⟨10.1016/j.sigpro.2021.108185⟩. ⟨hal-01971697v3⟩
455 Consultations
411 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More