  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.
