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.
The convex case on a chain (or its continuous-domain version) has been addressed in @cite_23 @cite_20 @cite_9 @cite_25 @cite_16 @cite_33 @cite_13 @cite_29 @cite_24 . In particular, it has been shown that the problem with quadratic unaries @math can be solved in @math time by the taut string algorithm @cite_0 @cite_12 and by the method of Johnson @cite_8 . Condat @cite_32 presented an @math algorithm, which however empirically outperformed the method in @cite_0 @cite_12 according to the tests in @cite_32 . @cite_1 , the authors proposed an elegant derivation of the method of Condat @cite_32 starting from the tau string algorithm @cite_0 , which in turn also allows to use weighted total variation. Our @math method for this case can be viewed as a generalization to weighted total variation and an alternative implementation of Johnson's algorithm that requires less memory.
@cite_33 @cite_8 @cite_9 @cite_29 @cite_1 @cite_32 @cite_24 @cite_0 @cite_23 @cite_12 @cite_16 @cite_13 @cite_25 @cite_20
2025289780 311729721 2962973949 2162894628 2021345239 2080238139
We propose a dynamic programming algorithm for the one-dimensional Fused Lasso Signal Approximator (FLSA). The proposed algorithm has a linear running time in the worst case. A similar approach is developed for the task of least squares segmentation, and simulations indicate substantial performance improvement over existing algorithms. Examples of R and C implementations are provided in the online Supplementary materials, posted on the journal web site. We study , a widely used technique for eliciting structured sparsity. In particular, we propose efficient algorithms for computing prox-operators for @math -norm TV. The most important among these is @math -norm TV, for whose prox-operator we present a new geometric analysis which unveils a hitherto unknown connection to taut-string methods. This connection turns out to be remarkably useful as it shows how our geometry guided implementation results in efficient weighted and unweighted 1D-TV solvers, surpassing state-of-the-art methods. Our 1D-TV solvers provide the backbone for building more complex (two or higher-dimensional) TV solvers within a modular proximal optimization approach. We review the literature for an array of methods exploiting this strategy, and illustrate the benefits of our modular design through extensive suite of experiments on (i) image denoising, (ii) image deconvolution, (iii) four variants of fused-lasso, and (iv) video denoising. To underscore our claims and permit easy reproducibility, we provide all the reviewed and our new TV solvers in an easy to use multi-threaded C++, Matlab and Python library. A very fast noniterative algorithm is proposed for denoising or smoothing one-dimensional discrete signals, by solving the total variation regularized least-squares problem or the related fused lasso problem. A C code implementation is available on the web page of the author. The paper considers the problem of nonparametric regression with emphasis on controlling the number of local extremes. Two methods, the run method and the taut-string multiresolution method, are introduced and analyzed on standard test beds. It is shown that the number and locations of local extreme values are consistently estimated. Rates of convergence are proved for both methods. The run method converges slowly but can withstand blocks as well as a high proportion of isolated outliers. The rate of convergence of the taut-string multiresolution method is almost optimal. The method is extremely sensitive and can detect very low power peaks. Section 1 contains an introduction with special reference to the number of local extreme values. The run method is described in Section 2 and the taut-string-multiresolution method in Section 3. Low power peaks are considered in Section 4. Section 5 contains a comparison with other methods and Section 6 a short conclusion. The proofs are given in Section 7 and the taut-string algorithm is described in the Appendix. It is known that discrete BV-regularization and the taut string algorithm are equivalent. In this paper we extend this result to the continuous case. First we derive necessary equations for the solution of both BV-regularization and the taut string algorithm by computing suitable Gateaux derivatives. The equivalence then follows from a uniqueness result. 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).