Gradient pursuits
Gradient pursuits
复制标题
DOI：
10.1109/tsp.2007.916124
复制
发表时间：
2008-06-01
影响因子：
5.4
通讯作者：
Davies, Mike E.
中科院分区：
文献类型：
--
作者：
Blumensath, Thomas;Davies, Mike E.
稀疏信号近似已经成为信号处理中的一种基本工具，从源分离到信号捕获都有广泛的应用。越来越多的可能应用，特别是现在解决的不断增加的问题规模，导致了计算策略方面的新挑战，开发快速有效的算法变得至关重要。最近，人们已经开发出非常快速的算法来解决通常用于逼近稀疏逼近问题的凸优化问题；然而，也有研究表明，在某些情况下，贪婪策略，如正交匹配追踪，可以比凸优化方法具有更好的性能。本文对贪婪策略进行了改进，提出了计算要求更接近匹配追踪的近似正交匹配追踪的算法。分别讨论了基于梯度、基于共轭梯度和基于共轭梯度逼近的三种不同方向优化方案。结果表明，共轭梯度法给出了一种新的正交匹配追踪实现方法，而基于梯度的方法和近似共轭梯度法都能快速逼近正交匹配追踪，且近似共轭梯度法优于梯度法。
Sparse signal approximations have become a fundamental tool in signal processing with wide-ranging applications from source separation to signal acquisition. The ever-growing number of possible applications and, in particular, the ever-increasing problem sizes now addressed lead to new challenges in terms of computational strategies and the development of fast and efficient algorithms has become paramount. Recently, very fast algorithms have been developed to solve convex optimization problems that are often used to approximate the sparse approximation problem; however, it has also been shown, that in certain circumstances, greedy strategies, such as orthogonal matching pursuit, can have better performance than the convex methods. In this paper, improvements to greedy strategies are proposed and algorithms are developed that approximate orthogonal matching pursuit with computational requirements more akin to matching pursuit. Three different directional optimization schemes based on the gradient, the conjugate gradient, and an approximation to the conjugate gradient are discussed, respectively. It is shown that the conjugate gradient update leads to a novel implementation of orthogonal matching pursuit, while the gradient-based approach as well as the approximate conjugate gradient methods both lead to fast approximations to orthogonal matching pursuit, with the approximate conjugate gradient method being superior to the gradient method.