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

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.

References in corpus (3)

• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• Near-ideal model selection by ${\ell }_1$ minimization
• Compressed Sensing in Astronomy

Cited by in corpus (62)

• A survey of sparse representation: algorithms and applications
• An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems
• Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning
• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• A significance test for the lasso
• The solution path of the generalized lasso
• Compressive Fluorescence Microscopy for Biological and Hyperspectral Imaging
• Enhancing ${\ell }_1$-minimization estimates of polynomial chaos expansions using basis selection
• Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches
• Evanescently coupled multimode spiral spectrometer
• Learning-based Compressive Subsampling
• Smoothing and Decomposition for Analysis Sparse Recovery
• Constrained Overcomplete Analysis Operator Learning for Cosparse Signal Modelling
• Dense Recurrent Neural Networks for Accelerated MRI: History-Cognizant Unrolling of Optimization Algorithms
• Broadband multimode fiber spectrometer
• Radial Velocity Data Analysis with Compressed Sensing Techniques
• Compressed sensing for longitudinal MRI: An adaptive-weighted approach
• Real-time single-pixel video imaging with Fourier domain regularization
• Compressed Sensing with General Frames via Optimal-dual-based ${\ell }_1$-analysis
• Sparse Signal Recovery via Generalized Entropy Functions Minimization
• Sparse Generalized Eigenvalue Problem via Smooth Optimization
• The application of compressive sampling to radio astronomy II: Faraday rotation measure synthesis
• Single-pixel imaging with Morlet wavelet correlated random patterns
• Ultrasound Signal Processing: From Models to Deep Learning
• Convergence Speed of a Dynamical System for Sparse Recovery
• A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing
• ICR: Iterative Convex Refinement for Sparse Signal Recovery Using Spike and Slab Priors
• High-Accuracy Total Variation for Compressed Video Sensing
• Generalized Row-Action Methods for Tomographic Imaging
• Target Oriented High Resolution SAR Image Formation via Semantic Information Guided Regularizations
• Iterative regularization via dual diagonal descent
• Optimal compressive multiphoton imaging at depth using single-pixel detection
• CAPPA: Continuous-time Accelerated Proximal Point Algorithm for Sparse Recovery
• Limitations of Deep Learning for Inverse Problems on Digital Hardware
• Differential real-time single-pixel imaging with Fourier domain regularization -- applications to VIS-IR imaging and polarization imaging
• Casual Compressive Sensing for Gene Network Inference
• A Total-Variation Sparseness-Promoting Method for the Synthesis of Contiguously Clustered Linear Arrays
• Norm-1 Regularized Consensus-based ADMM for Imaging with a Compressive Antenna
• Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery
• Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection
• Nonmonotone Barzilai-Borwein Gradient Algorithm for ${\ell }_1$-Regularized Nonsmooth Minimization in Compressive Sensing
• Utilizing the Wavelet Transform's Structure in Compressed Sensing
• IMRO: a proximal quasi-Newton method for solving $l_1$-regularized least square problem
• Blind Inference of Eigenvector Centrality Rankings
• Compressed Sensing with Linear Correlation Between Signal and Measurement Noise
• Robust Single-Image Super-Resolution via CNNs and TV-TV Minimization
• Reconstruction of optical vector-fields with applications in endoscopic imaging
• Accelerated Cardiac Diffusion Tensor Imaging Using Joint Low-Rank and Sparsity Constraints
• Analysis Based Blind Compressive Sensing
• Learning Co-Sparse Analysis Operators with Separable Structures
• GMRES-Accelerated ADMM for Quadratic Objectives
• Partially Linear Estimation with Application to Sparse Signal Recovery From Measurement Pairs
• NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems
• A projected gradient method for $\alpha {\ell }_1-\beta {\ell }_2$ sparsity regularization
• Power Module Heat Sink Design Optimization with Ensembles of Data-Driven Polynomial Chaos Surrogate Models
• The geometry of least squares in the 21st century
• Direct deconvolution of radio synthesis images using L1 minimisation
• An Accelerated Uzawa Method for Application to Frictionless Contact Problem
• Bell non-locality using tensor networks and sparse recovery
• A Variational View on Statistical Multiscale Estimation