Perturbation analysis of orthogonal matching pursuit

Jie Ding, Laming Chen, Yuantao Gu

Research output: Contribution to journalArticlepeer-review

57 Scopus citations


Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signal x through Φ and y=Φ x+b, where Φ is a matrix with more columns than rows and b denotes the measurement noise. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both y and Φ are perturbed. Though the exact recovery of an almost sparse signal x is no longer feasible, the main contribution reveals that the support set of the best k-term approximation of x can be recovered under reasonable conditions. The error bound between x and the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the best k -term approximation of x are rather tight. When x is strong-decaying, it is proved that the sufficient conditions for support recovery of the best k -term approximation of x can 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.

Original languageEnglish (US)
Article number6320703
Pages (from-to)398-410
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number2
StatePublished - 2013
Externally publishedYes


  • Compressed sensing (CS)
  • general perturbations
  • orthogonal matching pursuit (OMP)
  • restricted isometry property (RIP)
  • strong-decaying signals
  • support recovery


Dive into the research topics of 'Perturbation analysis of orthogonal matching pursuit'. Together they form a unique fingerprint.

Cite this