  


Sparse Reconstruction by Separable Approximation
Stephen J. Wright (swrightcs.wisc.edu) 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 wellknown areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (l_2) error term added to a sparsityinducing (usually $l_1$) regularizater. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex regularizer. 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 sparsityinducing regularizer; 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 $l_2l_1$ case, our framework yields efficient solution techniques for other regularizers, such as an $l_{infty}$ norm and groupseparable 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 $l_2l_1$ problem, as well as being efficient on problems with other separable regularization terms. Keywords: sparse approximation, compressed sensing, optimization, reconstruction Category 1: Applications  Science and Engineering (Other ) Category 2: Convex and Nonsmooth Optimization Citation: Journal version, to appear in IEEE Transactions on Signal Processing Download: [PDF] Entry Submitted: 10/25/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  