Iterative Thresholding for Sparse Approximations
Iterative Thresholding for Sparse Approximations
复制标题
DOI：
10.1007/s00041-008-9035-z
复制
发表时间：
2008-12-01
影响因子：
1.2
通讯作者：
Davies, Mike E.
中科院分区：
文献类型：
--
作者：
Blumensath, Thomas;Davies, Mike E.
稀疏信号展开使用来自大量基本波形的少量元素来表示或近似信号。寻找最优稀疏展开通常是NP难的，经常需要使用非最优策略，如匹配追踪、正交匹配追踪、基追踪和基追踪去噪。这些方法在实际情况中表现出良好的性能，但它们不适用于L(0)惩罚成本函数，而后者往往是问题的核心。在本文中，我们研究了两种最小化感兴趣的代价函数的迭代算法。此外，这些策略的每一次迭代都具有类似于匹配追踪迭代的计算复杂性，使得这些方法适用于许多现实世界的问题。然而，优化问题是非凸的，策略只能保证找到局部解，所以良好的初始化变得至关重要。我们在这里研究两种方法。第一种方法使用所提出的算法来改进用其他方法找到的解，以取代通常使用的共轭梯度求解器。第二种策略对算法进行了调整，我们在一个例子中表明，这种调整可以在保持匹配追踪算法的计算复杂性的同时，获得介于匹配追踪算法和正交匹配追踪算法之间的结果。
Sparse signal expansions represent or approximate a signal using a small number of elements from a large collection of elementary waveforms. Finding the optimal sparse expansion is known to be NP hard in general and non-optimal strategies such as Matching Pursuit, Orthogonal Matching Pursuit, Basis Pursuit and Basis Pursuit De-noising are often called upon. These methods show good performance in practical situations, however, they do not operate on the l(0) penalised cost functions that are often at the heart of the problem. In this paper we study two iterative algorithms that are minimising the cost functions of interest. Furthermore, each iteration of these strategies has computational complexity similar to a Matching Pursuit iteration, making the methods applicable to many real world problems. However, the optimisation problem is non-convex and the strategies are only guaranteed to find local solutions, so good initialisation becomes paramount. We here study two approaches. The first approach uses the proposed algorithms to refine the solutions found with other methods, replacing the typically used conjugate gradient solver. The second strategy adapts the algorithms and we show on one example that this adaptation can be used to achieve results that lie between those obtained with Matching Pursuit and those found with Orthogonal Matching Pursuit, while retaining the computational complexity of the Matching Pursuit algorithm.