NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
From MaRDI portal
Publication:3077123
DOI10.1137/090756855zbMATH Open1209.90265arXiv0904.3367OpenAlexW3124114587WikidataQ62780326 ScholiaQ62780326MaRDI QIDQ3077123FDOQ3077123
Emmanuel J. Candès, Jérôme Bobin, S. Becker
Publication date: 22 February 2011
Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)
Abstract: 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. Inspired by recent breakthroughs in the development of novel first-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.
Full work available at URL: https://arxiv.org/abs/0904.3367
compressed sensingNesterov's method\(\ell_1\) minimizationcontinuation methodsduality in convex optimizationsmooth approximations of nonsmooth functionstotal-variation minimization
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)
Cited In (only showing first 100 items - show all)
- Iterative choice of the optimal regularization parameter in TV image restoration
- A distributed algorithm for fitting generalized additive models
- A second-order method for strongly convex \(\ell _1\)-regularization problems
- Collaborative block compressed sensing reconstruction with dual-domain sparse representation
- Discussion: ``A significance test for the lasso
- Discussion: ``A significance test for the lasso
- Discussion: ``A significance test for the lasso
- Discussion: ``A significance test for the lasso
- A hybrid quasi-Newton method with application in sparse recovery
- Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence
- An FFT-based fast gradient method for elastic and inelastic unit cell homogenization problems
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- A unified primal-dual algorithm framework based on Bregman iteration
- An efficient augmented Lagrangian method with applications to total variation minimization
- On the regularizing behavior of the SDA and SDC gradient methods in the solution of linear ill-posed problems
- A forward and backward stagewise algorithm for nonconvex loss functions with adaptive Lasso
- A significance test for the lasso
- The geometry of least squares in the 21st century
- Discussion: ``A significance test for the lasso
- An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
- An alternating direction method of multipliers for MCP-penalized regression with high-dimensional data
- Accelerated gradient boosting
- A non-adapted sparse approximation of PDEs with stochastic inputs
- A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints
- Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
- ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
- A Trust-region Method for Nonsmooth Nonconvex Optimization
- Matrix-free interior point method for compressed sensing problems
- A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
- Restoration of images based on subspace optimization accelerating augmented Lagrangian approach
- PCM-TV-TFV: A Novel Two-Stage Framework for Image Reconstruction from Fourier Data
- Proximal methods for the latent group lasso penalty
- Generalized row-action methods for tomographic imaging
- A Proximal Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming with Applications to Imaging
- Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems
- NESTA
- Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
- Nonmonotone Barzilai-Borwein gradient algorithm for \(\ell_1\)-regularized nonsmooth minimization in compressive sensing
- A modified Newton projection method for \(\ell _1\)-regularized least squares image deblurring
- Sampling in the analysis transform domain
- Rejoinder: ``A significance test for the lasso
- Implementation of an optimal first-order method for strongly convex total variation regularization
- IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems
- Nesterov's smoothing and excessive gap methods for an optimization problem in VLSI placement
- Fast global convergence of gradient methods for high-dimensional statistical recovery
- Energy preserved sampling for compressed sensing MRI
- Restoring Poissonian images by a combined first-order and second-order variation approach
- Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data
- Reweighted minimization model for MR image reconstruction with split Bregman method
- Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique
- A non-convex regularization approach for compressive sensing
- The solution path of the generalized lasso
- An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
- Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection
- A relaxed-PPA contraction method for sparse signal recovery
- Combining line search and trust-region methods forℓ1-minimization
- An \(\mathcal O(1/{k})\) convergence rate for the variable stepsize Bregman operator splitting algorithm
- Discussion: ``A significance test for the lasso
- An introduction to continuous optimization for imaging
- Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
- Structured sparsity through convex optimization
- Relax-and-split method for nonconvex inverse problems
- Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- Templates for convex cone problems with applications to sparse signal recovery
- Solvability of monotone tensor complementarity problems
- An active-set proximal-Newton algorithm for \(\ell_1\) regularized optimization problems with box constraints
- Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications
- An Accelerated Linearized Alternating Direction Method of Multipliers
- Second order total generalized variation for Speckle reduction in ultrasound images
- Adaptive smoothing algorithms for nonsmooth composite convex minimization
- On the convergence of a class of inertial dynamical systems with Tikhonov regularization
- l1-Penalised Ordinal Polytomous Regression Estimators with Application to Gene Expression Studies
- Signal reconstruction by conjugate gradient algorithm based on smoothing \(l_1\)-norm
- Nonmonotone adaptive Barzilai-Borwein gradient algorithm for compressed sensing
- A projected gradient method for αℓ 1 − βℓ 2 sparsity regularization **
- A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions
- Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
- Two sufficient descent three-term conjugate gradient methods for unconstrained optimization problems with applications in compressive sensing
- A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
- A primal dual active set with continuation algorithm for high-dimensional nonconvex SICA-penalized regression
- Fast iterative regularization by reusing data
- Cardinality minimization, constraints, and regularization: a survey
- Sparsity Constrained Estimation in Image Processing and Computer Vision
- A dual active set method for \(\ell1\)-regularized problem
- A neurodynamic algorithm for sparse signal reconstruction with finite-time convergence
- An Iterative Reduction FISTA Algorithm for Large-Scale LASSO
- Tight-frame-like analysis-sparse recovery using nontight sensing matrices
- The Moreau envelope based efficient first-order methods for sparse recovery
- A modulus-based iterative method for sparse signal recovery
- WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions
- ADMM in Krylov Subspace and Its Application to Total Variation Restoration of Spatially Variant Blur
- An active-set proximal quasi-Newton algorithm for ℓ1-regularized minimization over a sphere constraint
- Implicit regularization with strongly convex bias: Stability and acceleration
- Robust Manhattan non-negative matrix factorization for image recovery and representation
- Analysis of the maximum magnification by the scaled memoryless DFP updating formula with application to compressive sensing
- Nesterov's algorithm solving dual formulation for compressed sensing
- An accelerated Uzawa method for application to frictionless contact problem
- Framework for segmented threshold \(\ell_0\) gradient approximation based network for sparse signal recovery
- Alternating direction method of multipliers for solving dictionary learning models
Uses Software
This page was built for publication: NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3077123)
