Optimization Online


NESTA: A Fast and Accurate First-order Method for Sparse Recovery

Stephen Becker(srbecker***at***acm.caltech.edu)
Jerome Bobin(bobin***at***acm.caltech.edu)
Emmanuel Candes(emmanuel***at***acm.caltech.edu)

Abstract: Accurate signal recovery or image reconstruction from indirect and possibly under- sampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel fi rst-order methods in convex optimization, most notably Nesterov's smoothing technique, this paper introduces a fast and accurate algorithm for solving common recovery problems in signal processing. In the spirit of Nesterov's work, one of the key ideas of this algorithm is a subtle averaging of sequences of iterates, which has been shown to improve the convergence properties of standard gradient-descent algorithms. This paper demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as 1) it is computationally efficient, 2) it is accurate and returns solutions with several correct digits, 3) it is flexible and amenable to many kinds of reconstruction problems, and 4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization, and convex programs seeking to minimize the l1 norm of Wx under constraints, in which W is not diagonal.

Keywords: Nesterov's method, smooth approximations of nonsmooth functions, l1 minimization, duality in convex optimization, continuation methods, compressed sensing, total-variation minimization

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Applications -- Science and Engineering (Biomedical Applications )

Citation: California Institute of Technology, April 2009

Download: [PDF]

Entry Submitted: 04/24/2009
Entry Accepted: 04/24/2009
Entry Last Modified: 04/24/2009

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