On the efficiency of the Orthogonal Matching Pursuit in compressed sensing

The paper shows that if a matrix Φ has the restricted isometry property (RIP) of order [CK1.2] with isometry constant δ=cK-0.2 and if its coherence is less than 1/(20K0.8), then the Orthogonal Matching Pursuit (the Orthogonal Greedy Algorithm) is capable to exactly recover an arbitrary K-sparse signal from the compressed sensing y=Φx in at most [CK1.2] iterations. As a result, an arbitrary K-sparse signal can be recovered by the Orthogonal Matching Pursuit from M=O(K1.6 log N) measurements. Bibliography: 23 titles.