Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

Stephen R. Becker; Emmanuel J. Candès; Michael Grant

Source-linked AI summary

Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

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

arXiv:1009.2065v3Sep 10, 2010math.OCmath.NAmath.ST

TL;DR

Many sparse and low-rank recovery problems lack flexible, scalable algorithms across their varied convex formulations. This paper combines conic modeling, duality, smoothing, and optimal first-order methods, yielding competitive LASSO algorithms and practical Dantzig selector solvers while leaving several implementation improvements for future work.

Problem
Large-scale sparse-recovery formulations, including nonorthogonal ℓ1-analysis and constrained Dantzig selector problems, lack efficient general-purpose algorithms.
Method
The framework converts a problem to conic form, derives its dual, applies smoothing, and solves the resulting model with optimal first-order methods.
Results
The resulting algorithms handle varied sparse and low-rank recovery models and are competitive with state-of-the-art methods on the LASSO.
Takeaways & Limitations
The flexible templates support interchangeable solvers and a wide variety of formulations, including total variation, arbitrary-W ℓ1-analysis, and other recovery problems.
Takeaways & Limitations
Accelerated continuation can require many inner iterations when updates are complicated or the smoothing parameter changes, because the previous dual variable is no longer a good starting estimate.

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents sparse and low-rank recovery problems arising from undersampled noisy data, emphasizing estimators and formulations that require scalable computational methods. It motivates Dantzig selector, LASSO, transformed-domain sparsity, total variation, and nuclear-norm models.

The paper targets convex optimization programs in signal and image processing, statistics, computer vision, and related fields.
When m < n, the Dantzig selector estimates nearly sparse vectors by minimizing ℓ1 norm subject to a residual-correlation constraint.The constraint is typically calibrated so the true vector is feasible with high probability under stochastic noise.
The LASSO uses an ℓ2 data-fidelity constraint, and both it and the Dantzig selector can accurately estimate nearly sparse vectors.The paper seeks algorithms handling problems with thousands or millions of variables and observations.
Image recovery can combine transformed-domain sparsity with total variation to reduce artifacts such as Gibbs oscillations.The transform W may be nonorthogonal, while total variation regularizes image differences.
The framework also addresses recovery of low-rank matrices from undersampled data, including matrix completion from revealed entries.A linear operator supplies measurements, and the nuclear norm is used in the associated convex formulation.

1.2 The literature

The literature review describes important gaps in scalable algorithms for constrained sparse-recovery formulations. Existing methods are effective only for particular operators, projections, or problem sizes, while Dantzig selector and mixed-norm problems remain difficult at scale.

Most LASSO methods address an unconstrained quadratic-penalty formulation rather than the hard-constrained problem studied here.
SPGL1 is designed for the constrained LASSO but cannot handle important nonorthogonal-transform variations.Its limitations arise because standard ℓ1 proximity operators are efficiently computed by soft-thresholding, unlike proximity operators for ∥Wx∥1 with general W.
NESTA handles ∥Wx∥1 efficiently but requires repeated feasible-set projections and is most effective when AA∗ is a projector or has well-clustered eigenvalues.
Homotopy methods compute full solution paths but do not scale well, especially when the solution is not very sparse.
Dantzig selector algorithms based on linear programming, interior-point methods, or homotopy methods are scarce and problematic for large problems.The mixed-norm formulation can be recast as an SOCP, but solving it with an interior-point method is likewise problematic at large scale.

1.3 Our approach

The proposed approach converts convex models into conic form, derives a dual problem, smooths its nonsmooth objective, and applies optimal first-order methods. Dualization and generalized projections make the resulting computations more tractable across varied models.

