Optimization Online


PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

Ming Gu (mgu***at***math.berkeley.edu)
Lek-Heng Lim (lekheng***at***galton.uchicago.edu)
Cinna Julie Wu (cinnawu***at***math.berkeley.edu)

Abstract: In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient method proposed by Nesterov in 1983 that takes O(e^(-1/2)) iterations to come within e > 0 of the optimal value. We introduce a modification to Nesterov's method that regularly updates the prox-center in a provably optimal manner, resulting in the linear convergence of NESTA-LASSO under reasonable assumptions. Our work is motivated by recent advances in solving the basis pursuit denoising (BPDN) problem (i.e., approximating the minimum one-norm solution to an underdetermined least squares problem). Thus, one of our goals is to show that NESTA-LASSO can be used to solve the BPDN problem. We use NESTA-LASSO to solve a subproblem within the Pareto root-finding method used by the state-of-the-art BPDN solver SPGL1. The resulting algorithm is called PARNES, and we show, experimentally, that it is comparable to currently available solvers.

Keywords: BPDN, LASSO, compressed sensing, NESTA, SPGL1, PARNES, Pareto curve, accelerated proximal gradient methods

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: UC Berkeley preprint

Download: [PDF]

Entry Submitted: 11/02/2009
Entry Accepted: 11/02/2009
Entry Last Modified: 07/02/2011

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 Optimization Society