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.

arXiv comment12 pages, 2 figures, extended and corrected version of the published version

References in corpus (1)

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

Cited by in corpus (1)

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