Templates for convex cone problems with applications to sparse signal recovery

DOI10.1007/s12532-011-0029-5zbMath1257.90042arXiv1009.2065OpenAlexW2119058682MaRDI QIDQ1762456

Michael C. Grant, Stephen R. Becker, Emmanuel J. Candès

Publication date: 27 November 2012

Published in: Mathematical Programming Computation (Search for Journal in Brave)

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

zbMATH Keywords

Dantzig selectorLASSOproximal algorithmsnuclear-norm minimizationconic dualityNesterov's accelerated descent algorithmsoptimal first-order methodssmoothing by conjugation

Mathematics Subject Classification ID

Ridge regression; shrinkage estimators (Lasso) (62J07) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)

Related Items

Nonparametric operator-regularized covariance function estimation for functional data, Refined analysis of sparse MIMO radar, A secant-based Nesterov method for convex functions, An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems, A line search filter-SQP method with Lagrangian function for nonlinear inequality constrained optimization, WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions, Low-Rank and Sparse Dictionary Learning, The Moreau envelope based efficient first-order methods for sparse recovery, An inexact successive quadratic approximation method for L-1 regularized optimization, Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems, OSGA: a fast subgradient algorithm with optimal complexity, A Newton Frank-Wolfe method for constrained self-concordant minimization, A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems, Book Review: A mathematical introduction to compressive sensing, Fast Phase Retrieval from Local Correlation Measurements, An algorithm for quadratic ℓ₁-regularized optimization with a flexible active-set strategy, A Survey of Compressed Sensing, Generalized System Identification with Stable Spline Kernels, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, Phase retrieval for imaging problems, Tomographic image reconstruction using training images, A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer, Robust sparse phase retrieval made easy, Finding Dantzig selectors with a proximity operator based fixed-point algorithm, Sparse microwave imaging: principles and applications, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, Distributed solutions for loosely coupled feasibility problems using proximal splitting methods, Benchmarking large-scale distributed convex quadratic programming algorithms, Multicompartment magnetic resonance fingerprinting, An alternating direction method for finding Dantzig selectors, A fast splitting method tailored for Dantzig selector, TILT: transform invariant low-rank textures, Adventures in Compressive Sensing Based MIMO Radar, The matrix splitting based proximal fixed-point algorithms for quadratically constrained \(\ell_{1}\) minimization and Dantzig selector, Iteratively reweighted \(\ell _1\) algorithms with extrapolation, A distributed algorithm for fitting generalized additive models, Optimal subgradient algorithms for large-scale convex optimization in simple domains, Matrix-Free Convex Optimization Modeling, Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems, Unnamed Item, A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems, SLOPE-adaptive variable selection via convex optimization, Accelerated linearized Bregman method, A proximal quasi-Newton method based on memoryless modified symmetric rank-one formula, Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements, Super-resolution radar, Smoothed \(\ell_1\)-regularization-based line search for sparse signal recovery, Statistical multiresolution Dantzig estimation in imaging: fundamental concepts and algorithmic framework, Implementation of an optimal first-order method for strongly convex total variation regularization, A relaxed-PPA contraction method for sparse signal recovery, Accelerated first-order methods for hyperbolic programming, Convergence of first-order methods via the convex conjugate, New preconditioners applied to linear programming and the compressive sensing problems, Proximal alternating penalty algorithms for nonsmooth constrained convex optimization, PRP-like algorithm for monotone operator equations, Optimization Methods for Large-Scale Machine Learning, A partially proximal linearized alternating minimization method for finding Dantzig selectors, A proximal difference-of-convex algorithm with extrapolation, FOM – a MATLAB toolbox of first-order methods for solving convex optimization problems, Inexact proximal Newton methods for self-concordant functions, A significance test for the lasso, Discussion: ``A significance test for the lasso, Rejoinder: ``A significance test for the lasso, Robust subspace clustering, Adaptive smoothing algorithms for nonsmooth composite convex minimization, Learning with tensors: a framework based on convex optimization and spectral regularization, A global sparse gradient based coupled system for image denoising, On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems, A general self-adaptive relaxed-PPA method for convex programming with linear constraints, Robust budget allocation via continuous submodular functions, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, Inexact proximal memoryless quasi-Newton methods based on the Broyden family for minimizing composite functions, A dual reformulation and solution framework for regularized convex clustering problems, PCM-TV-TFV: A Novel Two-Stage Framework for Image Reconstruction from Fourier Data, A tensor-based dictionary learning approach to tomographic image reconstruction, Super-Resolution of Positive Sources: The Discrete Setup, The matrix completion method for phase retrieval from fractional Fourier transform magnitudes, Using Nesterov's Method to Accelerate Multibody Dynamics with Friction and Contact, Robust finite mixture regression for heterogeneous targets, Phase recovery, MaxCut and complex semidefinite programming, Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization, Phase retrieval from coded diffraction patterns, Analysis of sparse MIMO radar, Low-Rank Spectral Optimization via Gauge Duality, Tensor-free proximal methods for lifted bilinear/quadratic inverse problems with applications to phase retrieval, Safe feature elimination for non-negativity constrained convex optimization, TFOCS, A comparison of numerical methods for solving multibody dynamics problems with frictional contact modeled via differential variational inequalities, Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity, Optimal subgradient methods: computational properties for large-scale linear inverse problems, Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence, PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming, Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems, Generalized self-concordant functions: a recipe for Newton-type methods, Block matching video compression based on sparse representation and dictionary learning, GenePEN: analysis of network activity alterations in complex diseases via the pairwise elastic net, COAL: a generic modelling and prototyping framework for convex optimization problems of variational image analysis, Efficient Sparse Hessian-Based Semismooth Newton Algorithms for Dantzig Selector, Adaptive restart for accelerated gradient schemes, A second-order method for strongly convex \(\ell _1\)-regularization problems, The numerics of phase retrieval, A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization, Quantization-aware phase retrieval, An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis, Star DGT: a robust Gabor transform for speech denoising, Doubly iteratively reweighted algorithm for constrained compressed sensing models, Composite Convex Minimization Involving Self-concordant-Like Cost Functions, Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints, Inexact proximal DC Newton-type method for nonconvex composite functions, Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability, Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems, Short-Term Memory Capacity in Networks via the Restricted Isometry Property, Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators, CHAOTIC ANALOG-TO-INFORMATION CONVERSION: PRINCIPLE AND RECONSTRUCTABILITY WITH PARAMETER IDENTIFIABILITY, A Bayesian Approach for Energy-Based Estimation of Acoustic Aberrations in High Intensity Focused Ultrasound Treatment, IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems, An acceleration procedure for optimal first-order methods, Computing Ground States of Bose--Einstein Condensates with Higher Order Interaction via a Regularized Density Function Formulation, Phase Retrieval via Matrix Completion, Generalized Conjugate Gradient Methods for ℓ₁ Regularized Convex Quadratic Programming with Finite Convergence, A Single-Phase, Proximal Path-Following Framework, Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably, Polar Convolution, A time continuation based fast approximate algorithm for compressed sensing related optimization, Numerical solution of an inverse random source problem for the time fractional diffusion equation via PhaseLift, Global Registration of Multiple Point Clouds Using Semidefinite Programming, 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

