When does OMP achieve exact recovery with continuous dictionaries?

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 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 key assumptions allowing to analyze OMP in the continuous setting. Under these assumptions, OMP unambiguously identifies in exactly $k$ steps the atom parameters from any observed linear combination of $k$ atoms. These parameters play the role of the so-called support of a sparse representation in traditional sparse recovery. In our paper, any kernel and set of parameters that satisfy these conditions are said to be admissible. In the one-dimensional setting, we exhibit a family of kernels relying on completely monotone functions for which admissibility holds for any set of atom parameters. For higher dimensional parameter spaces, the analysis turns out to be more subtle. An additional assumption, so-called axis admissibility, is imposed to ensure a form of delayed recovery (in at most $k^D$ steps, where $D$ is the dimension of the parameter space). Furthermore, guarantees for recovery in exactly $k$ steps are derived under an additional algebraic condition involving a finite subset of atoms (built as an extension of the set of atoms to be recovered). We show that the latter technical conditions simplify in the case of Laplacian kernels, allowing us to derive simple conditions for $k$-step exact recovery, and to carry out a coherence-based analysis in terms of a minimum separation assumption between the atoms to be recovered.

arXiv comment52 pages, 2 figures

References in corpus (21)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• The Convex Geometry of Linear Inverse Problems
• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport
• Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares
• A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Improved RIP Analysis of Orthogonal Matching Pursuit
• Greed is Super: A Fast Algorithm for Super-Resolution
• A Low-Rank Approach to Off-The-Grid Sparse Deconvolution
• Learning Gaussian Mixtures with Arbitrary Separation
• Continuous dictionaries meet low-rank tensor approximations

Cited by in corpus (2)

• Off-the-grid learning of mixtures from a continuous dictionary
• On the Uniqueness of Solutions for the Basis Pursuit in the Continuum