  


A FirstOrder Augmented Lagrangian Method for Compressed Sensing
Necdet Serhat Aybat (nsa2106columbia.edu) Abstract: We propose a Firstorder Augmented Lagrangian algorithm (FAL) for solving the basis pursuit problem. FAL computes a solution to this problem by inexactly solving a sequence of L1regularized least squares subproblems. These subproblems are solved using an infinite memory proximal gradient algorithm wherein each update reduces to "shrinkage" or constrained "shrinkage". We show that FAL converges to an optimal solution of the basis pursuit problem whenever the solution is unique, which is the case with very high probability for compressed sensing problems. We construct a parameter sequence such that the corresponding FAL iterates are epsilonfeasible and epsilonoptimal for all epsilon>0 within O(log(1/epsilon)) FAL iterations. Moreover, FAL requires at most O(1/epsilon) matrixvector multiplications of the form Ax or A^Ty to compute an epsilonfeasible, epsilonoptimal solution. We show that FAL can be easily extended to solve the basis pursuit denoising problem when there is a nontrivial level of noise on the measurements. We report the results of numerical experiments comparing FAL with the stateoftheart solvers for both noisy and noiseless compressed sensing problems. A striking property of FAL that we observed in the numerical experiments with randomly generated instances when there is no measurement noise was that FAL always correctly identifies the support of the target signal without any thresholding or postprocessing, for moderately small error tolerance values. Keywords: L1minimization, augmented Lagrangian method, first order method, compressed sensing, basis pursuit, sparse optimization, denoising Category 1: Convex and Nonsmooth Optimization Citation: IEOR Department, Columbia University, January 2010 Download: [PDF] Entry Submitted: 03/11/2010 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  