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

DOI10.1137/090756855zbMath1209.90265arXiv0904.3367OpenAlexW3124114587WikidataQ62780326 ScholiaQ62780326MaRDI QIDQ3077123

Emmanuel J. Candès, Jérôme Bobin, Stephen R. Becker

Publication date: 22 February 2011

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.3367

zbMATH Keywords

continuation methods compressed sensing Nesterov's method $\ell_1$ minimization duality in convex optimization smooth approximations of nonsmooth functions total-variation minimization

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Related Items (only showing first 100 items - show all)

A Trust-region Method for Nonsmooth Nonconvex Optimization ⋮ WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions ⋮ An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems ⋮ An Iterative Reduction FISTA Algorithm for Large-Scale LASSO ⋮ A smoothing inertial neural network for sparse signal reconstruction with noise measurements via $L_p-L_1$ minimization ⋮ Framework for segmented threshold $\ell_0$ gradient approximation based network for sparse signal recovery ⋮ Smoothing inertial neurodynamic approach for sparse signal reconstruction via $L_p$-norm minimization ⋮ A dual active set method for $\ell1$-regularized problem ⋮ A primal dual active set with continuation algorithm for high-dimensional nonconvex SICA-penalized regression ⋮ Nonmonotone quasi-Newton-based conjugate gradient methods with application to signal processing ⋮ A neurodynamic algorithm for sparse signal reconstruction with finite-time convergence ⋮ A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions ⋮ Relax-and-split method for nonconvex inverse problems ⋮ A projected gradient method for αℓ ₁ − βℓ ₂ sparsity regularization ^** ⋮ IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems ⋮ An introduction to continuous optimization for imaging ⋮ Structured sparsity through convex optimization ⋮ An Efficient Proximal Block Coordinate Homotopy Method for Large-Scale Sparse Least Squares Problems ⋮ Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence ⋮ l1-Penalised Ordinal Polytomous Regression Estimators with Application to Gene Expression Studies ⋮ Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably ⋮ An Accelerated Linearized Alternating Direction Method of Multipliers ⋮ Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging ⋮ 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 ⋮ Discussion: ``A significance test for the lasso ⋮ ADMM in Krylov Subspace and Its Application to Total Variation Restoration of Spatially Variant Blur ⋮ An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint ⋮ Implicit regularization with strongly convex bias: Stability and acceleration ⋮ Combining line search and trust-region methods forℓ1-minimization ⋮ On the regularizing behavior of the SDA and SDC gradient methods in the solution of linear ill-posed problems ⋮ The Moreau envelope based efficient first-order methods for sparse recovery ⋮ Proximal Markov chain Monte Carlo algorithms ⋮ A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints ⋮ Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique ⋮ Performance of first- and second-order methods for $\ell_1$-regularized least squares problems ⋮ An alternating direction method of multipliers for MCP-penalized regression with high-dimensional data ⋮ Accelerated gradient sliding for structured convex optimization ⋮ Two sufficient descent three-term conjugate gradient methods for unconstrained optimization problems with applications in compressive sensing ⋮ A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems ⋮ A dual method for minimizing a nonsmooth objective over one smooth inequality constraint ⋮ An efficient augmented Lagrangian method with applications to total variation minimization ⋮ GMRES-Accelerated ADMM for Quadratic Objectives ⋮ An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing ⋮ Sparsity Constrained Estimation in Image Processing and Computer Vision ⋮ A Proximal Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming with Applications to Imaging ⋮ Restoring Poissonian images by a combined first-order and second-order variation approach ⋮ Nonmonotone diagonally scaled limited-memory BFGS methods with application to compressive sensing based on a penalty model ⋮ A forward and backward stagewise algorithm for nonconvex loss functions with adaptive Lasso ⋮ A hybrid quasi-Newton method with application in sparse recovery ⋮ Reweighted minimization model for MR image reconstruction with split Bregman method ⋮ Smoothing strategy along with conjugate gradient algorithm for signal reconstruction ⋮ A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing ⋮ ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals ⋮ The geometry of least squares in the 21st century ⋮ Robust Manhattan non-negative matrix factorization for image recovery and representation ⋮ Approximation accuracy, gradient methods, and error bound for structured convex optimization ⋮ The matrix splitting based proximal fixed-point algorithms for quadratically constrained $\ell_{1}$ minimization and Dantzig selector ⋮ Fast bundle-level methods for unconstrained and ball-constrained convex optimization ⋮ A distributed algorithm for fitting generalized additive models ⋮ Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization ⋮ Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step ⋮ Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems ⋮ Accelerated gradient boosting ⋮ A simple homotopy proximal mapping algorithm for compressive sensing ⋮ Sampling in the analysis transform domain ⋮ Restoration of images based on subspace optimization accelerating augmented Lagrangian approach ⋮ Solvability of monotone tensor complementarity problems ⋮ Collaborative block compressed sensing reconstruction with dual-domain sparse representation ⋮ Primal and dual alternating direction algorithms for $\ell _{1}$-$\ell _{1}$-norm minimization problems in compressive sensing ⋮ Robust image compressive sensing based on half-quadratic function and weighted Schatten-$p$ norm ⋮ Smoothed $\ell_1$-regularization-based line search for sparse signal recovery ⋮ Iterative regularization via dual diagonal descent ⋮ A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems ⋮ The solution path of the generalized lasso ⋮ Implementation of an optimal first-order method for strongly convex total variation regularization ⋮ A unified primal-dual algorithm framework based on Bregman iteration ⋮ NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems ⋮ Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data ⋮ A relaxed-PPA contraction method for sparse signal recovery ⋮ Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework ⋮ Proximal methods for the latent group lasso penalty ⋮ Accelerated first-order methods for hyperbolic programming ⋮ An active-set proximal-Newton algorithm for $\ell_1$ regularized optimization problems with box constraints ⋮ Nonmonotone adaptive Barzilai-Borwein gradient algorithm for compressed sensing ⋮ Nonmonotone Barzilai-Borwein gradient algorithm for $\ell_1$-regularized nonsmooth minimization in compressive sensing ⋮ A new piecewise quadratic approximation approach for $L_0$ norm minimization problem ⋮ An Introduction to Compressed Sensing ⋮ An accelerated Uzawa method for application to frictionless contact problem ⋮ Nesterov's smoothing and excessive gap methods for an optimization problem in VLSI placement ⋮ Analysis of the maximum magnification by the scaled memoryless DFP updating formula with application to compressive sensing ⋮ Second order total generalized variation for Speckle reduction in ultrasound images ⋮ A compressed-sensing approach for closed-loop optimal control of nonlinear systems ⋮ A significance test for the lasso ⋮ Discussion: ``A significance test for the lasso ⋮ Rejoinder: ``A significance test for the lasso ⋮ Adaptive smoothing algorithms for nonsmooth composite convex minimization ⋮ On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization

Uses Software

This page was built for publication: NESTA: A Fast and Accurate First-Order Method for Sparse Recovery