**SpaRSA**

**Spa****rse Reconstruction by Separable
Approximation**

Computer Sciences Department,

University of Wisconsin-Madison

Madison, WI, USA

Electrical and Computer Engineering Department

University of Wisconsin-Madison

Madison, WI, USA

Instituto de Telecomunicações

Instituto Superior Técnico

Lisboa, PORTUGAL

Download the paper here.

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

ABSTRACT

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.