On efficiency of Orthogonal Matching Pursuit

Abstract

We show that if a matrix $\Phi$ satisfies the RIP of order $[C{K}^{1.2}]$ with isometry constant $\dt = c K^{-0.2}$ and has coherence less than $1/(20K^{0.8})$, then Orthogonal Matching Pursuit (OMP) will recover $K$-sparse signal $x$ from $y=\Phi x$ in at most $[C{K}^{1.2}]$ iterations. This result implies that $K$-sparse signal can be recovered via OMP by $M=O(K^{1.6}\log N)$ measurements.