Templates for convex cone problems with applications to sparse signal recovery

By Stephen Becker, E.J. Candes, Michael C. Grant. Mathematical Programming Computation, 2010

693 citations recorded by the source corpus.

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 introduces a number of technical contributions such as a novel continuation scheme and a novel approach for controlling the step size, and applies 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.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/1d7ad0a7ae64bd8d78d09d03ca181e6e579bd6d8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization (2015, methodology): “Motivated by the significant advances in integer optimization over the past 10-15 years, we present a Mixed Integer Linear Optimization (MILO) approach to obtain certifiably optimal global solutions to this nonconvex optimization problem.”
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, methodology): “’ There are several other methods that share similar characteristics, such as [55–62], as well as some techniques for solving the split-feasibility problem [35].”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “One of the ﬁrst provable algorithmic solutions for the QST problem was through convexiﬁcation [29, 65, 21]: this includes nuclear norm minimization approaches [33] (using e.g. , [7]), as well as proximal variants [30] (using e.g. , [17]).”
Pivotal estimation via square-root Lasso in nonparametric regression (2011, methodology): “ A(w) +b∈K. where f is a smooth function and his a structured function that is possibly non-diﬀerentiable or with extended values. However it allows for an eﬃcient proximal function to be solved, see [2]. By combining projections and (sub)gradient information these methods construct a sequence of it”
A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem (2012, background): “Nesterov gave some suggestions along this direction in [32], and strategies such as periodic restart have been studied recently [21, 3].”
Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm (2011, methodology): “For large-scale systems there has been some resurgence of first-order methods [16], [17], [18], [19], [20], [21] and recently there has been applications of first-order methods specifically for optimization-based image reconstruction in CT [21], [22], [23].”
Robust Subspace Clustering (2013, methodology): “For solving the LASSO problems in the two-step procedure, we developed a computational routine made publicly available [60] based on TFOCS [10] solving 9We have adopted this subsampling strategy to make our experiments reproducible.”
Phase recovery, MaxCut and complex semidefinite programming (2012, methodology): “If we use ﬁrst-order solvers such as TFOCS [Becker et al., 2012], based on the optimal algorithm in [Nesterov, 1983], the dependence on the dimension can be further reduced, to become for solving a penalized version of the PhaseCut relaxation and the penalized formulation of PhaseLift in (18).”
1-Bit Matrix Completion (2012, methodology): “We implement this traditional approach using the TFOCS software package [5], and evaluate the results using the same error criterion as the 1-bit matrix completion approach—namely, we compare the recovered ratings to the average (recovered) rating.”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, methodology): “We demonstrate how the objective F (x) progresses as a function of iterations k for solving (Left) the LS formulation (3), and (Right) the LASSO formulation (4), both with p = 5000 and n = 2500, for four methods: (proximal)-gradient descent with fixed step-size α = 1/L and adaptive step-size, accele”
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights (2014, background): “Notable applications can be found in sparse linear regression (Beck and Teboulle, 2009; Qin and Goldfarb, 2012), compressed sensing (Becker et al., 2011) and, deep and recurrent neural networks (Sutskever et al., 2013).”
A second-order method for strongly convex ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document}-re (2013, methodology): “An efficient implementation of this algorithm can be found as part of the TFOCS (Templates for First-Order Conic Solvers) package [5] under the name N83.”
Phase Retrieval from Coded Diffraction Patterns (2013, positive): “To solve the optimization problems below we use Auslender and Teboulle [6] sub-gradient optimization method with a solver written in the framework provided by TFOCS [17] (The code is available online at [1]).”
Bayesian Optimization and Semiparametric Models with Applications to Assistive Technology (2014, methodology): “Thus as an initial step, missing data is inferred using collaborative filtering techniques such as probabilistic principal components analysis with missing values (PPCA [Roweis, 1996]), Robust PCA with `1 norm minimization (RPCA Becker et al. [2011]) and probabilistic matrix factorization (PMF Salak”
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming (2011, methodology): “The numerical algorithm to solve (7.1) was implemented in Matlab using TFOCS [5].”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “mention that eective techniques have been developed for computing the stepsize k, in ISTA or FISTA, based on an estimate of the Lipschitz constant of rF or on curvature measured in recent iterations [8,152,9]. 8.1.2 Bound-Constrained Methods for ‘ 1-norm Regularized Problems By observing the structu”
A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms (2012, background): “…use of proximal splitting methods is spreading rapidly in signal and image processing, especially to solve large-scale problems formulated with sparsity-promoting (cid:2) 1 penalties; we refer to [9] for a recent overview with a list of relevant references, and to [1, 10–12] for examples of…”