Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

Abstract

This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal first-order method. A merit of this approach is its flexibility: for example, all compressed sensing problems can be solved via this approach. These include models with objective functionals such as the total-variation norm, ||Wx||_1 where W is arbitrary, or a combination thereof. In addition, the paper also introduces a number of technical contributions such as a novel continuation scheme, a novel approach for controlling the step size, and some new results showing that the smooth and unsmoothed problems are sometimes formally equivalent. Combined with our framework, these lead to novel, stable and computationally efficient algorithms. For instance, our general implementation is competitive with state-of-the-art methods for solving intensively studied problems such as the LASSO. Further, numerical experiments show that one can solve the Dantzig selector problem, for which no efficient large-scale solvers exist, in a few hundred iterations. Finally, the paper is accompanied with a software release. This software is not a single, monolithic solver; rather, it is a suite of programs and routines designed to serve as building blocks for constructing complete algorithms.

The TFOCS software is available at http://tfocs.stanford.edu This version has updated references

References in corpus (1)

• Constructing test instances for Basis Pursuit Denoising

Cited by in corpus (155)

• A survey of sparse representation: algorithms and applications
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• A significance test for the lasso
• Optimum Design for Coexistence Between Matrix Completion Based MIMO Radars and a MIMO Communication System
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm
• Convex Optimization for Big Data
• SLOPE - Adaptive variable selection via convex optimization
• Robust subspace clustering
• Pivotal estimation via square-root Lasso in nonparametric regression
• Lasso Screening Rules via Dual Polytope Projection
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Superfast maximum likelihood reconstruction for quantum tomography
• Constrained Overcomplete Analysis Operator Learning for Cosparse Signal Modelling
• The Numerics of Phase Retrieval
• MIMO-MC Radar: A MIMO Radar Approach Based on Matrix Completion
• Phase Retrieval from 1D Fourier Measurements: Convexity, Uniqueness, and Algorithms
• Randomized Low-Rank Dynamic Mode Decomposition for Motion Detection
• Statistical estimation and testing via the sorted L1 norm
• Core Imaging Library -- Part I: a versatile Python framework for tomographic imaging
• Composite Self-Concordant Minimization
• Sparse projections onto the simplex
• Tensor Completion from Regular Sub-Nyquist Samples
• Statistical Multiresolution Dantzig Estimation in Imaging: Fundamental Concepts and Algorithmic Framework
• Sparse CCA: Adaptive Estimation and Computational Barriers
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
• Acceleration Methods
• Dropping Convexity for Faster Semi-definite Optimization
• Quadrature Compressive Sampling for Radar Signals
• Online Unmixing of Multitemporal Hyperspectral Images accounting for Spectral Variability
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Target Estimation in Colocated MIMO Radar via Matrix Completion
• An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
• Multicompartment Magnetic Resonance Fingerprinting
• Efficient hybridization fitting for dynamical mean-field theory via semi-definite relaxation
• Convex optimization over classes of multiparticle entanglement
• Efficient First Order Methods for Linear Composite Regularizers
• Efficient Solvers for Sparse Subspace Clustering
• High-Accuracy Total Variation for Compressed Video Sensing
• Efficient Compressive Phase Retrieval with Constrained Sensing Vectors
• Parameterless Optimal Approximate Message Passing
• An approximation algorithm for joint caching and recommendations in cache networks
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Constrained adaptive sensing
• Matrix completion with deterministic pattern - a geometric perspective
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Reconstruction with a Convex Constraint
• Low-rank spectral optimization via gauge duality
• Signal reconstruction from the magnitude of subspace components
• Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing
• Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
• Adaptive Restart for Accelerated Gradient Schemes
• Compressive Principal Component Pursuit
• Learning interactions through hierarchical group-lasso regularization
• A Second-Order Method for Strongly Convex L1-Regularization Problems
• An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization
• IMRO: a proximal quasi-Newton method for solving $l_1$-regularized least square problem
• Ranking and synchronization from pairwise measurements via SVD
• Phase retrieval for imaging problems
• Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
• Sparse canonical correlation analysis
• Learning Mixed Graphical Models
• Accurate detection of moving targets via random sensor arrays and Kerdock codes
• Learning Heteroscedastic Models by Convex Programming under Group Sparsity
• Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions
• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Optimal subgradient algorithms with application to large-scale linear inverse problems
• Fast non-coplanar beam orientation optimization based on group sparsity
• Sparse Signal Separation in Redundant Dictionaries
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Robust Finite Mixture Regression for Heterogeneous Targets
• User-Curated Image Collections: Modeling and Recommendation
• Proximal Gradient Method with Extrapolation and Line Search for a Class of Nonconvex and Nonsmooth Problems
• Approximate Leave-One-Out for High-Dimensional Non-Differentiable Learning Problems
• Accelerating Nesterov's Method for Strongly Convex Functions with Lipschitz Gradient
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Sparse point-source removal for full-sky CMB experiments: application to WMAP 9-year data
• Non-Common Band SAR Interferometry via Compressive Sensing
• Proximal Alternating Penalty Algorithms for Constrained Convex Optimization
• Super-Resolution Radar
• Fast and Accurate Algorithms for Re-Weighted L1-Norm Minimization
• DECONET: an Unfolding Network for Analysis-based Compressed Sensing with Generalization Error Bounds
• A sparse semismooth Newton based proximal majorization-minimization algorithm for nonconvex square-root-loss regression problems
• Parameter-free accelerated gradient descent for nonconvex minimization
• Re-Weighted l_1 Dynamic Filtering for Time-Varying Sparse Signal Estimation
• A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries
• Spark Deficient Gabor Frame Provides a Novel Analysis Operator for Compressed Sensing
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
• Tensor-Free Proximal Methods for Lifted Bilinear/Quadratic Inverse Problems with Applications to Phase Retrieval
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• High-Dimensional Confidence Regions in Sparse MRI
• Multi-Branch Matching Pursuit with applications to MIMO radar
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• A Bayesian approach for energy-based estimation of acoustic aberrations in high intensity focused ultrasound treatment
• Improved Recovery of Analysis Sparse Vectors in Presence of Prior Information
• A Proximal Stochastic Quasi-Newton Algorithm
• Algorithms and software for projections onto intersections of convex and non-convex sets with applications to inverse problems
• Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures
• Chaotic Analog-to-Information Conversion: Principle and Reconstructability with Parameter Identifiability
• Solving L1-regularized SVMs and related linear programs: Revisiting the effectiveness of Column and Constraint Generation
• Quantifying admissible undersampling for sparsity-exploiting iterative image reconstruction in X-ray CT
• Fast Phase Retrieval from Local Correlation Measurements
• Robust Sparse Phase Retrieval Made Easy
• Using Convex Optimization of Autocorrelation with Constrained Support and Windowing for Improved Phase Retrieval Accuracy
• An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimization
• Adaptive Sieving with PPDNA: Generating Solution Paths of Exclusive Lasso Models
• Complexity penalized hydraulic fracture localization and moment tensor estimation under limited model information
• Generalized Conjugate Gradient Methods for ${\ell }_1$ Regularized Convex Quadratic Programming with Finite Convergence
• An LS-Decomposition Approach for Robust Data Recovery in Wireless Sensor Networks
• How Low Can We Go: Trading Memory for Error in Low-Precision Training
• Fast Signal Separation of 2D Sparse Mixture via Approximate Message-Passing
• Nonparametric Operator-Regularized Covariance Function Estimation for Functional Data
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• NCVX: A User-Friendly and Scalable Package for Nonconvex Optimization in Machine Learning
• Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
• Computing Estimators of Dantzig Selector type via Column and Constraint Generation
• Matrix Computations and Optimization in Apache Spark
• Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems
• Low-Rank and Total Variation Regularization and Its Application to Image Recovery
• Star DGT: a Robust Gabor Transform for Speech Denoising
• Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
• Solving ptychography with a convex relaxation
• The proximal-proximal gradient algorithm
• Computing ground states of Bose-Einstein Condensates with higher order interaction via a regularized density function formulation
• On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations
• Accelerated first-order methods for large-scale convex minimization
• New Proximal Newton-Type Methods for Convex Optimization
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems
• Selective Inference and Learning Mixed Graphical Models
• A proximal difference-of-convex algorithm with extrapolation
• Deep Tensor Encoding
• A Direct Estimation Approach to Sparse Linear Discriminant Analysis
• Best Rank-One Tensor Approximation and Parallel Update Algorithm for CPD
• Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application to Reinforcement Learning
• Safe Feature Elimination for Non-Negativity Constrained Convex Optimization
• Efficient ${\ell }_q$ Minimization Algorithms for Compressive Sensing Based on Proximity Operator
• Inexact proximal DC Newton-type method for nonconvex composite functions
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Reliable optimization of arbitrary functions over quantum measurements
• Numerical solution of an inverse random source problem for the time fractional diffusion equation via PhaseLift
• An Extrapolated Iteratively Reweighted l1 Method with Complexity Analysis
• Short Term Memory Capacity in Networks via the Restricted Isometry Property
• The Sparse Reverse of Principal Component Analysis for Fast Low-Rank Matrix Completion
• Phase inpainting in time-frequency plane
• Linearly Constrained Smoothing Group Sparsity Solvers in Off-grid Model
• PCM-TV-TFV: A Novel Two Stage Framework for Image Reconstruction from Fourier Data
• A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems
• An Algorithm for Quadratic ${\ell }_1$-Regularized Optimization with a Flexible Active-Set Strategy
• An optimal subgradient algorithm for large-scale convex optimization in simple domains
• Segment-Sliding Reconstruction of Pulsed Radar Echoes with Sub-Nyquist Sampling
• A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem
• An acceleration procedure for optimal first-order methods