When does OMP achieve support recovery with continuous dictionaries?

Clément Elvira 1 Rémi Gribonval 1 Charles Soussen 2 Cedric Herzet 3
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA_D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
3 SIMSMART - SIMulation pARTiculaire de Modèles Stochastiques
IRMAR - Institut de Recherche Mathématique de Rennes, Inria Rennes – Bretagne Atlantique
Abstract : 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.
Liste complète des métadonnées

https://hal.inria.fr/hal-02099464
Contributeur : Clément Elvira <>
Soumis le : mercredi 17 avril 2019 - 16:31:26
Dernière modification le : lundi 29 avril 2019 - 13:52:21

Fichier

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

Identifiants

  • HAL Id : hal-02099464, version 3

Citation

Clément Elvira, Rémi Gribonval, Charles Soussen, Cedric Herzet. When does OMP achieve support recovery with continuous dictionaries?. 2019. ⟨hal-02099464v3⟩

Partager

Métriques

Consultations de la notice

148

Téléchargements de fichiers

429