Average Performance of Orthogonal Matching Pursuit (OMP) for Sparse Approximation

We present a theoretical analysis of the average performance of orthogonal matching pursuit (OMP) for sparse approximation. For signals that are generated from a dictionary with K atoms and coherence μ and coefficients corresponding to a geometric sequence with parameter α <; 1, we show that OMP is successful with high probability as long as the sparsity level S scales as Sμ
²
log K ≲ 1 - α. 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.