Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

When does OMP achieve exact recovery with continuous dictionaries?

Clément Elvira 1 Rémi Gribonval 1 Charles Soussen 2 Cédric 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 fora greedy algorithm, Orthogonal Matching Pursuit (OMP), in the context ofcontinuous parametric dictionaries. Here, the continuous setting means thatthe dictionary is made up of an innite uncountable number of atoms. In thiswork, we rely on the Hilbert structure of the observation space to express ourrecovery results as a property of the kernel dened by the inner product betweentwo atoms. Using a continuous extension of Tropp's Exact Recovery Condition,we identify key assumptions allowing to analyze OMP in the continuous setting.Under these assumptions, OMP unambiguously identies in exactly k steps theatom parameters from any observed linear combination of k atoms. Theseparameters play the role of the so-called support of a sparse representation intraditional sparse recovery. In our paper, any kernel and set of parameters thatsatisfy these conditions are said to be admissible.In the one-dimensional setting, we exhibit a family of kernels relying oncompletely monotone functions for which admissibility holds for any set of atomparameters. For higher dimensional parameter spaces, the analysis turns outto be more subtle. An additional assumption, so-called axis admissibility, isimposed to ensure a form of delayed recovery (in at most kD steps, where D isthe dimension of the parameter space). Furthermore, guarantees for recoveryin exactly k steps are derived under an additional algebraic condition involvinga nite subset of atoms (built as an extension of the set of atoms to berecovered). We show that the latter technical conditions simplify in the caseof Laplacian kernels, allowing us to derive simple conditions for k-step exactrecovery, and to carry out a coherence-based analysis in terms of a minimumseparation assumption between the atoms to be recovered.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-02099464
Contributeur : Clément Elvira <>
Soumis le : dimanche 21 juin 2020 - 20:51:47
Dernière modification le : jeudi 1 avril 2021 - 03:35:38

Fichier

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

Identifiants

Citation

Clément Elvira, Rémi Gribonval, Charles Soussen, Cédric Herzet. When does OMP achieve exact recovery with continuous dictionaries?. Applied and Computational Harmonic Analysis, Elsevier, 2021, 51, pp.39. ⟨10.1016/j.acha.2020.12.002⟩. ⟨hal-02099464v4⟩

Partager

Métriques

Consultations de la notice

228

Téléchargements de fichiers

634