Optimization Online


A Fast Algorithm for Sparse Reconstruction based on Shrinkage, Subspace Optimization and Continuation

Zaiwen Wen(zw2109***at***columbia.edu)
Wotao Yin(wotao.yin***at***rice.edu)
Donald Goldfarb(godfarb***at***columbia.edu)
Yin Zhang(yzhang***at***rice.edu)

Abstract: We propose a fast algorithm for solving the l1-regularized least squares problem for recovering sparse solutions to an undetermined system of linear equations Ax = b. The algorithm is divided into two stages that are performed repeatedly. In the first stage a first-order iterative method called "shrinkage" yields an estimate of the subset of components of x likely to be nonzero in an optimal solution. Restricting the decision variables x to this subset and fixing their signs at their current values reduces the l1-norm to a linear function of x. The resulting subspace problem, which involves the minimization of a smaller and smooth quadratic function, is solved in the second phase. Our code FPC_AS embeds this basic two-stage algorithm in a continuation (homotopy) approach by assigning a decreasing sequence of values to mu. This code exhibits state-of-the-art performance both in terms of its speed and its ability to recover sparse signals. It can even recover signals that are not as sparse as required by current compressive sensing theory.

Keywords: l1-minimization, basis pursuit, compressive sensing, subspace optimization, active set, continuation, shrinkage

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Rice University CAAM Technical Report TR09-01

Download: [PDF]

Entry Submitted: 03/11/2009
Entry Accepted: 03/12/2009
Entry Last Modified: 03/11/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society