the lasso – Optimization Online

Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

Published: 2010/09/23

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 … Read more

When LP is not a good idea – using structure in polyhedral optimization problems

Published: 2003/12/10

Michael Osborne

Convex Optimization, Linear Programming, Statistics active set method, homotopy method, l_1 estimation, line-search, linear programming, rank regression, simplicial algorithm, structure functional, support vector regression, the lasso

It has been known for almost 50 years that the discrete l_1 approximation problem can be solved effectively by linear programming. However, improved algorithms involve a step which can be interpreted as a line search, and which is not part of the standard LP solution procedures. l_1 provides the simplest example of a class of … Read more