Perturbation Analysis of Orthogonal Matching Pursuit
Perturbation Analysis of Orthogonal Matching Pursuit
复制标题
DOI：
10.1109/tsp.2012.2222377
复制
发表时间：
2011-06
影响因子：
5.4
通讯作者：
Jie Ding;Laming Chen;Yuantao Gu
中科院分区：
文献类型：
--
作者：
Jie Ding;Laming Chen;Yuantao Gu
正交匹配追踪（OMP）算法是一种典型的稀疏近似贪婪追踪算法.以前的OMP研究考虑了通过Φ和y = Φx + B恢复稀疏信号，其中是列数多于行数的矩阵，表示测量噪声。本文基于约束等距性（RIP），分析了OMP算法在一般扰动下的性能。虽然几乎稀疏信号x的精确恢复不再可行，但主要贡献揭示了x的最佳k项近似的支持集可以在合理的条件下恢复。最后，给出了最大均方误差估计与x之间的误差界.通过构造一个例子，证明了最佳k项逼近的支持恢复的充分条件是相当严格的。当x是强衰减的时，证明了x的最佳k项逼近的支持度恢复的充分条件可以放宽，甚至支持度可以按元素的数量级恢复.我们的结果也与一些相关的以前的详细比较。
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.