Sparse Reconstruction by Separable Approximation
Sparse Reconstruction by Separable Approximation
复制标题
DOI：
10.1109/tsp.2009.2016892
复制
发表时间：
2009-07-01
影响因子：
5.4
通讯作者：
Figueiredo, Mario A. T.
中科院分区：
文献类型：
--
作者：
Wright, Stephen J.;Nowak, Robert D.;Figueiredo, Mario A. T.
寻找大型欠定线性方程组的稀疏近似解是信号/图像处理和统计学中的一个常见问题。基追踪，最小绝对收缩和选择算子（LASSO），基于小波的反卷积和重建，以及压缩传感（CS）是一些众所周知的领域，其中出现了这种类型的问题。一种标准方法是最小化目标函数，该目标函数包括添加到稀疏诱导（通常为l（1））正则化器的二次（l（2））误差项。我们提出了一个算法框架，更一般的问题，最小化光滑凸函数和非光滑，可能非凸正则化的总和。我们提出了迭代方法，其中每一步都是通过求解一个涉及二次项的对角Hessian（即，可分离的未知数）加上原来的稀疏诱导正则化;我们的方法是适合的情况下，这个子问题可以更快地解决比原来的问题。在适当的条件下（即正则化子的凸性），我们证明了所提出的迭代算法收敛到目标函数的最小值。除了解决标准的l（2）- l（1）情况，我们的框架还为其他正则化子（如l（无穷大）范数和群可分正则化子）提供了有效的解决方案。它还立即推广到数据是复杂的而不是真实的的情况。CS问题的实验表明，我们的方法是具有竞争力的最快的已知方法的标准l（2）- l（1）的问题，以及与其他可分离的正则化项的问题是有效的。
Finding sparse approximate solutions to large underdetermined linear systems of equations is a common problem in signal/image processing and statistics. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution and reconstruction, and compressed sensing (CS) are a few well-known areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (l(2)) error term added to a sparsity-inducing (usually l(1)) regularizater. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex regularizer. We propose iterative methods in which each step is obtained by solving an optimization subproblem involving a quadratic term with diagonal Hessian (i.e., separable in the unknowns) plus the original sparsity-inducing regularizer; our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. Under mild conditions (namely convexity of the regularizer), we prove convergence of the proposed iterative algorithm to a minimum of the objective function. In addition to solving the standard l(2) - l(1) case, our framework yields efficient solution techniques for other regularizers, such as an l(infinity) norm and group-separable regularizers. It also generalizes immediately to the case in which the data is complex rather than real. Experiments with CS problems show that our approach is competitive with the fastest known methods for the standard l(2) - l(1) problem, as well as being efficient on problems with other separable regularization terms.