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.
Suppose that we observe independent, identically distributed random pairs (X1; Y1), (X2; Y2), . . . , (Xn; Yn). Our goal is to estimate regression functions such as the conditional mean or nquantile of Y given X, where 0 0 is some tuning parameter. This framework is extended further in order to include binary or Poisson regression, and to include local variation penalties. The latter are needed in order to construct estimators adapting to inhomogenous smoothness of f . For the general framework we develop noniterative algorithms for the solution of the minimization problems which are closely related to the taut string algorithm (cf. Davies and Kovac 2001).