The template consists of four stages: formulate the problem conically, derive its dual, apply smoothing, and solve with an optimal first-order method.
A conic model uses a convex objective, a linear operator, an offset vector, and a closed convex cone; many convex constraints can be represented this way.Linear equations, linear inequalities, and norm inequalities are among the readily transformed cases.
Dualization replaces potentially expensive primal feasible-set projections with projections onto dual cones that are usually tractable and efficient.For the LASSO, the second-order cone is self-dual and has a simple projection, simplifying computation after the affine mapping is eliminated.
Smoothing adds a strongly convex proximity function to the primal objective, producing a smooth approximate dual suitable for first-order methods.Larger smoothing parameters improve solver performance at the expense of accuracy, while continuation can recover lost accuracy.
The smoothed dual can often be written as a convex smooth term plus a convex nonsmooth term and solved using generalized-projection iterations.This composite form can simplify central algorithmic computations and supports objectives such as δ∥z∥1.
Nesterov-style acceleration reduces the iteration complexity for ϵ-optimality from O(1/ϵ) to O(1/√ϵ), which is optimal for this problem class.The method recovers approximate primal solutions through the relationship between dual iterates and the associated minimization problem.

1.4 Contributions

The paper’s contribution is the combination of conic duality, smoothing, and optimal first-order methods into flexible algorithms for sparse and low-rank recovery. It also adds technical improvements and supports a broad software-oriented framework.

The conic formulation connects compressed-sensing models to existing conic modeling systems, while the paper applies first-order methods instead of interior-point methods.
Although the individual components are known, their combination yields effective algorithms for compressed-sensing problems, including novel Dantzig selector and LASSO methods.The Dantzig selector can be solved with a reasonable number of applications of A and its adjoint, while the LASSO methods are competitive with SPGL1.
The framework covers total-variation problems, ℓ1-analysis with arbitrary W, and other sparse or low-rank recovery formulations.The authors emphasize flexibility across the compressed-sensing problems listed in the introduction and related models.
The paper introduces an exact-penalty result for certain models, a continuation scheme using more aggressive smoothing, and new step-size control approaches.For models including the Dantzig selector, smoothing can sometimes preserve the exact solution of the original problem.

1.5 Software

The software release is a flexible toolkit rather than a monolithic solver, supporting multiple first-order algorithms, conic wrappers, and model-specific routines.

The release provides building blocks for constructing complete algorithms instead of a single monolithic solver.
Its first level implements projected-gradient and optimal first-order variants by Nesterov and others.
Its second level accepts conic standard-form problems and applies first-order solvers to smoothed dual problems.
Its third level directly solves the paper’s specific models and reproduces the reported experiments.
Sensible defaults are provided for line search, continuation, and related components, while users can substitute their own choices.

1.6 Organization of the paper

The paper develops conic duality and smoothing before specializing the framework to the Dantzig selector and other models, then reviewing first-order methods.

Section 2 develops conic formulations, derives the dual formulation, and details smoothing.
Section 3 applies the framework to derive a new algorithm for the Dantzig selector.
Section 4 instantiates the framework for LASSO, total variation, ℓ1-analysis, and nuclear-norm minimization.
Section 5 reviews first-order methods.

2 Conic formulations

The framework represents convex problems in conic form, derives their duals, and smooths the primal objective to enable accelerated first-order methods while preserving useful structure.

2.1 Alternate forms: Equivalent conic formulations are not unique, and experiments show that their choices can produce different performance with the same algorithms.Some formulations are also simpler to implement, motivating exploration of alternatives for each application.
2.2 The dual: Strict primal and dual feasibility gives zero minimum duality gap and an optimal pair satisfying complementary optimality conditions.
2.3 The differentiable case: When the objective is strongly convex, the dual is differentiable with Lipschitz-continuous gradient, enabling accelerated gradient methods.
2.4 Smoothing: Because the dual is often nondifferentiable or nonfinite, the method adds µd(x) to the primal objective and solves the smoothed model.
2.4 Smoothing: Smoothed minimizers are unique for µ > 0 and converge to a selected original optimum as µ approaches zero.For some models, including the Dantzig selector, the smoothed and original solutions are exactly equal for sufficiently small positive µ.
2.4 Smoothing: Unlike Nesterov’s primal smoothing, the paper’s modified ℓ1 objective preserves sharp vertices that encourage sparse solutions.The compared Nesterov smoothing has quadratic behavior around zero, while the paper’s approach retains the ℓ1 vertices.
2.5 Composite forms: Figure 1 compares the original absolute-value objective with the paper’s modification and Nesterov’s smoothing.
2.5 Composite forms: In composite forms, linear dual variables are removed from the proximity term, while the remaining smooth dual component is handled separately.This produces more accurate approximations and can make generalized projections analytic and less expensive, although iteration predictions are identical.

