Applications of l 1 regularisation

Abstract

The lasso algorithm for variable selection in linear models, intro- duced by Tibshirani, works by imposing an l1 norm bound constraint on the variables in a least squares model and then tuning the model estimation calculation using this bound. This introduction of the bound is interpreted as a form of regularisation step. It leads to a form of quadratic program which is solved by a straight-forward modifica-tion of a standard active set algorithm for each value of this bound. Considerable interest was generated by the discovery that the complete solution trajectory parametrised by this bound is piecewise linear and can be calculated very effciently. Essentially it takes no more work than the solution of either the unconstrained least squares problem or the quadratic program at a single bound value. This has resulted in the study both of the selection problem for different objective and constraint choices and of applications to such areas as data compres- sion and the generation of sparse solutions of very under-determined systems. One important class of generalisation is to quantile regression estimation problems. The original continuation idea extends to these polyhedral objectives in an interesting two phase procedure which involves both the constrained and Lagrangian forms of the problem at each step. However, it is significantly less computationally effective than is the original algorithm for least squares objectives. In contrast, the piecewise linear estimation problem can be solved for each value of the l1 bound by a relatively effcient simplicial descent algorithm, and that this can be used to explore trajectory information in a manner which is at least competitive with the homotopy algorithm in this context. The form of line search used in the descent steps has an important bearing on the effectiveness of the algorithm. A comparison is given between the relative performance of the simplicial descent algorithm used and an interior point method on the piecewise linear estimation problem.