  


A Fast Algorithm for Sparse Reconstruction based on Shrinkage, Subspace Optimization and Continuation
Zaiwen Wen(zw2109columbia.edu) Abstract: We propose a fast algorithm for solving the l1regularized 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 firstorder 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 l1norm 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 twostage algorithm in a continuation (homotopy) approach by assigning a decreasing sequence of values to mu. This code exhibits stateoftheart 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: l1minimization, 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 TR0901 Download: [PDF] Entry Submitted: 03/11/2009 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  