Source-linked AI summary
A path algorithm for the Fused Lasso Signal Approximator
Holger Hoefling
TL;DR
The paper addresses efficient computation of Fused Lasso solution paths, extending sparse regression with penalties that fuse neighboring coefficients. It develops path algorithms for the one-dimensional FLSA and a rank(X) = p general Fused Lasso, with simulations showing speed and accuracy advantages over standard convex solvers for FLSA. The general algorithm is restricted because rank(X) < p can produce discontinuous λ2 paths.
Problem
The Fused Lasso requires solutions across two penalty parameters, motivating efficient path computation for ordered and graph-structured coefficients.
Method
The paper develops path algorithms for one-dimensional and general Fused Lasso models, using a full λ2 path with soft-thresholding to obtain λ1 ≠ 0 solutions in the one-dimensional case.
Results
The algorithms compare favorably in speed and stored information, with the path algorithm much faster than standard convex solvers for the FLSA while retaining useful accuracy.
Takeaways & Limitations
The path representation makes it easy and quick to extract solutions for additional penalty parameter values and gathers more path information than alternative methods.
Takeaways & Limitations
The general path algorithm is restricted to rank(X) = p because rank(X) < p can yield discontinuities in the solution path with respect to λ2.
Abstract
from arXiv · showhide
The Lasso is a very well known penalized regression model, which adds an $L_{1}$ penalty with parameter $λ_{1}$ on the coefficients to the squared error loss function. The Fused Lasso extends this model by also putting an $L_{1}$ penalty with parameter $λ_{2}$ on the difference of neighboring coefficients, assuming there is a natural ordering. In this paper, we develop a fast path algorithm for solving the Fused Lasso Signal Approximator that computes the solutions for all values of $λ_1$ and $λ_2$. In the supplement, we also give an algorithm for the general Fused Lasso for the case with predictor matrix $\bX \in \mathds{R}^{n \times p}$ with $\text{rank}(\bX)=p$.
1 Introduction
The Fused Lasso adds a neighboring-coefficient penalty to sparsity-inducing regression, making it useful for ordered, piecewise-constant signals and structured data such as CGH measurements and images. The paper develops path algorithms for one-dimensional and general graph-based forms, with exact full-path computation and a rank restriction for the general predictor case.
- Motivation: The Lasso promotes sparse or shrunken regression coefficients through penalties added to the loss function.The Fused Lasso extends this framework with an additional penalty on neighboring coefficient differences.
- Motivation: The neighboring-difference penalty shrinks adjacent coefficients together and tends to make them exactly equal, favoring signals that are constant over intervals and change in jumps.This structure is especially relevant when nearby coefficients in the true model are closely related.
- FLSA applications: The one-dimensional FLSA assumes X = I and treats each coefficient as an estimate of an ordered measurement, such as a chromosomal position in CGH data.The method uses neighboring differences to reduce noise and improve estimation when genomic gains or losses occur across regions and in jumps.
- FLSA applications: In lung-cancer CGH data, FLSA estimates with λ1 = 0 and λ2 = 2 show measurements averaging below 0 from around position 150, indicating DNA loss in that region.This is presented as an example application of the one-dimensional FLSA.
- FLSA applications: The Fused Lasso also supports image reconstruction by penalizing differences between neighboring coefficients on a two-dimensional grid.The example contrasts a true image, a noisy image, and a Fused-Lasso reconstruction.
- General Fused Lasso: In the general formulation, coefficients correspond to graph nodes and every difference across an edge is penalized; the paper develops path algorithms for general graphs and rank(X) = p.For rank(X) < p, the solution path with respect to λ2 may have discontinuities, so the paper does not develop a path algorithm for that case.
2 One-dimensional Fused Lasso Signal Approximator
The one-dimensional FLSA path algorithm computes the solution by tracking neighboring coefficient groups as they fuse while increasing λ2. For λ1 > 0, solutions follow by soft-thresholding, and the resulting path is computationally efficient and faster than the compared alternatives.
- Path construction: For X = I, solutions at any λ1 > 0 are obtained by soft-thresholding the λ1 = 0 solution for the same λ2.This soft-thresholding result also applies to FLSA on arbitrary graphs.
- Algorithm representation: Fused sets partition the ordered coefficients into contiguous intervals whose members share one coefficient value, while adjacent sets have distinct values.The algorithm represents successive fusions in a binary tree, supporting retrieval of a solution at a chosen λ2.
- Path construction: In the one-dimensional FLSA, fused coefficient groups cannot split as λ2 increases, so the solution path is piecewise linear with breakpoints at fusion events.The no-splitting property enables sequential computation of the next hitting time.
- Path construction: The algorithm starts at λ2 = 0 with βk = yk, increases λ2, and merges neighboring coefficient sets when their values become equal.Each merged set is subsequently treated as a single variable as λ2 increases.
- Efficiency and evaluation: The one-dimensional path algorithm has complexity n log(n) and uses O(n) memory for compact solution-path storage.The stored path object also permits rapid extraction of solutions for additional λ2 values.
3 General Fused Lasso Signal Approximator
The general FLSA algorithm handles arbitrary graph structures by tracking connected fused-variable sets, which may merge or split as λ2 increases. It follows the resulting piecewise-linear path exactly, with an approximate variant that trades limited accuracy for speed.
- The general FLSA penalizes differences across every edge of an arbitrary undirected graph G.
- Unlike the one-dimensional case, fused groups may split as λ2 increases, so the algorithm detects both fusion and splitting breakpoints.
- For general graphs, fused-variable sets must be connected subgraphs rather than one-dimensional intervals.
- Skipping split checks for fused sets of size K or larger substantially speeds computation while causing only a modest accuracy trade-off for moderate K.
- For 2-dimensional simulations, the path and component-wise algorithms were much faster than CVX; K around 500–1000 produced high accuracy while remaining faster than CVX.
4 Conclusion
The paper presents path algorithms for the FLSA and general Fused Lasso, reports advantages over standard convex solvers, and identifies extensions for weighted penalties and dense graphs.
- The algorithms cover the one-dimensional and general forms of the Fused Lasso Signal Approximator.
- The authors report advantages in speed and stored information compared with other available methods, especially standard convex solvers for the FLSA.
- The paper proposes extending the penalty to allow separate weights for each summand.
- The current FLSA algorithm is not optimized for graphs with large numbers of edges, motivating future clique-aware improvements.
- Implementations are planned as an R package on CRAN and the authors’ website.
Signal Approximator
The supplied passage identifies the paper as an arXiv version dated 3 October 2009.
- The document is identified as arXiv:0910.0526v1.
- The supplied metadata dates this version to 3 Oct 2009.
- The passage is bibliographic rather than methodological or empirical.
1 Introduction
The supplement provides proofs and further results beyond the article’s scope, including complexity analysis and a proof that fused sets do not become unfused as λ2 increases.
- The supplement supplies proofs and further results omitted from the article because of size and scope constraints.
- It discusses the algorithm’s computational and memory complexity.
- It gives an alternative proof that fused variable sets do not become unfused when λ2 increases.
2 One dimensional FLSA
The one-dimensional FLSA path algorithm starts from the known λ2 = 0 solution, tracks piecewise coefficient paths, and merges neighboring fused sets until the full path is obtained.
- Computational complexity: The algorithm has computational complexity O(n log(n)) for obtaining the entire one-dimensional solution path.There are at most n − 1 iterations because the number of fused sets decreases by one per iteration.
- Path storage: The binary-tree representation requires memory that grows linearly in n rather than storing coefficient vectors for every fusion value.
- Path storage: The solution path is stored in a binary tree whose nodes record fusion values of λ2 and updated coefficients.Starting from n leaves, each fusion creates a parent node for the two merged groups.
- Fusion property: Theorem 2 states that once adjacent coefficients fuse, they remain fused for every larger λ2.
3 The general Fused Lasso Signal Approximator
The general FLSA path algorithm updates fused groups as λ2 changes, using maximum-flow conditions to determine valid solutions and group changes. Fusion and splitting cannot immediately reverse, ensuring finite convergence.
- Group updates: Maximum-flow graphs determine whether fused groups satisfy the required capacity conditions and identify groups that must split.Flows from the source and to the sink encode the conditions used in the solution proof.
- Correctness: The algorithm verifies each proposed solution by satisfying the subgradient equations for every fused group over a λ2 interval.The proof establishes that the constructed solution minimizes the loss function.
- Group updates: The grouping remains valid after splitting because neighboring groups preserve distinct coefficient values and compatible sign conditions over a subsequent interval.The proof checks both coefficient ordering and the signs of connecting-edge differences.
- Convergence: Groups split at λ2 cannot immediately merge again at the same breakpoint, preventing immediate reversal of fusion or splitting decisions.This property rules out returning directly to the starting partition.
- Convergence: Because there are finitely many possible sets and no infinite fusion-splitting cycles, the algorithm converges after finitely many iterations.The non-reversal property supplies the finite-iteration argument.
4 Path algorithm for the General Fused Lasso
The paper extends path computation from the FLSA to the general Fused Lasso with a full-rank predictor matrix and graph-defined coefficient differences. The general algorithm handles fixed λ1 while tracing the solution path in λ2.
- Scope: The general Fused Lasso extension targets predictor matrices X ∈ R^n×p with rank(X) = p.The loss uses a graph G to define penalties on differences between connected coefficients.
- Scope: Unlike the X = I case, solutions for all λ1 cannot be obtained by soft-thresholding a single λ1 = 0 path.The general method therefore does not reduce all (λ1, λ2) combinations to one path.
- Algorithm design: The algorithm uses active and inactive sets of fused variables in a LARS-like procedure to incorporate the coefficient penalty λ1.Fused sets are tracked according to whether their common coefficient is zero.
- Scope: When rank(X) < p, the solution path with respect to λ2 may have discontinuities, so the paper restricts its algorithmic development to full-rank X.A one-observation, two-predictor example exhibits a jump at λ2 = 1/3.
- Algorithm design: The section develops a piecewise-linear λ2 path and gives the complete algorithm for fixed λ1.The path is described through slopes and breakpoint changes.
4.1 Sets of fused variables and active sets
For the general Fused Lasso, fused variables are organized into connected groups that share coefficients and signs, while each group is marked active or inactive according to whether its coefficient is nonzero.
- Active and inactive sets: Because λ1 cannot be removed by soft-thresholding in the general case, the algorithm must track the additional coefficient penalty directly.This motivates distinguishing active and inactive fused sets.
- Active and inactive sets: Variables in the same fused set share both a coefficient value and sign, and an entire fused set is active or inactive together.Active means the common coefficient is nonzero; inactive means it equals zero.
- Validity conditions: A valid grouping covers all variables, preserves distinct neighboring groups over intervals, and keeps each group connected in the induced graph.These conditions extend the earlier fused-set definition to account for inactive coefficients.
- Active and inactive sets: Active sets are defined using a forward-looking condition for λ2 values immediately after a breakpoint.The distinction from evaluating activity exactly at the breakpoint is mainly technical for the algorithm and proofs.
4.2 Derivation of the algorithm
The derivation constructs a constrained problem over fused and active sets, computes local path slopes, and identifies breakpoints where grouping or activity changes. Fusion, splitting, activation, and deactivation rules then assemble the path algorithm.
- Constrained formulation: The constrained loss uses XF for fused groups and XF,A after removing inactive groups, while XA and XN separate active and inactive coefficients.Assuming the sets are correct, minimizing this constrained loss also minimizes the original loss.
- Constrained formulation: The optimality condition is written compactly as ∂βF = −XF,Ty + XF,TXFβF + λ1a + λ2b = 0.The vectors a and b encode the coefficient and fusion-penalty subgradient contributions.
- Path derivatives: Full rank ensures (XF,A)^T XF,A is invertible, allowing the algorithm to calculate derivatives and slopes for the solution path.These derivatives support determining when fused sets activate, deactivate, split, or fuse.
- Path derivatives: Maximum flow determines the derivatives of τkl = λ2tkl, using the maximal flow between nodes within each fused set.This reuses the maximum-flow construction from the general FLSA algorithm.
- Update rules: The algorithm fuses equal active-state groups, splits groups failing the maximum-flow condition, and iterates these updates until stable.Additional rules activate inactive groups and inactivate active groups when their breakpoint conditions occur.
- Update rules: The update rules produce valid fused and active sets, completing the necessary steps for the general Fused Lasso path algorithm.Proposition 2 establishes validity after changing grouping and activity status.
4.3 Outline of the algorithm
The general Fused Lasso path algorithm starts from a Lasso solution at λ2 = 0 and traces changes in grouped coefficients as λ2 increases. At each breakpoint, it updates derivatives, flow constraints, and active groups, but is substantially more complex than the FLSA case.
- Initialization: The algorithm initializes λ2 = 0, treats each variable as a separate group, and obtains starting coefficients and subgradients by solving a Lasso problem.These starting values complete the initialization for the general path algorithm.
- Path updates: At each iteration, it updates β, s, and t, computes their derivatives, solves maximum-flow problems, and determines the next breakpoint.The next event is selected from hitting, violation, activation, and deactivation times.
- Event handling: The algorithm fuses groups at hitting times, splits groups at violation times, and activates or deactivates sets when their corresponding event times are reached.The number of groups is adjusted after fusion or splitting events.
- Computational complexity: Unlike the FLSA case, changes in one active group can affect the paths of all other active groups, requiring their derivatives and maximum-flow problems to be recomputed.Only inactive groups can be treated as in the FLSA case.
- Computational complexity: The general Fused Lasso algorithm is computationally much more complex than FLSA, so implementations are limited to FLSA cases while the general implementation is deferred.The paper identifies the one-dimensional FLSA as having more immediate applications.
4.4 Proof of Theorem 4.2.1
The theorem proof verifies that the maximum-flow construction satisfies the subgradient equations along the proposed path. It concludes by showing that the required flow balances hold at every regular node.
- Subgradient verification: Because the current coefficients are assumed optimal, the proof reduces to showing that the subgradient equations equal zero over the interval under consideration.The argument checks the relevant conditions for every node or coefficient index.
- Flow formulation: The definition of node push converts the subgradient condition into an equivalent flow statement.This links the optimization proof to the maximum-flow representation.
- Flow formulation: All source flows are at maximum capacity, and antisymmetry of tkl implies the corresponding balance for flows entering the sink.The proof then uses flow conservation at regular nodes.
- Conclusion: Flow conservation at every regular node establishes the required nodewise conditions and completes the theorem proof.The proof concludes after verifying these balances.
4.5 Proof of Proposition 4.2.3
The proposition proof establishes that the path algorithm handles fusions, splits, and set activation or deactivation without invalid transitions. Its argument relies on continuity and piecewise linearity of the solution path, together with feasible flow constructions.
- Path regularity: Under rank(X) = p, strict convexity makes β(λ2) continuous, while the loss is affine in λ2; s(λ2) is likewise continuous and piecewise linear.These regularity properties support the event-handling arguments throughout the proof.
- Set validity: When two sets share coefficient and subgradient values, derivative and edge-sign conditions determine whether they fuse or remain valid as separate sets.The proof uses tkl = ±1 between distinct sets and verifies the sign restriction after the transition.
- Set validity: A feasible flow in the constructed graph guarantees that the within-set variables tkl satisfy their required bounds.This establishes existence of admissible subgradient variables for each group.
- Fusions and splits: A finite sequence of fusions and splits follows once an immediately repeated split after a fusion is ruled out.The proof uses the finite number of nodes and analyzes a single breakpoint, with perturbation handling coincident breakpoints.
- Fusions and splits: After two groups fuse, their derivative ordering forces them to remain fused over a nonzero interval rather than split immediately.Continuity and the assumed ordering before the breakpoint yield the contradiction needed for this result.
- Fusions and splits: The fused grouping remains optimal over that interval, and differentiating the associated linear equations produces a feasible maximum flow, so the algorithm does not force a premature split.The constructed flows keep source edges at maximum capacity.
- Set transitions: An inactive set reaching its boundary with positive derivative must activate, because remaining inactive would contradict the subgradient sign condition.The proof then establishes the resulting coefficient and activity conditions.
- Set transitions: An active set with negative derivative becomes zero over a right-hand interval and therefore must deactivate rather than violate continuity of its subgradient.The argument excludes a negative coefficient because it would force a discontinuous subgradient value.