Skip to Main content Skip to Navigation
Journal articles

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
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.
Complete list of metadatas

Cited literature [74 references]  Display  Hide  Download
Contributor : Clément Elvira <>
Submitted on : Sunday, June 21, 2020 - 8:51:47 PM
Last modification on : Monday, January 18, 2021 - 11:04:39 AM


Files produced by the author(s)



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⟩



Record views


Files downloads