Edit on GitHub

Fused Lasso on Trees

This is the documentation of the Julia part. For other languages, have a look at

TreeLas.TreeLas — Module

Fused Lasso Solver for tree graphs, i.e. we aim to minimize the following objective function

\[f(x) = \frac{1}{2} \sum_{i=1}^n \mu_i (x_i - y_i)^2 + \sum_{(i,j) \in E} \lambda_{ij} |x_i - x_j|\]

Hereby is

  • $y_i$ the input signal for node $i$,
  • $\mu_i \geq 0$ is the node weight for node $i$,
  • $E$ the edges of a tree, and
  • $\lambda_{ij} > 0$ is the edge weight for $(i,j)$.
source

Exact Tree Solver

The exact solver is found in the module TreeLas.TreeDP.

General Graphs

Furtheron, we presend a general graph solver that iteratively picks a subtree and block-optimizes it.

TreeLas.MGT — Module

Maximum Gap Tree

Also called Gap Tree Lasso (GapLas).

In the central function gaplas, a tree having the largest gap values (computed by gap_vec!) is selected. The non-tree edge-flows are forwarded into the input y. Then the tree solver is used and the tree-edges are updated.

Graph Indexes

For the different steps, several indexes are necessary

  1. Dual.gap_vec! needs to access every edge once.

  2. Prim's minimum spanning tree: IncidenceIndex providing outgoing edges for a node (i.e. every edge is included in two node's adjacency lists)

  3. Once the tree has been determined we need to have a ChildrenIndex from the parent (e.g. for dfs_walk); also needed for computing the Queues layout (parenthesis tree representation) and the processing order.

source
TreeLas.MGT.enumerate_typed_edges — Method
traverse_edges(func, edges, π)

Call for every edge (u, v) enumerated by i the function

func(istree, i, u, v)

whereby istree tells whether the edge is a tree edge. If it is a tree edge, u is the child of v.

source
TreeLas.MGT.extract_non_tree! — Method
extract_non_tree!(graph, y, λt, π, α, λ)

Iterate over all edges of grapy (weighted by λ) and do the following: If the edge e is a tree edge, store the corresponding λ[e] in tree order. If the edge e is not part of the tree, compute the flow α[e] into the node input y.

source
TreeLas.MGT.gaplas! — Method
gaplas!(...)

Perform one iteration. Premises:

  1. x = y + D'*α
  2. α dually feasible, abs(α[e]) ≤ λ[e] for all edges e.
source
TreeLas.MGT.gaplas — Method
gaplas(...)

Graph has to implement several methods:

  • iter_edges(::Function, ::Graph)
  • IncidenceIndex(::Graph)
source
TreeLas.MGT.gaplas — Method
gaplas(y, graph, λ; learn=1.0, max_iter=3, ...)

Optimize in each iteration along a tree.

The learn parameter controls how much of the new tree solution should be taken (should be between $0$ and $1.0$).

source

Utility Functions

TreeLas.Utils.primal_objective — Method
primal_objective(x, y, graph [, mu])

Compute the objective function, i.e.

\[\frac{1}{2} \sum_{i=1}^n μ_i (x_i - y_i)^2 + \sum_{(i,j) \in E} λ_{ij} |x_i - x_j|\]

Hereby the edges (and edge weights $λ_{ij}$) are obtained via enumerate_edges(graph).

source