The solution path of the generalized lasso

By Robert Tibshirani, Jonathan E. Taylor. 2010

921 citations recorded by the source corpus.

We present a path algorithm for the generalized lasso problem. This problem penalizes the $\ell_1$ norm of a matrix D times the coefficient vector, and has a wide range of applications, dictated by the choice of D. Our algorithm is based on solving the dual of the generalized lasso, which greatly facilitates computation of the path. For $D=I$ (the usual lasso), we draw a connection between our approach and the well-known LARS algorithm. For an arbitrary D, we derive an unbiased estimate of the degrees of freedom of the generalized lasso fit. This estimate turns out to be quite intuitive in many applications.

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Additive models with trend filtering (2017, background): “Of course, additive trend filtering is a not a linear smoother; however, it is a particular type of generalized lasso estimator, and degrees of freedom for such a class of estimators is well-understood [Tibshirani and Taylor, 2011, 2012].”
A Robust Regularization Path Algorithm for $\nu $ -Support Vector Classification (2017, background): “However, most solution algorithms [4]–[7], [9] mainly depend on Assumption 1.”
Regression shrinkage and selection via the lasso: a retrospective (2011, neutral): “They also showed that the number of degrees of freedom is the number of unique values of ŷi in the solution, using results from Tibshirani and Taylor (2011).”
Numerical construction of Green's functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations (2012, background): “We note that this is the “generalized lasso” problem described in [134].”
Degrees of freedom and model search (2014, background): “…for an entirely arbitrary predictor matrix X (not necessarily having columns in general position), see Tibshirani & Taylor (2012); analogous results also exist for the generalized lasso problem (special cases of which are the fused lasso and trend filtering), see Tibshirani & Taylor (2011, 2012).”
A Direct Algorithm for 1-D Total Variation Denoising (2013, background): “homotopy, algorithms have been proposed for l1 penalized problems; they can find the smallest value of λ and the associated x in (1) such that x has at most m segments, with complexity O(mN ) [27, 37, 39, 18, 40, 41].”
Handbook of Big Data (2016, background): “For certain specific loss functions and penalties, solutions for all λ ≥ 0 have been worked out (Osborne et al., 2000; Efron et al., 2004; Tibshirani and Taylor, 2011).”
A LASSO FOR HIERARCHICAL INTERACTIONS (2012, methodology): “The structure of our proof is based on (Ryan) Tibshirani and Taylor (2011, 2012).”
Exact post-selection inference for the generalized lasso path (2018, methodology): “The boundary set constructed by the dual path algorithm, Algorithm 1, has the following interpretation for the graph fused lasso problem [37, 1].”
The generalized lasso is reducible to a subspace constrained lasso (2013, methodology): “In this case, the generalized lasso reduces to a lasso in agreement with the result in [13].”
Asynchronous Distributed ADMM for Consensus Optimization (2014, methodology): “In this section, we perform classification experiments with a variant of the generalized lasso model (Tibshirani & Taylor, 2011): minx 1L ∑L i=1 `i(x) + λ‖Ax‖1, where L is the number of samples, `i is the logistic loss (which is more appropriate than the square loss in classification), λ is the…”
The Generalized Lasso Problem and Uniqueness (2018, methodology): “As explained in Tibshirani and Taylor (2011), the generalized lasso problem (1) encompasses several well-studied problems as special cases, corresponding to different choices of D, e.g., the lasso (Tibshirani, 1996), the fused lasso (Rudin et al., 1992; Tibshirani et al., 2005), trend filtering…”
Multiple predicting K-fold cross-validation for model selection (2018, background): “…Friedman, Hastie, and Tibshirani (2010), Simon, Friedman, Hastie, and Tibshirani (2011), glmpath for Park and Hastie (2007), genlasso for Tibshirani and Taylor (2011), lqa for Zou (2006), elasticnet for Zou and Hastie (2005), ncvreg for Fan and Li (2001), and quantreg for Wu and Liu…”
Stochastic Alternating Direction Method of Multipliers (2013, background): “An important class of these problems is called the generalized lasso (Tibshirani & Taylor, 2011): minEξ [1 2 ( l − xT s )2 ] + ‖Fx‖1, (17) where the linear transformation F ∈ Rf×d1 encodes the structural prior of a specific problem.”