Cut-Pursuit Algorithm for Regularizing Nonsmooth Functionals with Graph Total Variation

Loïc Landrieu's cut-pursuit algorithm is a very efficient working-set approach for minimizing the sum of a differentiable functional with a graph total variation regularization (and also nonconvex variations thereof).
As many applications involve other nondifferentiable terms, we extended it to the minimization of functionals, structured over a weighted graph G = (VEw), of the form

    F: xf(x) + ∑vV gv(xv) + ∑(u,v) ∈ E w(u,v)xuxv║ ,

where x ∈ ℍV for some base vector space ℍ, f is differentiable, and for all vV, gv: ℝ → ]−∞,+∞] admits directional derivatives on every points of its domain and every directions.
The cut-pursuit algorithm seeks partitions V = (U1,...,U|V|) of the set of vertices V, constituting the constant connected components of the solution, by successively solving the corresponding problem, structured over the reduced graph G = (V, E), that is

  arg minξ ∈ ℍV    F(x) , such that ∀ UV, ∀ uU, xu = ξU ,

and then refining the partition, by using the directional derivatives and well-thought graph cuts.
A key requirement is thus the ability to solve the reduced problem, which often have the exact same structure as the original one, but with much less vertices |V| ≪ |V|. If the solution of the original problem has only few constant connected components in comparison to the number of vertices, the cut-pursuit strategy can speed-up minimization by several order of magnitude.
Indeed, our first numerical experiments show tremendous improvement over state-of-the-art proximal splitting methods:
medium-scale setting of brain source identification for electroencephalography (|V| = 19 626, |E| = 29 439), using fused LASSO

large-scale multidimensional setting of semantic labeling of 3D point cloud (|V| = 3 000 111, |E| = 17 206 938), using simplex-constraint convex relaxation

This has been published in the 35th International conference on machine learning: paper; reference as BibTeX format.
More details can be found in our preprint.
Optimized C++ implementations, interfaced with GNU Octave or Matlab and Python, can be found at the dedicated GitHub repository.
This is a joint work with Loïc Landrieu.

Back To Home