Efficient Implementations of the Generalized Lasso Dual Path Algorithm

The term "generalized" refers to the fact that problem (1) reduces to the standard lasso problem (Tibshirani 1996, Chen et al. 1998) when D I, but yields different problems with different choices of the penalty matrix D. We will assume that X has full column rank (i.e., rank(X) p), so as to ensure a unique solution in (1) for all values of λ. Our main contribution is to derive efficient implementations of the generalized lasso dual path algorithm of Tibshirani & Taylor (2011). This algorithm computes the solution ˆβ(λ) in (1) over the full range of regularization parameter values λ [0,). We present an efficient implementation for a general penalty matrix D, as well as specialized, extra-efficient implementations for two special classes of generalized lasso problems: fused lasso and trend filtering problems. The algorithms that we describe in this work are all implemented in the genlasso R package, freely available on the CRAN repository (R Development Core Team 2008). We note that the fused lasso and trend filtering problems are known, well-established problems (early references for fused lasso are Land & Friedman (1996), Tibshirani et al. (2005), and early works on trend filtering are Steidl et al. (2006), Kim et al. (2009)). These problems are not original to the generalized lasso framework, but the latter framework simply provides a useful, unifying perspective from which we can study them. We give a brief overview here; see the aforementioned references for more discussion, or Section 2 of Tibshirani & Taylor (2011), and also Section 6 of this paper, for examples and figures.