The Exact Support Recovery of Sparse Signals With Noise via Orthogonal Matching Pursuit

Orthogonal matching pursuit (OMP) algorithm is a classical greedy algorithm in Compressed Sensing. In this letter, we study the performance of OMP in recovering the support of a sparse signal from a few noisy linear measurements. We consider two types of bounded noise and our analysis is in the framework of restricted isometry property (RIP). It is shown that under some conditions on RIP and the minimum magnitude of the nonzero elements of the sparse signal, OMP with proper stopping rules can recover the support of the signal exactly from the noisy observation. We also discuss the case of Gaussian noise. Our conditions on RIP improve some existing results.