Fast OMP for Exact Recovery and Sparse Approximation

这篇论文提出了一种改进的正交匹配追踪（OMP）算法，用于稀疏信号恢复和逼近。然而，当信号具有大量非零元素时，OMP存在计算问题。该论文在两个方面推进了OMP的方法：提供了一种快速算法来进行每次迭代时输入信号的正交投影，以及一种新的选择准则来进行贪心选择，从而减少了恢复信号所需的迭代次数。所提出的改进直接降低了计算复杂度。实验结果显示，在计算时间上与经典OMP相比，有显着的改进。该论文还提供了一种新的贪心选择准则下的精确恢复的充分条件。对于可能没有稀疏表示的一般信号，该论文提供了逼近误差的界限。逼近误差与OMP的误差同阶，但是在较少的迭代次数和时间内得到。

优化OMP算法在大量非零信号情况下的计算问题，提高信号恢复速度。

通过改进OMP算法的正交投影和贪心选择标准，减少恢复信号所需迭代次数，从而减少计算复杂度。

论文提供了一个新的贪心选择标准，并给出了精确恢复的充分条件。对于一般信号，论文提供了一个近似误差的界限。实验结果表明，相比于经典OMP算法，改进的算法在计算时间上有显著提高。

近期的相关研究包括“Improved Orthogonal Matching Pursuit Algorithm for Compressed Sensing”和“Adaptive Orthogonal Matching Pursuit Algorithm for Sparse Signal Recovery”等。