SpaRSA
Sparse 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.