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

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.

• Publication year

  2009

• Venue

  SIAM Journal of Imaging Sciences

• Publication date

  2009-04-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/090756855arXiv 0904.3367
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Geophysics

  2020cited by this paper
• Introductory Lectures on Convex Optimization - A Basic Course

  2014cited by this paper
• Compressed Sensing

  2012cited by this paper
• Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising

  2011cited by this paper
• A Fast Alternating Direction Method for TVL1-L2 Signal Reconstruction From Partial Fourier Data

  2010cited by this paper
• Regularization Paths for Generalized Linear Models via Coordinate Descent.

  2010cited by this paper
• A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation

  2010cited by this paper
• Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing

  2009cited by this paper
• The Application of Compressed Sensing for

  2009cited by this paper
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  2009influential reference
• The Split Bregman Method for L1-Regularized Problems

  2009influential reference
• Some First-Order Algorithms for Total Variation Based Image Restoration

  2009cited by this paper
• Algorithms and software for total variation image reconstruction via first-order methods

  2009cited by this paper
• Linearized Bregman iterations for compressed sensing

  2009cited by this paper
• Reproducible Research in Computational Harmonic Analysis

  2009cited by this paper
• Convergence of the linearized Bregman iteration for ℓ1-norm minimization

  2009cited by this paper
• A fast and accurate first-order algorithm for compressed sensing

  2009cited by this paper
• Probing the Pareto Frontier for Basis Pursuit Solutions

  2008influential reference
• Bregman Iterative Algorithms for (cid:2) 1 -Minimization with Applications to Compressed Sensing ∗

  2008cited by this paper
• A proximal decomposition method for solving convex variational inverse problems

  2008cited by this paper
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

  2008cited by this paper
• Compressed Sensing in Astronomy

  2008cited by this paper
• A Fast TVL1-L2 Minimization Algorithm for Signal Reconstruction from Partial Fourier Data

  2008cited by this paper
• Fixed-Point Continuation for l1-Minimization: Methodology and Convergence

  2008influential reference
• Fast Solution of (cid:0) (cid:0) -Norm Minimization Problems When the Solution May Be Sparse

  2008cited by this paper
• Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse

  2008influential reference
• Some algorithms for total variation based image restoration

  2008influential reference
• Sparse Reconstruction by Separable Approximation

  2008influential reference
• 15 Years of Reproducible Research in Computational Harmonic Analysis

  2008cited by this paper
• An Efficient Primal-Dual Hybrid Gradient Algorithm For Total Variation Image Restoration

  2008cited by this paper
• Near-ideal model selection by ℓ1 minimization

  2008cited by this paper
• Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

  2007influential reference
• Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization

  2007cited by this paper
• Compressed wavefield extrapolation

  2007cited by this paper
• A New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration

  2007cited by this paper
• On the performance of algorithms for the minimization of ℓ1-penalized functionals

  2007cited by this paper
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• Sparse MRI: The application of compressed sensing for rapid MR imaging

  2007cited by this paper
• An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares

  2007influential reference
• Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints

  2007cited by this paper
• Enhancing Sparsity by Reweighted ℓ1 Minimization

  2007cited by this paper
• Analysis versus synthesis in signal priors

  2006influential reference
• Fast Discrete Curvelet Transforms

  2006cited by this paper
• Sparse Solution Of Underdetermined Linear Equations By Stagewise Orthogonal Matching Pursuit

  2006cited by this paper
• Signal Recovery by Proximal Forward-Backward Splitting

  2005cited by this paper
• Smooth minimization of non-smooth functions

  2005influential reference
• A Fast and Exact Algorithm for Total Variation Minimization

  2005cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• An Algorithm for Total Variation Minimization and Applications

  2004cited by this paper
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

  2004cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• Affine Invariant Flows in the Beltrami Framework

  2004cited by this paper
• Introductory Lectures on Convex Optimization

  2003cited by this paper
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

  2003cited by this paper
• An EM algorithm for wavelet-based image restoration

  2003cited by this paper
• Lectures on modern convex optimization - analysis, algorithms, and engineering applications

  2001cited by this paper
• A new approach to variable selection in least squares problems

  2000cited by this paper
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets

  1999cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• A wavelet tour of signal processing

  1998cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Two-Point Step Size Gradient Methods

  1988cited by this paper
• A method for unconstrained convex minimization problem with the rate of convergence o(1/k^2)

  1983cited by this paper
• A method for solving the convex programming problem with convergence rate O(1/k^2)

  1983cited by this paper
• Signal processing

  1980cited by this paper
• Author's Personal Copy Applied and Computational Harmonic Analysis Accelerating Gradient Projection Methods for 1 -constrained Signal Recovery by Steplength Selection Rules

  year unknowncited by this paper

• Active nonuniform sampling.

  2026cites this paper
• Statistical compressive sensing method for Hadamard-based single-pixel microscopy supported by kernel density estimators

  2026cites this paper
• Nest-MGDL: Nesterov-Optimized Memory and Geometric Distillation Learning for Image Compressed Sensing

  2026cites this paper
• Frequency-decomposed attention joint optimization network for image compressive sensing

  2025cites this paper
• Compressive Phaseless Imaging Based on Synthetic Aperture Radar Techniques

  2025cites this paper
• Analysis of the Image Tiling Influence in its Sparse Reconstruction

  2025cites this paper
• Enhancing discrete cosine single-pixel imaging via DCT spectrum restoration

  2025cites this paper
• Recovering sparse DFT from missing signals via interior point method on GPU

  2025cites this paper
• Compressive Sensing for Inter-Frame Video Compression Using OMP and TVAL3 Algorithms

  2025cites this paper
• HUNet: Homotopy Unfolding Network for Image Compressive Sensing

  2025cites this paper
• Deblurring Images by Huber Lasso

  2025cites this paper
• F$^\mathbf {2}$Mamba: Frequency-Aware and Flexibly-Unfolded Mamba for Compressed Sensing

  2025cites this paper
• A Modified Dai-Liao Spectral Conjugate Gradient Method with an Application to Signal Processing

  2025cites this paper
• How to warm-start your unfolding network

  2025cites this paper
• SVD method for sparse recovery

  2025cites this paper
• Enhancing single-element compressive ultrasound imaging through novel random aperture masking and data mixing strategy.

  2025cites this paper
• APG-Net: APG Optimization-Induced Multiscale Attention Network for MRI Reconstruction From Undersampled k-Space Measurements

  2025cites this paper
• Using Powerful Prior Knowledge of Diffusion Model in Deep Unfolding Networks for Image Compressive Sensing

  2025cites this paper
• Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective

  2025cites this paper
• Stable recovery guarantees for ℓp/ℓq-minimization based on restricted isometry and orthogonality properties

  2025cites this paper
• Sparse Transform and Compressed Sensing Methods to Improve Efficiency and Quality in Magnetic Resonance Medical Imaging

  2025cites this paper
• Dense Optical Flow Estimation Using Sparse Regularizers From Reduced Measurements

  2024cites this paper
• A Fast Intersection of Confidence Intervals Method-Based Adaptive Thresholding for Sparse Image Reconstruction Using the Matrix Form of the Wavelet Transform

  2024cites this paper
• Distributed continuous-time accelerated neurodynamic approaches for sparse recovery via smooth approximation to L1-minimization

  2024cites this paper
• Analysis of the Robustness of Compressive Phaseless Imaging Under Noisy Conditions

  2024cites this paper
• A Low-Complexity and High-Quality Reconstruction Algorithm for Terahertz Single-Pixel Imaging

  2024cites this paper
• Distributed Inertial Proximal Neurodynamic Approach for Sparse Recovery on Directed Networks

  2024cites this paper
• Deep learning in classical x-ray ghost imaging for dose reduction

  2024cites this paper
• Accelerated Mirror Descent for Non-Euclidean Star-convex Functions

  2024cites this paper
• A Second-Order Continuous-Time Dynamical System for Solving Sparse Image Restoration Problems

  2024cites this paper
• Advances and Challenges of Single‐Pixel Imaging Based on Deep Learning

  2024cites this paper
• Compressed Hermite–Gaussian differential single-pixel imaging

  2024cites this paper
• A regularized eigenmatrix method for unstructured sparse recovery

  2024cites this paper
• NesTD-Net: Deep NESTA-Inspired Unfolding Network With Dual-Path Deblocking Structure for Image Compressive Sensing

  2024cites this paper
• Multi-Device Parallel MRI Reconstruction: Efficient Partitioning for Undersampled 5D Cardiac CINE

  2024cites this paper
• Regularization by deep learning in signal processing

  2024cites this paper
• A Survey of Advances in Optimization Methods for Wireless Communication System Design

  2024cites this paper
• Cardinality Minimization, Constraints, and Regularization: A Survey

  2024cites this paper
• High speed single pixel imaging using a microLED-on-CMOS light projector.

  2024cites this paper
• An inexact regularized proximal Newton method without line search

  2024cites this paper
• Dual-scan dual-frequency GPR imaging for mapping the permafrost table

  2024cites this paper
• A Novel Projection Neural Network for Sparse Optimization With ${L_\mathrm{{1}}}$-Minimization Problem

  2024cites this paper
• Transformation of Regressors for Low Coherent Sparse System Identification

  2024cites this paper
• Tight-Frame-Like Analysis-Sparse Recovery Using Nontight Sensing Matrices

  2023cites this paper
• Survey on compressed sensing over the past two decades

  2023cites this paper
• SALSA-Net: Explainable Deep Unrolling Networks for Compressed Sensing

  2023cites this paper
• Framework for Segmented threshold <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e4287" altimg="si398.svg"><mml:msub><mml:mrow><mml:mi>ℓ</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow></mml:msub></mml:math> gradient approximation based network for sparse s

  2023cites this paper
• A Survey on Regularized Sparse Optimization Models and Algorithms

  2023cites this paper
