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

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.