Uses Software

• PROPACK
• CVX
• Mosek
• PDCO
• NESTA
• glmnet
• SPGL1
• ParNes
• FPC_AS
• L1-MAGIC
• L1TestPack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonlinear total variation based noise removal algorithms
• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
• An implementable proximal point algorithmic framework for nuclear norm minimization
• Compressed sensing with coherent and redundant dictionaries
• Dualization of signal recovery problems
• Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Wavelets and curvelets for image deconvolution: a combined approach
• Fast linearized Bregman iteration for compressive sensing and sparse denoising
• Introductory lectures on convex optimization. A basic course.
• New multiscale transforms, minimum total variation synthesis: Applications to edge-preserving image reconstruction
• Least angle regression. (With discussion)
• A first-order primal-dual algorithm for convex problems with applications to imaging
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Exact matrix completion via convex optimization
• A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
• Analysis and Generalizations of the Linearized Bregman Method
• A Singular Value Thresholding Algorithm for Matrix Completion
• NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• Exact Regularization of Convex Programs
• DASSO: Connections Between the Dantzig Selector and Lasso
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing
• Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
• Nonlinear Perturbation of Linear Programs
• A generalized proximal point algorithm for certain non-convex minimization problems
• New Proximal Point Algorithms for Convex Minimization
• Monotone Operators and the Proximal Point Algorithm
• Sparse Reconstruction by Separable Approximation
• Constructing Test Instances for Basis Pursuit Denoising
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Analysis versus synthesis in signal priors
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Signal Recovery by Proximal Forward-Backward Splitting
• Proximité et dualité dans un espace hilbertien
• Convex Analysis