Talk by Clément Elvira (Inria Rennes) : Greedy algorithms and continuous dictionaries : is exact recovery still possible?
Over the last decade, sparse representations have sparked a surge of interest in the signal processing community. A question of broad interest is the identification of the ``sparsest" representation of an input signal over a parametric dictionary. Currently, performance guarantees for greedy methods - an ubiquitous family of algorithms - are typically carried out in the discrete setting associated to a grid of atom parameters, and based on, e.g., the coherence of the considered discretized dictionary. However, such analyses fail to be conclusive for grid-based approaches when the discretization step tends to zero, as the coherence goes to one. In this work, we present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous dictionaries where the dictionary is made up of an infinite uncountable number of atoms. We capitalize on these results to build up a family of dictionaries permitting exact recovery, and revisit some well known analyses such as coherence and minimum separation conditions.
Greedy algorithms and continuous dictionaries : is exact recovery still possible?
Over the last decade, sparse representations have sparked a surge of interest in the signal processing community. A question of broad interest is the identification of the ``sparsest" representation of an input signal over a parametric dictionary. Currently, performance guarantees for greedy methods - an ubiquitous family of algorithms - are typically carried out in the discrete setting associated to a grid of atom parameters, and based on, e.g., the coherence of the considered discretized dictionary. However, such analyses fail to be conclusive for grid-based approaches when the discretization step tends to zero, as the coherence goes to one. In this work, we present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous dictionaries where the dictionary is made up of an infinite uncountable number of atoms. We capitalize on these results to build up a family of dictionaries permitting exact recovery, and revisit some well known analyses such as coherence and minimum separation conditions.
keywords: sparse representation, greedy algorithms, continuous dictionaries, uniform recovery.
keywords: sparse representation, greedy algorithms, continuous dictionaries, uniform recovery.
https://scholar.google.fr/citations?hl=fr&user=2LSEQYcAAAAJ&view_op=list_works&sortby=pubdate
Bio: Clément Elvira received his Eng. degree from Centrale Lille, France, and the M.Sc. degree in applied Mathematics from the university of Lille, both in September 2014.
After receiving his Ph.D. degree from Centrale Lille in 2017, he is pursuing a postdoctoral position at Inria Rennes, France, under the supervision of Cédric Herzet, Rémi Gribonval and Charles Soussen.
His research interests are centered around sparsity with a strong emphasized on Bayesian methods with applications to signal processing.
Bio: Clément Elvira received his Eng. degree from Centrale Lille, France, and the M.Sc. degree in applied Mathematics from the university of Lille, both in September 2014.
After receiving his Ph.D. degree from Centrale Lille in 2017, he is pursuing a postdoctoral position at Inria Rennes, France, under the supervision of Cédric Herzet, Rémi Gribonval and Charles Soussen.
His research interests are centered around sparsity with a strong emphasized on Bayesian methods with applications to signal processing.