When does OMP achieve exact recovery with continuous dictionaries? - Centre Henri Lebesgue Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

When does OMP achieve exact recovery with continuous dictionaries?

Résumé

This paper presents new theoretical results on sparse recovery guarantees for a greedy algorithm, Orthogonal Matching Pursuit (OMP), in the context of continuous parametric dictionaries. Here, the continuous setting means that the dictionary is made up of an infinite (potentially uncountable) number of atoms. In this work, we rely on the Hilbert structure of the observation space to express our recovery results as a property of the kernel defined by the inner product between two atoms. Using a continuous extension of Tropp's Exact Recovery Condition, we identify two key notions of admissible kernel and admissible support that are sufficient to ensure exact recovery with OMP. We exhibit a family of admissible kernels relying on completely monotone functions for which admissibility holds for any support in the one-dimensional setting. For higher dimensional parameter spaces, an additional notion of axis admissibility is shown to be sufficient to ensure a form of "delayed" recovery. An additional algebraic condition involving a finite subset of (known) atoms further yields exact recovery guarantees. Finally, a coherence-based viewpoint on these results provides recovery guarantees in terms of a minimum separation assumption.
Fichier principal
Vignette du fichier
acha.pdf (556.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02099464 , version 1 (15-04-2019)
hal-02099464 , version 2 (15-04-2019)
hal-02099464 , version 3 (17-04-2019)
hal-02099464 , version 4 (21-06-2020)

Identifiants

  • HAL Id : hal-02099464 , version 3

Citer

Clément Elvira, Rémi Gribonval, Charles Soussen, Cédric Herzet. When does OMP achieve exact recovery with continuous dictionaries?. 2019. ⟨hal-02099464v3⟩
763 Consultations
668 Téléchargements

Partager

Gmail Facebook X LinkedIn More