A First-Order Smoothed Penalty Method for Compressed Sensing

Necdet Serhat Aybat (nsa2106columbia.edu)
Garud Iyengar (garudieor.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