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

https://hal.inria.fr/hal-02099464
Contributor : Clément Elvira <>
Submitted on : Wednesday, April 17, 2019 - 4:31:26 PM
Last modification on : Monday, April 29, 2019 - 1:52:21 PM

File

acha.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

193

Files downloads

432