3 A Novel Algorithm for the Dantzig selector

The paper combines conic duality, smoothing, and optimal first-order updates into a Dantzig selector algorithm with efficient iterations and exact recovery for sufficiently small smoothing.

The Dantzig selector is formulated conically and reduced to a dual problem whose objective is nonsmooth, requiring smoothing.
The composite dual update incorporates an ℓ1 term and can be implemented with soft thresholding.
A quadratic proximity function yields a Lipschitz gradient and expresses the primal minimizer through componentwise soft-thresholding.
Each iteration requires two applications of A and A∗, making the method inexpensive when fast matrix-vector multiplication is available.
O(k^-2) dual convergence is obtained, and the primal iterates converge to the unique solution of the smoothed model.
For sufficiently small µ, the smoothed Dantzig selector solution coincides with the original solution because the model is a linear program.The exact-penalty theorem states this for arbitrary linear programs with a positive semidefinite quadratic perturbation.
In the reported 512 × 4096 DCT example, the smoothing error drops to solver precision below approximately µ ≈0.025.The constructed solution had 129 nonzeros and 60 dB of dynamic range.
The exact penalty property does not generally hold for non-linear-program compressed-sensing models such as LASSO.For small ϵ and µ, the LASSO and its smoothed version are nevertheless described as similar.

4 Further Instantiations

The paper instantiates its conic framework for LASSO, nuclear-norm, ℓ1-analysis, total-variation, and mixed-norm models by deriving compatible dual problems and specialized projections. These models share a generic algorithmic structure based on linear operators, dual recursions, smoothing, and first-order updates.

Generic template: The generic conic algorithm is adapted to specific models by replacing the standard iteration’s primal minimization and dual projection lines.Each variant uses the same computational primitives, although a particular first-order variant may not be best for every model.
LASSO: For LASSO, soft-thresholding supplies the primal projection, while Euclidean-norm dual projections complete the smoothed algorithm.The resulting procedure is presented in an algorithm listing specialized to LASSO.
Nuclear-norm minimization: Nuclear-norm minimization uses singular-value thresholding for the relevant projection, with separate algorithms for LASSO and Dantzig-selector constraints.The smooth gradient has Lipschitz constant at most µ^-1∥A* A∥2.
ℓ1-analysis: The ℓ1-analysis model with arbitrary W is challenging because the generalized projection for f(x) = ∥Wx∥1 lacks an analytical form.A scaled formulation uses α = ∥W∥2/∥A∥2 to balance operator scaling while preserving convergence guarantees.
Total variation and mixed norms: Total-variation minimization is recast as complex ℓ1-analysis using a difference operator D, requiring complex inner products and complex truncation projections.The same strategy extends to weighted combinations of ∥Wx∥1 and ∥x∥TV by introducing a direct product of three cones.

5 Implementing first-order methods

The implementation section develops composite-form first-order methods, practical step-size and continuation strategies, and variants for exploiting strong convexity. It emphasizes both provable rates and practical trade-offs, including warm starts and numerical stability.

