Perturbation analysis of orthogonal matching pursuit

Jie Ding, Laming Chen, Yuantao Gu

Research output: Contribution to journalArticle

42 Scopus citations

Abstract

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
Volume61
Issue number2
DOIs
StatePublished - Jan 7 2013
Externally publishedYes

Keywords

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

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

  • Cite this