On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
复制标题
DOI：
10.1109/tsp.2012.2203124
复制
发表时间：
2012-09-01
影响因子：
5.4
通讯作者：
Shim, Byonghyo
中科院分区：
文献类型：
--
作者：
Wang, Jian;Shim, Byonghyo
正交匹配追踪（OMP）是一种贪婪搜索算法，被广泛用于压缩感知稀疏信号的恢复。在此通信中，我们证明了如果感知矩阵Phi的等距常数δ (K+1)满足δ (K+1) < 1/根K+1，则OMP算法可以从压缩测量y = Phi x中完美地恢复K-稀疏信号。我们的界比Davenport和Wakin最近的结果有了很大的改进，并且缩小了恢复界和基本极限之间的差距，超过该极限OMP不能保证完美恢复。
Orthogonal matching pursuit (OMP) is a greedy search algorithm popularly being used for the recovery of compressive sensed sparse signals. In this correspondence, we show that if the isometry constant delta(K+1) of the sensing matrix Phi satisfies delta(K+1) < 1/root K+1 then the OMP algorithm can perfectly recover K-sparse signals from the compressed measurements y = Phi x. Our bound offers a substantial improvement over the recent result of Davenport and Wakin and also closes gap between the recovery bound and fundamental limit over which the perfect recovery of the OMP cannot be guaranteed.