Average performance of Orthogonal Matching Pursuit (OMP) for sparse approximation

Abstract

We present a theoretical analysis of the average performance of OMP for sparse approximation. For signals that are generated from a dictionary with $K$ atoms and coherence $\mu$ and coefficients corresponding to a geometric sequence with parameter $\alpha <1$, we show that OMP is successful with high probability as long as the sparsity level $S$ scales as $S{\mu }^2\log K\lesssim 1-\alpha$. This improves by an order of magnitude over worst case results and shows that OMP and its famous competitor Basis Pursuit outperform each other depending on the setting.

12 pages, 2 figures, extended and corrected version of the published version