The efficiency of using Orthogonal Matching Pursuit in compressed sensing

Abstract

We investigate the efficiency of compressed sensing by using Orthogonal Matching Pursuit. We prove that if the sampling Matrix Φ has coherence less than 1/20K^0.8 and satisfies the Restricted Isometry Property (RIP) of order [CK^1.2] with constant δ =cK^-0.2, then every K-sparse signal x can be recovered from measure values y=Φ x via Orthogonal Matching Pursuit in at most optimal approximation on the first [CK^1.2] iterations.