Perturbation Analysis of Orthogonal Matching Pursuit

Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signalxthroughΦandy= Φ x+ b, whereΦis a matrix with more columns than rows andbdenotes the measurement noise. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means bothyandΦare perturbed. Though the exact recovery of an almost sparse signalxis no longer feasible, the main contribution reveals that the support set of the bestk-term approximation ofxcan be recovered under reasonable conditions. The error bound betweenxand the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the bestk-term approximation ofxare rather tight. Whenxis strong-decaying, it is proved that the sufficient conditions for support recovery of the bestk-term approximation ofxcan be relaxed, and the support can even be recovered in the order of the entries' magnitude. Our results are also compared in detail with some related previous ones.