Sparse Reconstruction by Separable Approximation
Sparse Reconstruction by Separable Approximation
复制标题
DOI：
10.1109/icassp.2008.4518374
复制
发表时间：
2008-05
影响因子：
5.4
通讯作者：
Stephen J. Wright;R. Nowak;Mário A. T. Figueiredo
中科院分区：
文献类型：
--
作者：
Stephen J. Wright;R. Nowak;Mário A. T. Figueiredo
寻找大型欠定线性方程组的稀疏近似解是信号/图像处理和统计学中的一个常见问题。基追踪，最小绝对收缩和选择算子（LASSO），基于小波的反卷积和重建，以及压缩传感（CS）是一些众所周知的领域，其中出现了这种类型的问题。一个标准的方法是最小化一个目标函数，该目标函数包括一个二次（lscr 2）误差项，该误差项添加到一个稀疏诱导（通常为lscr 1）正则化器。我们提出了一个算法框架，更一般的问题，最小化光滑凸函数和非光滑，可能非凸正则化的总和。我们提出了迭代方法，其中每一步都是通过求解一个涉及二次项的对角Hessian（即，可分离的未知数）加上原来的稀疏诱导正则化;我们的方法是适合的情况下，这个子问题可以更快地解决比原来的问题。在适当的条件下（即正则化子的凸性），我们证明了所提出的迭代算法收敛到目标函数的最小值。除了解决标准的正则化子2-正则化子1的情况下，我们的框架产生了有效的解决方案技术，其他正则化子，如一个正则化子范数和组可分离的正则化。它还立即推广到数据是复杂的而不是真实的的情况。CS问题的实验表明，我们的方法是最快的已知的方法的标准的lx 2-lx 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 (lscr 2) error term added to a sparsity-inducing (usually lscr1) 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 lscr2-lscr1 case, our framework yields efficient solution techniques for other regularizers, such as an lscrinfin 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 lscr2-lscr1 problem, as well as being efficient on problems with other separable regularization terms.