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.
Before comparison, it is worth mentioning that there are fundamental differences between the above two conclusions. First, conditions that guarantee the support set recovery of the best @math -term approximation of @math is the main concern in Corollary 2, and based on the successful support recovery, an upper bound on the error is estimated. In the reference, however, the @math error is directly given regardless of the support recovery. Sometimes, recovering the support set other than the more accurate estimation is a fundamental concern. Second, compared with @cite_6 , this paper has an apparent limitation: the non-sparse signal considered in this paper is almost sparse, whereas the one in @cite_6 is arbitrary.
@cite_6
2057380028
In this paper we investigate the efficiency of the Orthogonal Matching Pursuit algorithm (OMP) for random dictionaries. We concentrate on dictionaries satisfying the Restricted Isometry Property. We also introduce a stronger Homogenous Restricted Isometry Property which we show is satisfied with overwhelming probability for random dictionaries used in compressed sensing. For these dictionaries we obtain upper estimates for the error of approximation by OMP in terms of the error of the best n-term approximation (Lebesgue-type inequalities). We also present and discuss some open problems about OMP. This is a development of recent results obtained by D.L. Donoho, M. Elad and V.N. Temlyakov.