  


A FirstOrder Smoothed Penalty Method for Compressed Sensing
Necdet Serhat Aybat (nsa2106columbia.edu) Abstract: We propose a firstorder smoothed penalty algorithm (SPA) to solve the sparse recovery problem min{x_1 : Ax=b}. SPA is efficient as long as the matrixvector product Ax and A^Ty can be computed efficiently; in particular, A need not be an orthogonal projection matrix. SPA converges to the target signal by solving a sequence of penalized optimization subproblems, and each subproblem is solved using Nesterov's optimal algorithm for simple sets [13, 14]. We show that the SPA iterates x_k are epsfeasible, i.e. Ax_kb_2<= eps and epsoptimal, i.e.  x_k_1x*_1  <= eps after O(eps^(3/2)) iterations. We also bound the suboptimality,  x_k_1x*_1  for any iterate x_k; thus, the user can stop the algorithm at any iteration k with guarantee on the suboptimality. SPA is able to work with L_1, L_2 or L_infinity penalty on the infeasibility, and SPA can be easily extended to solve the relaxed recovery problem min{x_1 : Axb_2}. Keywords: Penalty method, First order method, Compressed sensing, Nesterov's method, Smooth approximations of nonsmooth functions, L1 minimization Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Category 2: Applications  Science and Engineering (Biomedical Applications ) Citation: IEOR Department, Columbia University, April 2009 Download: [PDF] Entry Submitted: 06/23/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  