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.