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$, 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. 查看全文>>