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

By Stephen Becker, Jérôme Bobin, E.J. Candes. SIAM Journal of Imaging Sciences, 2009

1,227 citations recorded by the source corpus.

Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. This paper applies a smoothing technique and an accelerated first-order algorithm, both from Nesterov [Math. Program. Ser. A, 103 (2005), pp. 127-152], and 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 $\ell_1$ norm of $Wx$ under constraints, in which $W$ is not diagonal. The code is available online as a free package in the MATLAB language.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Radiology, Nuclear Medicine and Imaging

View Paper: https://www.semanticscholar.org/paper/a04e95660dd948525618325e0dbfcb12daf18648

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Radiology, Nuclear Medicine and Imaging

Citations in the corpus

A second-order method for strongly convex ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document}-re (2013, neutral): “To meet such a goal, the first-order methods community replaces the 1-norm with the so-called Huber penalty function ∑m i=1 φμ(xi ) [4], where φμ(xi ) = { 1 2 x2 i μ , if |xi | ≤ μ |xi | − 1 2μ, if |xi | ≥ μ i = 1, 2, .”
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems (2013, methodology): “Recently, this method has been used to improve the fastest known running time of some fundamental problems in computer science, such as compressive sensing [15], [16], undirected maximum flow [17], linear programming [18], [19].”
Alternating Direction Algorithms for 1-Problems in Compressive Sensing (2009, methodology): “In Section 4.4 we compare PADM and DADM with SPGL1 [23] — a spectral projected gradient algorithm for (1.4), and NESTA [4] — a fast and accurate fast ﬁrst-order algorithm based on Nesterov’s smoothing technique [35].”
Fast L1-Minimization Algorithms For Robust Face Recognition (2010, neutral): “Methods that are not discussed in this paper include GPSR [24], SpaRSA [25], SPGL1 [26], NESTA [15], SALSA [27], GLMNET [28], and Bregman iterative algorithm [29], just to name a few.”
Sparse Signal Recovery With Temporally Correlated Source Vectors Using Sparse Bayesian Learning (2011, methodology): “It is also inter esting to see that SBL algorithms could adopt the continuation strategies [56], [57], used in Lasso-type algorithms, to ad just the value ofλ for better recovery performance or faster speed.”
An optimal method for stochastic composite optimization (2011, methodology): “These ﬁrst-order meth-ods were further studied in, for example, [1,8,26,28,37,38,50], and successfully used in sparse covariance selection, rank reduction in multivariate linear regression and compressed sensing, etc. (see for example, [3,9,24,25]).”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, methodology): “Various methods have been proposed to solve (3) and (4) for fixed ρ and τ , including interior point method [30], coordinate minimization [121, 122], proximal gradient (with or without smoothing) [13, 14, 34], proximal minimization [155].”
A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration (2010, methodology): “Note that we do not compare to other more complicated implicit algorithms for solving the first subproblem, such as FPC [34] and methods based on Nestorov’s approach such as Fista [3], Nesta [4].”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, methodology): “Numerous solvers based on the active set [54, 36], interiorpoint continuation [21, 42] and projected gradient [25, 23, 39, 13, 9, 62, 3, 4] methods have been developed for solving the above formulations of the l1minimization problem.”
Templates for convex cone problems with applications to sparse signal recovery (2010, methodology): “1: The original objective f(x) = |x| (blue), our modification (red), and the Moreau-Yosida regularization [37] (green) used in [5, 53].”
Kernel Sparse Representation-Based Classifier (2012, background): “Namely (15) where is the transformation vector of , and is called the pseudo-transformation vector corresponding to the transformation vector.”
Sparse Methods for Direction-of-Arrival Estimation (2016, methodology): “Examples include `1-magic [50], interior-point method [51], conjugate gradient method [52], fixed-point continuation [53], Nesterov’s smoothing technique with continuation (NESTA) [54, 55], ONE-L1 algorithms [56], alternating direction method of multipliers (ADMM) [57, 58] and so on.”
A compressed sensing approach for partial differential equations with random input data (2012, methodology): “For a real-valued quantity f , the smoothed L(1)-norm is taken as, Becker et al. (2009):”