OMP and Continuous Dictionaries: Is k-step Recovery Possible?

Clément Elvira, Rémi Gribonval, Charles Soussen, Cédric HerzetICASSP 2019 · OpenReview

Abstract

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 parametric dictionaries, i.e., made up of an infinite uncountable number of atoms. We build up a family of dictionaries for which k-step recovery is possible with OMP for 1-dimensional parameters. In higher dimension, algebraic conditions become necessary and will lead us to revisit some well-known k-step discrete analyses. Finally, a toy-example illustrates the level of tightness of our sufficient conditions.
BibTeX
@inproceedings{elvira2019omp,
  author = {Clément Elvira and Rémi Gribonval and Charles Soussen and Cédric Herzet},
  title = {{OMP and Continuous Dictionaries: Is k-step Recovery Possible?}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=BWUihnSIUm},
}

Loading related content...

Figure