License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.23
URN: urn:nbn:de:0030-drops-120977
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12097/
Go to the corresponding LIPIcs Volume Portal

Kuthe, Elias ; Rahmann, Sven

Engineering Fused Lasso Solvers on Trees

pdf-format:
LIPIcs-SEA-2020-23.pdf (0.8 MB)

Abstract

The graph fused lasso optimization problem seeks, for a given input signal y=(y_i) on nodes i∈ V of a graph G=(V,E), a reconstructed signal x=(x_i) that is both element-wise close to y in quadratic error and also has bounded total variation (sum of absolute differences across edges), thereby favoring regionally constant solutions. An important application is denoising of spatially correlated data, especially for medical images.
Currently, fused lasso solvers for general graph input reduce the problem to an iteration over a series of "one-dimensional" problems (on paths or line graphs), which can be solved in linear time. Recently, a direct fused lasso algorithm for tree graphs has been presented, but no implementation of it appears to be available.
We here present a simplified exact algorithm and additionally a fast approximation scheme for trees, together with engineered implementations for both. We empirically evaluate their performance on different kinds of trees with distinct degree distributions (simulated trees; spanning trees of road networks, grid graphs of images, social networks). The exact algorithm is very efficient on trees with low node degrees, which covers many naturally arising graphs, while the approximation scheme can perform better on trees with several higher-degree nodes when limiting the desired accuracy to values that are useful in practice.

BibTeX - Entry

@InProceedings{kuthe_et_al:LIPIcs:2020:12097,
  author =	{Elias Kuthe and Sven Rahmann},
  title =	{{Engineering Fused Lasso Solvers on Trees}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12097},
  URN =		{urn:nbn:de:0030-drops-120977},
  doi =		{10.4230/LIPIcs.SEA.2020.23},
  annote =	{Keywords: fused lasso, regularization, tree traversal, cache effects}
}

Keywords: fused lasso, regularization, tree traversal, cache effects
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: Source code: https://github.com/eqt/treelas

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI