An Improved Analysis for Support Recovery With Orthogonal Matching Pursuit Under General Perturbations

作者：Li, Haifeng^*; Liu, Guoqi

来源：IEEE Access, 2018, 6: 18856-18867.

DOI：10.1109/ACCESS.2018.2820804

• Compressed sensing
• perturbation
• restricted isometry property
• near orthogonal property

Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for recovering the support of a sparse signal x from the underdetermined model y = Ax. In practice, we should analyze the performance of OMP under general perturbations, which means that both y and A are perturbed. In this paper, under general perturbations, we present necessary and suffcient conditions for the exact support recovery with the OMP. We also discuss the performance of OMP for recovering alpha strongly decaying sparse signals. Typically, in the noise-free case, we show that the upper bound of our sufffcient condition is unrelated with K and is a sharp bound. Furthermore, we establish suffcient conditions for the recovery of OMP, which can guarantee that the recovery is in the order of the signal entries' magnitude.

• 出版日期2018
• 单位河南师范大学