When does OMP achieve exact recovery with continuous dictionaries?

Overview & Synopsis

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.