Sparse Reconstruction by Separable Approximation

Stephen J. Wright(swrightcs.wisc.edu)
Robert Nowak(nowakece.wisc.edu)
Mario A. T. Figueiredo(mario.a.t.figueiredogmail.com)

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), 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 ($\ell_2$) error term added to a sparsity-inducing (usually $\ell_1$) 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 standard $\ell_2-\ell_1$ case, our approach handles other problems, {\it e.g.}, $\ell_p$ regularizers with $p\neq 1$, or group-separable (GS) regularizers. Experiments with CS problems show that our approach provides state-of-the-art speed for the standard $\ell_2-\ell_1$ problem, and is also efficient on problems with GS regularizers.

Keywords: sparse approximation, compressed sensing, optimization, reconstruction

Category 1: Applications -- Science and Engineering (Other )

Category 2: Convex and Nonsmooth Optimization

Citation: Submitted, October, 2007.

Download: [PDF]

Entry Submitted: 10/25/2007
Entry Accepted: 10/25/2007
Entry Last Modified: 10/25/2007

Modify/Update this entry