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 language | English (US) |
|---|---|
| Article number | 6320703 |
| Pages (from-to) | 398-410 |
| Number of pages | 13 |
| Journal | IEEE Transactions on Signal Processing |
| Volume | 61 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2013 |
| Externally published | Yes |
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
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS