A simple algorithm for fast and accurate L1-penalized least squares
Andrew Barron and Cong Huang
Yale University
Abstract
We introduce L1-PENALIZED GREEDY PURSUIT, a simple algorithm for
minimizing squared error with a L1 penalty on the coefficients of linear
combination. Terms are introduced iteratively. Given the previous fit,
the next term and its coefficient are chosen such that in linear
combination with the previous fit the criterion is optimized. After k
such iterations the criterion is within order 1/k of the minimum. Explicit
bounds are given that hold for arbitrary data-sets. The risk of the
estimator is also characterized in a similar way under statistical
assumptions. We discuss the relationship of this algorithm to early work
on greedy algorithms by Jones, Barron, Mallat, Lee-Bartlett-Williamson,
and Zhang and to other work on L1-penalized optimization by Tibshirani,
Chen and Donoho, Zhang, Juditsky and Nemirovski, Bunea-Tsybakov-Wegkamp,
Efron and others.