• A linearly convergent self-adaptive gradient projection algorithm for sparse signal reconstruction in compressive sensing

  2023cites this paper
• A Waveform Design for MIMO Sensing on Two-Dimensional Arrays with Sparse Estimation

  2023cites this paper
• A Unified Framework for Soft Threshold Pruning

  2023cites this paper
• Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods

  2023influential citation
• Stroke Diagnosis Using Microwave Techniques: Review of Systems and Algorithms

  2023cites this paper
• Integrated Single-Resonator Spectrometer beyond the Free-Spectral-Range Limit

  2023cites this paper
• Directional proximal point method for convex optimization

  2023cites this paper
• A dual active set method for $ \ell $1-regularized problem

  2023cites this paper
• An augmented Lagrangian method for nonconvex composite optimization problems with nonlinear constraints

  2023cites this paper
• Adaptive thresholding for sparse image reconstruction

  2023cites this paper
• A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions

  2023cites this paper
• Context-Aware Recovery of Image Block Compressive Sensing for Wireless Sensor Networks

  2023cites this paper
• Exploring the Effect of Sparse Recovery on the Quality of Image Superresolution

  2023cites this paper
• A Smoothing Conjugate Gradient Algorithm for Sparse Logistic Regression Problems

  2023cites this paper
• Riemannian acceleration with preconditioning for symmetric eigenvalue problems

  2023cites this paper
• Global Convergence and Acceleration of Projection Methods for Feasibility Problems Involving Union Convex Sets

  2022cites this paper
• Machine learning based efficient routing protocol in wireless sensor network

  2022cites this paper
• Neurodynamic approaches with derivative feedback for sparse signal reconstruction

  2022cites this paper
• Nonmonotone Quasi–Newton-based conjugate gradient methods with application to signal processing

  2022influential citation
• Structured Models for Semantic Analysis of Audio Content

  2022cites this paper
• Sparse Image Reconstruction via Fast ICI Based Adaptive Thresholding

  2022cites this paper
• Compressed Ultrasound Imaging: From Sub-Nyquist Rates to Super Resolution

  2022cites this paper
• CMSnet: State of the Art Deep Learning Multiscale Reconstruction for Compressive Sensing

  2022cites this paper
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems

  2022cites this paper
• An inexact regularized proximal Newton method for nonconvex and nonsmooth optimization

  2022cites this paper
• A Smoothing Inertial Neural Network for Sparse Signal Reconstruction with Noise Measurements via Lp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemarg

  2022cites this paper
• Performance measure for sparse recovery algorithms in compressed sensing perspective

  2022cites this paper
• Learning-based method for k-space trajectory design in MRI

  2022influential citation
• Non-Parametric Simultaneous Reconstruction and Denoising via Sparse and Low-Rank Regularization

  2022cites this paper
• A Joint Scheme of Antenna Placement and Power Allocation in a Compressive-Sensing-Based Colocated MIMO Radar

  2022cites this paper
• Comparison of compressive imaging and video techniques for threat detection applications

  2022influential citation
• Ultrasound Signal Processing: From Models to Deep Learning

  2022cites this paper
• Nonmonotone diagonally scaled limited-memory BFGS methods with application to compressive sensing based on a penalty model

  2022cites this paper
• Power module heat sink design optimization with ensembles of data-driven polynomial chaos surrogate models

  2022cites this paper
• Instability , Computational Efficiency and Statistical Accuracy Instability , Computational Efficiency and Statistical Accuracy

  2022cites this paper
• WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions

  2022cites this paper
• Fast iterative regularization by reusing data

  2022cites this paper
• Stable, accurate and efficient deep neural networks for inverse problems with analysis-sparse models

  2022influential citation
• Limitations of Deep Learning for Inverse Problems on Digital Hardware

  2022cites this paper
• Semi-Random Sparse Recovery in Nearly-Linear Time

  2022cites this paper
• Power Module Heat Sink Design Optimization with Data-Driven Polynomial Chaos Surrogate Models

  2022cites this paper
• Image Denoising Using a Compressive Sensing Approach Based on Regularization Constraints

  2022cites this paper
• Global convergence and acceleration of fixed point iterations of union upper semicontinuous operators: proximal algorithms, alternating and averaged nonconvex projections, and linear complementarity problems

  2022influential citation
• Adapted Variable Density Subsampling for Compressed Sensing

  2022cites this paper
• Green Visual Sensor of Plant: An Energy-Efficient Compressive Video Sensing in the Internet of Things

  2022cites this paper
• Solvability of monotone tensor complementarity problems

  2022cites this paper
• A hybrid quasi-Newton method with application in sparse recovery

  2022cites this paper
• Compressed Ultrasound Imaging: From Sub-Nyquist Rates to Super Resolution

  2022cites this paper
• The Essentials of Compressive Imaging

  2021cites this paper
• Compressed Sensing for Imaging

  2021cites this paper
• A review of single and multiple optical image encryption techniques

  2021cites this paper
• Total Variation Minimization

  2021cites this paper