论文标题
近似支持恢复的新界限
A New Bound on Approximate Support Recovery
论文作者
论文摘要
正交匹配追踪（OMP）是一种贪婪的算法，通常用于恢复稀疏信号。在本文中，我们研究了OMP的性能，以支持噪声下稀疏信号的恢复。我们的分析表明，在稀疏信号中非零条目的最低与平均值的比率和信号噪声比率的最小限制下，OMP算法可以以任意较小的错误率恢复信号的支持。我们的结果对[Wang，TSP 2015]的猜想提供了肯定的答案，即通过OMP的支持恢复的错误率不依赖信号的最大元素。
Orthogonal matching pursuit (OMP) is a greedy algorithm popularly being used for the recovery of sparse signals. In this paper, we study the performance of OMP for support recovery of sparse signal under noise. Our analysis shows that under mild constraint on the minimum-to-average ratio of nonzero entries in the sparse signal and the signal-to-noise ratio, the OMP algorithm can recover the support of signal with an error rate that can be arbitrarily small. Our result offers an affirmative answer to the conjecture of [Wang, TSP 2015] that the error rate of support recovery via OMP has no dependence on the maximum element of the signal.
