# Total variation on a tree

arXiv: https://arxiv.org/abs/1502.07770 · HTML: https://mlsanity.com/paper/1502.07770/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2015.

## Built on by (most cited first, 4 of 4)

- [Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [conference paper]](https://mlsanity.com/paper/2502.01358/) (2025)
- [Untangling Lariats: Subgradient Following of Variationally Penalized Objectives](https://mlsanity.com/paper/2405.04710/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees](https://mlsanity.com/paper/2508.11112/) (2025)

## Abstract (arXiv)

We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the non-convex case and derive worst case complexities that are equal or better than existing methods. We show applications to total variation based 2D image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very efficient, offer a high degree of parallelism and come along with memory requirements which are only in the order of the number of image pixels.