Sparse reconstruction by separable approximation
Stephen J. Wright, Robert D. Nowak, Mário A. T. Figueiredo · IEEE International Conference on Acoustics Speech and Signal Processing · 2008
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 (pound2) error term added to a sparsity-inducing (usuallypound1) regularizer. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex, sparsity-inducing function. We propose iterative methods in which each step is an optimization subproblem involving a separable quadratic term (diagonal Hessian) plus the original sparsity-inducing term. Our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. In addition to solving the standardpound2-pound1case, our approach handles other problems, e.g.,poundpregularizers with p ne 1, or group-separable (GS) regularizers. Experiments with CS problems show that our approach provides state-of-the-art speed for the standardpound2-pound1problem, and is also efficient on problems with GS regularizers.
Cited by 189 works. doi:10.1109/icassp.2008.4518374
Authors
References
- Regression Shrinkage and Selection Via the Lasso
- Compressed sensing
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Nonlinear total variation based noise removal algorithms
- Maximum likelihood estimation from incomplete data via the EM algorithm
- Numerical optimization
- Atomic Decomposition by Basis Pursuit
- Least angle regression
- De-noising by soft-thresholding
- Matrix computations (3rd ed.)