SIGNAL RECOVERY FROM PARTIAL INFORMATION VIA ORTHOGONAL MATCHING PURSUIT
SIGNAL RECOVERY FROM PARTIAL INFORMATION VIA ORTHOGONAL MATCHING PURSUIT
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. Tropp;A. Gilbert
中科院分区：
文献类型：
--
作者：
J. Tropp;A. Gilbert
本文从理论上和经验上证明了一种称为正交匹配追踪（OMP）的贪婪算法可以可靠地恢复一个在d维中具有m个非零条目的信号，给定该信号的O（m ln d）个随机线性测量。这比以前需要O(m)测量的OMP结果有了巨大的改进。OMP的新结果与另一种称为Basis Pursuit （BP）的算法的最新结果具有可比性。OMP算法更快，更容易实现，这使得它成为BP信号恢复问题的一个有吸引力的替代方案。
This article demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(m ln d) random linear measurements of that signal. This is a massive improvement over previous results for OMP, which require O(m) measurements. The new results for OMP are comparable with recent results for another algorithm called Basis Pursuit (BP). The OMP algorithm is much faster and much easier to implement, which makes it an attractive alternative to BP for signal recovery problems.