Composite first-order methods: The conic models are treated as unconstrained composite problems with a smooth convex term and a nonsmooth convex term, solved through generalized projections.Convex constraints can be represented through indicator functions in the nonsmooth term.
Convergence rates: Simple methods require O(L/ϵ) iterations for ϵ accuracy, whereas optimal first-order methods require O(√(L/ϵ)) iterations.The rates follow from the Lipschitz-based upper-bound condition used in the generalized projection.
Algorithm variants: The implementation includes projected-gradient and five optimal first-order variants, including TS, LLM, AT, N83, and GRA.The variants differ in their update formulas while preserving the same basic computational structure.
Step-size adaptation: Global Lipschitz constants can produce overly conservative step sizes, while excessive reduction may cause divergence near a sharp convergence-divergence transition.The paper therefore examines practical step-size control and reports cancellation problems in a standard line-search test at high accuracy.
Continuation: Accelerated continuation can achieve O(j^-2) convergence versus O(j^-1) for standard continuation, but complicated primal updates may weaken dual warm starts.With fixed smoothing and simple center updates, the previous dual variable remains a useful initial guess.
Strong convexity: Strong convexity can yield linear convergence: restart lets AT approach N83 performance, while GRA eventually overtakes unrestarted AT.The optimal restart interval depends on the strong-convexity ratio, although linear convergence can persist with suboptimal intervals.

6 Numerical experiments

Numerical experiments evaluate the framework across sparse recovery, denoising, and matrix completion, showing that performance depends on algorithm variant, continuation, restart strategy, and problem structure. The methods achieve competitive accuracy and computational performance, while no single algorithm dominates every setting.

Dantzig selector: Backtracking improved AT’s 10^-4 convergence from more than 3000 to fewer than 2000 calls to A or A∗.With backtracking, AT and TS also exhibited less oscillation than the other variants.
Dantzig selector: A restart interval of 200 iterations enabled AT to reach 10^-4 relative error after approximately 1000 linear operations and identify the correct support after a few hundred.Other variants also improved with restart, although two-projection methods took about 50% longer than one-projection methods.
LASSO: AT with accelerated continuation solved the LASSO test significantly faster than SPGL1, while both methods achieved several digits of accuracy in a few hundred applications of A and its adjoint.In the wavelet test, SPGL1 was often slightly better, especially for large ϵ, although AT with continuation reached high accuracy in fewer than 1000 operations.
Wavelet analysis with total-variation: TV minimization achieved 30.9 dB PSNR, while adding wavelet analysis achieved 31.0 dB; both outperformed the wavelet-analysis reconstruction alone by PSNR and visual inspection.The wavelet-analysis, TV, and combined models took 26, 37, and 30 iterations, respectively.
Matrix completion: In noiseless matrix completion, AT initially outperformed GRA, but GRA overtook it at moderate precision because of linear convergence; restart substantially improved AT.With a restart interval of 50 iterations, AT approached but did not overtake GRA.
Matrix completion: Continuation substantially improved noisy matrix completion, requiring only 100 SVDs to reach 10^-2 relative error.The experiment used a 50×45 rank-20 matrix with 67% of entries sampled and 30 dB SNR.

7 Software: TFOCS

TFOCS is a publicly available collection of templates and routines for constructing customized first-order solvers for convex models. Its implementation separates reusable solver components from problem-specific operators, supporting efficient solutions for Dantzig selector, LASSO, total-variation, and related models.

Software package: TFOCS provides templates and building blocks for constructing efficient, customized solvers rather than one monolithic solver.The package includes a user guide and examples covering popular problem formulations.
Dantzig selector implementation: A smoothed Dantzig selector solver combines a smooth dual component, a generalized projection, soft-thresholding, and an Auslender/Teboulle first-order variant.The implementation uses functions for the smooth objective and nonsmooth generalized projection before calling the AT solver.
Dantzig selector implementation: Soft-thresholding computes both the smooth Dantzig component and its generalized projection, with thresholds determined by the smoothing or step-size parameters.The supplied routines apply SoftThreshold in both g_dantzig and h_dantzig.
Implementation flexibility: Problem-specific linear operators can be rewritten to exploit fast structures such as Fourier transforms without changing the solver template.The solver interacts with A and y through problem-specific function calls, while TFOCS can automate linear-operator management.
Implementation flexibility: Complete solvers for Dantzig selector, LASSO, total-variation, and other models use the same lower-level efficiencies and templates.The lower-level templates are intended to extend beyond the specific conic form discussed in the paper.

