Signal recovery from random measurements via orthogonal matching pursuit
Signal recovery from random measurements via orthogonal matching pursuit
复制标题
DOI：
10.1109/tit.2007.909108
复制
发表时间：
2007-12-01
影响因子：
2.5
通讯作者：
Gilbert, Anna C.
中科院分区：
文献类型：
--
作者：
Tropp, Joel A.;Gilbert, Anna C.
本文从理论和经验上证明了一种贪婪的正交匹配追踪算法（OMP）可以可靠地恢复一个在d维中具有m个非零项的信号，该信号具有O（m 1n d）个随机线性测量值。这比以前需要O（m(2)）次测量的结果有了很大的改进。OMP的新结果与另一种称为基础追踪（BP）的方法的最新结果可比较。在某些情况下，OMP算法更快，更容易实现，因此在信号恢复问题上是BP的一个有吸引力的替代方案。
This paper 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 1n d) random linear measurements of that signal. This is a massive improvement over previous results, which require O(m(2)) measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.