Computer Science – Information Theory
Scientific paper
2011-06-17
Computer Science
Information Theory
11 pages
Scientific paper
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 $\bm x$ through $\bm \Phi$ and $\bm y=\bm \Phi \bm x$, where $\bm \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 $\bm y$ and $\bm \Phi$ are perturbed. Though exact recovery of an almost sparse signal $\bm x$ is no longer feasible, the main contribution reveals that the exact recovery of the locations of $k$ largest magnitude entries of $\bm x$ can be guaranteed under reasonable conditions. The error between $\bm x$ and solution of OMP is also estimated. It is also demonstrated that the sufficient condition is rather tight by constructing an example. When $\bm 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.
Chen Laming
Ding Jie
Gu Yuantao
No associations
LandOfFree
Perturbation Analysis of Orthogonal Matching Pursuit does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Perturbation Analysis of Orthogonal Matching Pursuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perturbation Analysis of Orthogonal Matching Pursuit will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-695385