Optimization Online


A First-Order Smoothed Penalty Method for Compressed Sensing

Necdet Serhat Aybat (nsa2106***at***columbia.edu)
Garud Iyengar (garud***at***ieor.columbia.edu)

Abstract: We propose a first-order smoothed penalty algorithm (SPA) to solve the sparse recovery problem min{||x||_1 : Ax=b}. SPA is efficient as long as the matrix-vector 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 sub-problems, and each sub-problem is solved using Nesterov's optimal algorithm for simple sets [13, 14]. We show that the SPA iterates x_k are eps-feasible, i.e. ||Ax_k-b||_2<= eps and eps-optimal, i.e. | ||x_k||_1-||x*||_1 | <= eps after O(eps^(-3/2)) iterations. We also bound the sub-optimality, | ||x_k||_1-||x*||_1 | for any iterate x_k; thus, the user can stop the algorithm at any iteration k with guarantee on the sub-optimality. 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 : ||Ax-b||_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
Entry Accepted: 06/23/2009
Entry Last Modified: 03/24/2010

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