Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance
Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance
复制标题
DOI：
10.1109/jstsp.2010.2042411
复制
发表时间：
2010-04-01
影响因子：
7.5
通讯作者：
Davies, Mike E.
中科院分区：
文献类型：
--
作者：
Blumensath, Thomas;Davies, Mike E.
稀疏信号模型用于许多信号处理应用中。在这些模型中估算最稀少系数向量的任务是一个组合问题和有效的，通常必须使用次优策略。幸运的是，在模型上的某些条件下，可以证明几种算法可以有效计算近乎最佳的解决方案。在本文中，我们研究了其中一种方法，即所谓的迭代硬阈值算法。尽管这种方法在某些理论属性中都具有强大的理论性能保证，但经验研究表明，每当条件失败时，算法的性能就会显着降低。此外，在这种制度中，该算法通常也无法收敛。由于我们在这里对将方法应用于现实世界问题感兴趣，而在现实世界中的问题一般不知道，无论是否满足理论条件政权。通过这种修改，经验证据表明，该算法比许多其他最先进的方法都快，同时显示出相似的性能。此外，修改后的算法保留了与原始算法相似的理论性能保证。
Sparse signal models are used in many signal processing applications. The task of estimating the sparsest coefficient vector in these models is a combinatorial problem and efficient, often suboptimal strategies have to be used. Fortunately, under certain conditions on the model, several algorithms could be shown to efficiently calculate near-optimal solutions. In this paper, we study one of these methods, the so-called Iterative Hard Thresholding algorithm. While this method has strong theoretical performance guarantees whenever certain theoretical properties hold, empirical studies show that the algorithm's performance degrades significantly, whenever the conditions fail. What is more, in this regime, the algorithm also often fails to converge. As we are here interested in the application of the method to real world problems, in which it is not known in general, whether the theoretical conditions are satisfied or not, we suggest a simple modification that guarantees the convergence of the method, even in this regime. With this modification, empirical evidence suggests that the algorithm is faster than many other state-of-the-art approaches while showing similar performance. What is more, the modified algorithm retains theoretical performance guarantees similar to the original algorithm.