A Path Algorithm for the Fused Lasso Signal Approximator

By Holger Hoefling. 2009

261 citations recorded by the source corpus.

The Lasso is a very well-known penalized regression model, which adds an L1 penalty with parameter λ1 on the coefficients to the squared error loss function. The Fused Lasso extends this model by also putting an L1 penalty with parameter λ2 on the difference of neighboring coefficients, assuming there is a natural ordering. In this article, we develop a path algorithm for solving the Fused Lasso Signal Approximator that computes the solutions for all values of λ1 and λ2. We also present an approximate algorithm that has considerable speed advantages for a moderate trade-off in accuracy. In the Online Supplement for this article, we provide proofs and further details for the methods developed in the article.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Fused Lasso Additive Model (2014, methodology): “Several algorithms for solving (3) have been proposed (Hoefling 2010; Liu, Yuan, and Ye 2010; Johnson 2013).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “The Lovász extension of cuts in an undirected graph, often referred to as the total variation, has now become a classical regularizer in signal processing and machine learning: given a graph, it will encourages solutions to be piecewise-constant according to the graph [100, 99].”
Penalized classification using Fisher’s linear discriminant (2011, background): “• If ˜ Σ w is a diagonal estimate for Σ w then (22) is a diagonal fused lasso problem, for which fast algorithms have been proposed (see e.g. Hoeﬂing, 2009; Johnson, 2010).”
Clusterpath: an Algorithm for Clustering using Convex Fusion Penalties (2011, methodology): “For each of these subproblems, we can exploit the FLSA path algorithm (Hoefling, 2009).”
Seismic sparse-spike deconvolution via Toeplitz-sparse matrix factorization (2016, methodology): “Then, substituting equation 20 into equation 13 gives the following Fused Lasso problem: Jα ¼ minα 1 2 k ~y − ~Rαk22 þ βkαk1 þ β1 X k jakþ1 − akj; (21) which can be solved by any of the standard methods (e.g., Hoefling, 2010; Liu et al., 2010; Ye and Xie, 2011).”
A Direct Algorithm for 1-D Total Variation Denoising (2013, background): “Besides, path-following, a.k.a. homotopy, algorithms have been proposed for ℓ 1 penalized problems; they can ﬁnd the smallest value of λ and the associated x in (1) such that x has at most m segments, with complexity O ( mN ) [18], [29], [40], [42]–[44].”
Accelerated Attributed Network Embedding (2017, background): “The pioneer work of network lasso can also be traced back to the fused lasso [12, 37] and convex clustering [28] problems.”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, methodology): “For all binary variables, one can show that this is equivalent to the lasso-penalized pseudo-likelihood for the Ising model (see Hoefling and Tibshirani (2009) and Exercise 9.”
The joint graphical lasso for inverse covariance estimation across multiple classes (2011, background): “(2009b), and Kolar et al. (2010). These papers deal with both continuous and binary data.”
Machine Learning for Precision Medicine. (2020, unknown): “, 2009) JG(β) = a‖β‖1 + (1− a) ∑ i∼j |βi − βj | (Hoefling, 2010)”
Tensor Regression Networks (2017, methodology): “Additional regularizers such as Lasso (l1) Hoefling (2010); Tibshirani and Taylor (2011) can provide further advantages, especially in the face of noisy inputs.”
Exact post-selection inference for the generalized lasso path (2018, background): “[13], Chambolle and Darbon [5], Hoefling [18], Tibshirani and Taylor [37], Sharpnack et al.”
An efficient algorithm for a class of fused lasso problems (2010, methodology): “To efﬁciently solve FLSA corresponding to a pair of λ 1 and λ 2 , we propose to reformulate it as the problem of ﬁnding an “appropri-ate" subgradient of the fused penalty at the minimizer, and develop a Subgradient Finding Algorithm (SFA).”