8 Conclusion

The paper presents flexible first-order templates for convex cone problems, including models lacking efficient large-scale algorithms. The authors report stable, efficient implementations and competitiveness with state-of-the-art LASSO methods, while identifying several directions for future improvement.

Contributions: The framework handles a variety of convex cone problems, including problems that previously lacked efficient algorithms.Its primary reported merit is flexibility across sparse recovery and low-rank models.
Contributions: The implementation introduces ideas intended to produce novel, stable, and efficient algorithms.These implementation contributions support the framework's application to large-scale models.
Results: The LASSO implementation appears surprisingly competitive with the state of the art.This comparison concerns an intensively studied problem.
Software flexibility: The templates support interchangeable solvers and a wide variety of formulations, enabling direct benchmarking and broader sparse-recovery use.The authors aim to improve usability for nonexperts and provide sensible default parameters.
Future work: Future work includes improving smoothing-parameter selection, line search, expensive-projection management, scaled norms, and continuation with inexact solves.The authors state that these issues will be addressed in subsequent work.

A Exact Penalty

The exact-penalty analysis studies smoothing by adding a strongly convex quadratic term to the primal objective, thereby smoothing the dual. For certain problems, sufficiently small smoothing preserves an optimizer of the unsmoothed problem.

Exact-penalty principle: The framework smooths the dual by adding a strongly convex term to the primal objective, unlike penalty methods that eliminate constraints.For some choices, the smoothed and unsmoothed problems are nearly equivalent for positive smoothing.
Proof setting: The analysis considers a linear program over a convex polyhedron and a perturbed objective containing a quadratic proximity term.The quadratic term is measured using a positive semidefinite matrix Q.
Proof setting: The selected point x⋆ is an optimal point of the original problem minimizing the Q-distance to a reference point x0 among all original optimizers.When Q is the identity, this is the usual projection onto the optimal solution set.
Proof mechanism: The proof decomposes feasible directions into convex combinations of extreme points and nonnegative combinations of extreme directions.The argument distinguishes nonoptimal vertices and directions with strictly positive objective increase.
Proof conclusion: Choosing µ sufficiently small makes the perturbation's directional contribution nonnegative, so x⋆ remains a local minimizer of the smoothed objective.The bound uses positive minimum cosine terms and the quantity µQ = µ∥Q(x⋆−x0)∥2.

B Creating a Synthetic Test Problem

The paper constructs synthetic test problems with exact or machine-precision solutions to evaluate algorithms when ground truth is otherwise unavailable. The construction uses primal-dual optimality conditions and a small matrix correction to clean numerical solutions.

Motivation: Interior-point solvers provide mature and accurate reference solutions, but their poor scaling and limited use of fast matrix-vector products motivate synthetic exact solutions.This is especially relevant when the true solution is not known analytically.
Optimality conditions: Basis pursuit testing uses the dual constraint ∥A∗λ∥∞≤1 together with KKT conditions to characterize primal-dual optimality.The support T = supp(x⋆) appears in the optimality conditions.
Construction: The procedure begins by choosing A and y, optionally setting y = A˜x for a signal with prescribed properties such as sparsity or image-derived wavelet coefficients.A high-accuracy primal-dual solve then produces candidate primal and dual solutions.
Cleaning up solutions: A diagonal correction D modifies A so the dual certificate matches sign(x⋆) on the support and stays strictly bounded off the support.When the original solve is accurate, D remains close to the identity.
Cleaning up solutions: The corrected primal-dual pair becomes an exact solution for the basis-pursuit problem using ˜A and y under the stated full-column-rank assumption.Positive entries in D preserve the sign of x⋆.
Other models: For LASSO and Dantzig selector experiments, exact smoothed solutions can be obtained, while the unsmoothed solution is estimated through decreasing smoothing and a sufficiently small µ.This procedure exploits the exact-penalty property described earlier.