A low complexity Orthogonal Matching Pursuit for sparse signal approximation with shift-invariant dictionaries

Boris Mailhé, Rémi Gribonval, Frédéric Bimbot, Pierre Vandergheynst

Abstract

We propose a variant of orthogonal matching pursuit (OMP), called LoCOMP, for scalable sparse signal approximation. The algorithm is designed for shift-invariant signal dictionaries with localized atoms, such as time-frequency dictionaries, and achieves approximation performance comparable to OMP at a computational cost similar to matching pursuit. Numerical experiments with a large audio signal show that, compared to OMP and gradient pursuit, the proposed algorithm runs in over 500 less time while leaving the approximation error almost unchanged.
BibTeX
@inproceedings{mailhe2009low,
  author = {Boris Mailhé and Rémi Gribonval and Frédéric Bimbot and Pierre Vandergheynst},
  title = {{A low complexity Orthogonal Matching Pursuit for sparse signal approximation with shift-invariant dictionaries}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2009},
  doi = {10.1109/icassp.2009.4960366},
}
Figure