Fast OMP for Exact Recovery and Sparse Approximation
Huiyuan Yu Jia He Maggie Cheng
Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal
recovery and approximation. However OMP suffers computational issue when the
signal has large number of non-zeros. This paper advances OMP in two fronts: it
offers a fast algorithm for the orthogonal projection of the input signal at
each iteration, and a new selection criterion for making the greedy choice,
which reduces the number of iterations it takes to recover the signal. The
proposed modifications to OMP directly reduce the computational complexity.
Experiment results show significant improvement over the classical OMP in
computation time. The paper also provided a sufficient condition for exact
recovery under the new greedy choice criterion. For general signals that may
not have sparse representations, the paper provides a bound for the
approximation error. The approximation error is at the same order as OMP but is
obtained within fewer iterations and less time.