Signal Recovery from Random Measurements via Extended Orthogonal Matching Pursuit
Signal Recovery from Random Measurements via Extended Orthogonal Matching Pursuit
复制标题
DOI：
10.1109/tsp.2015.2413384
复制
发表时间：
2015-05-15
影响因子：
5.4
通讯作者：
Makur, Anamitra
中科院分区：
文献类型：
--
作者：
Sahoo, Sujit Kumar;Makur, Anamitra
正交匹配追踪（OMP）和基追踪（BP）是压缩感知中两种著名的恢复算法。为了以高概率恢复d维m稀疏信号，OMP需要O（m ln d）个测量，而BP只需要O（m ln d/m）个测量。相反，OMP是一个实际上更有吸引力的算法，由于其上级的执行速度。在这项工作中，我们提出了一个方案，使OMP所需的测量次数更接近BP。我们将此方案称为OMP alpha，它通过选择alpha的值为[0，1]的元素来运行OMP（m + [am]）迭代而不是m迭代。它示出OMP α保证了高概率的信号恢复与O（m ln d/[am] + 1）的测量数。与BP不同，OMP alpha的另一个局限性是它需要了解。为了克服这一限制，我们扩展了OMP alpha的概念，以说明另一种称为OMP infinity的恢复方案，该方案运行OMP直到信号残差消失。结果表明，OMP无穷大可以实现接近l（0）-范数的恢复，而无需任何知识的BP。
Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover a d-dimensional m-sparse signal with high probability, OMP needs O(m ln d) number of measurements, whereas BP needs only O(m ln d/m) number of measurements. In contrary, OMP is a practically more appealing algorithm due to its superior execution speed. In this piece of work, we have proposed a scheme that brings the required number of measurements for OMP closer to BP. We have termed this scheme as OMP alpha, which runs OMP for (m + [am])-iterations instead of m-iterations, by choosing a value of alpha is an element of[0, 1]. It is shown that OMP alpha guarantees a high probability signal recovery with O(m ln d/[am] + 1) number of measurements. Another limitation of OMP alpha unlike BP is that it requires the knowledge of. In order to overcome this limitation, we have extended the idea of OMP alpha to illustrate another recovery scheme called OMP infinity, which runs OMP until the signal residue vanishes. It is shown that OMP infinity can achieve a close to l(0)-norm recovery without any knowledge of like BP.