Sparse Reconstruction by Separable Approximation


Stephen  J. Wright

Computer Sciences Department,

University of Wisconsin-Madison

Madison, WI, USA


Robert D. Nowak,

Electrical and Computer Engineering Department

University of Wisconsin-Madison

Madison, WI, USA


Mário Figueiredo,

Instituto de Telecomunicações                   

Instituto Superior Técnico                          



Download the paper here.                        


Download the MATLAB code here   (latest version, 2.0, January 20, 2009)



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), waveletbased 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  error term added to a sparsity-inducing (usually

the 1-norm) 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 regular izer. 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 r

egularizer; 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  L2-L1

case, our framework yields efficient solution techniques for other regularizers, such

as an 1-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 L2-L1 problem, as well as being efficient on problems with other

separable regularization terms.