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 through Φ and y = Φx + b, where is a matrix with more columns than rows and 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 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.
In @cite_3 , it is proved that for @math process, the support of a @math -sparse signal @math can be recovered, provided that @math and @math . By comparison, it is shown that Corollary @math is at least as good as this conclusion.
@cite_3
2028878677
Orthogonal matching pursuit (OMP) is a commonly used algorithm for recovery sparse signals due to its low complexity and simple implementation. We analyze the convergence property of OMP based on the restricted isometry property (RIP), and show that the OMP algorithm can exactly recover an arbitrary K-sparse signal using K steps provided that the sampling matrix Φ satisfies the RIP with parameter . In addition, we also give the convergence analysis of OMP for the case of inaccurate measurements. Moreover, a variant of OMP, referred to as multi-candidate OMP (MOMP) algorithm, is proposed to recover sparse signals, which can further reduce the computational complexity of OMP. The key point of MOMP is that at each step it selects multi-candidates adding to the optimal atom set, whilst OMP only selects one atom. We also present the convergence analysis of MOMP using the RIP. Finally, we testify the performance of the proposed algorithm using several numerical experiments.