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 (only showing first 100 items - show all)

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

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

This page was built for publication: Templates for convex cone problems with applications to sparse signal recovery