Perturbation Analysis of Orthogonal Matching Pursuit

Abstract

Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have mainly considered the exact recovery of a sparse signal $\mathbf{x}$ through $\mathbf{\Phi }$ and $\mathbf{y}=\mathbf{\Phi }\mathbf{x}$, where $\mathbf{\Phi }$ is a matrix with more columns than rows. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both $\mathbf{y}$ and $\mathbf{\Phi }$ are perturbed. Though exact recovery of an almost sparse signal $\mathbf{x}$ is no longer feasible, the main contribution reveals that the exact recovery of the locations of $k$ largest magnitude entries of $\mathbf{x}$ can be guaranteed under reasonable conditions. The error between $\mathbf{x}$ and solution of OMP is also estimated. It is also demonstrated that the sufficient condition is rather tight by constructing an example. When $\mathbf{x}$ is strong-decaying, it is proved that the sufficient conditions can be relaxed, and the locations can even be recovered in the order of the entries' magnitude.

29 pages

References in corpus (3)

• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• On-Off Random Access Channels: A Compressed Sensing Framework
• Orthogonal Matching Pursuit: A Brownian Motion Analysis

Cited by in corpus (11)

• Model Selection Techniques -- An Overview
• Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data
• Nearly Optimal Bounds for Orthogonal Least Squares
• Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
• On the Performance Bound of Sparse Estimation with Sensing Matrix Perturbation
• Oracle-order Recovery Performance of Greedy Pursuits with Replacement against General Perturbations
• Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit
• Preconditioned Multiple Orthogonal Least Squares and Applications in Ghost Imaging via Sparsity Constraint
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix
• Noise Folding based on General Complete Perturbation in Compressed Sensing