Abstract
We study Total Variation (TV) regularization, a widely used technique for eliciting structured sparsity. In particular, we propose efficient algorithms for computing prox-operators for $\ell_p$-norm TV. The most important among these is $\ell_1$-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 an extensive suite of experiments on image denoising, image deconvolution, fused-lasso variants, and 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.
Introduction
Total Variation (TV) regularization is a cornerstone of modern data science, particularly in signal and image processing. It is designed to "clean" signals while preserving critical structural features, such as sharp edges, by encouraging structured sparsity—the assumption that a signal is mostly constant with occasional, discrete jumps.
As data scales from 1D signals to 2D images and 3D videos, the computational complexity of TV regularization increases significantly. Existing algorithms are often either highly specialized for specific dimensions or computationally expensive and difficult to parallelize. Furthermore, while standard $\ell_1$-norm TV is well-understood, variants involving other $\ell_p$-norms or weighted penalties lack efficient, general-purpose solvers. This paper introduces a fast, modular framework that addresses these challenges by decomposing multidimensional problems into optimized 1D components.
The Taut-String Connection
The core innovation of this work lies in a new geometric analysis of 1D $\ell_1$-TV. The authors demonstrate that solving the 1D TV problem is mathematically equivalent to finding the shortest path—a "taut string"—through a "tube" constructed around the cumulative sum of the input signal.
This geometric insight allows for the development of a Hybrid Taut-String algorithm. While current state-of-the-art methods (like Condat’s) are fast, they can exhibit $O(n^2)$ worst-case runtimes on certain "pathological" signals. The proposed hybrid approach utilizes a fast linearized version of the taut-string method but switches to a robust classic version when necessary, ensuring consistent $O(n)$ performance.
Modular Proximal Optimization
Rather than building monolithic solvers for high-dimensional data, the authors propose a modular proximal optimization strategy. By creating an exceptionally fast 1D solver, they can use "combiner" algorithms—such as Proximal Dykstra, Douglas-Rachford (Alternating Reflections), and ADMM—to stack these 1D operations into higher dimensions.
This modularity provides several key benefits:
- Efficiency: Any improvement to the 1D "backbone" solver automatically accelerates every multidimensional application within the framework.
- Parallelization: Because multidimensional solvers apply 1D solvers to independent rows, columns, or time-frames, the framework is "embarrassingly parallel" and ideal for multi-core CPUs.
- Versatility: The framework extends beyond $\ell_1$-TV to include specialized Newton methods for $\ell_2$-TV and hybrid Gradient Projection/Frank-Wolfe approaches for general $\ell_p$-norms ($p \ge 1$).
Experimental Validation
The framework was rigorously tested across multiple domains:
- Synthetic Data: Timing benchmarks on signals with up to $10^7$ points.
- Natural Images: Denoising and deconvolution tests using the INRIA Holidays and ImageNet (LSVRC 2010) datasets.
- Bioinformatics: Fused-Lasso classification on microarray datasets (e.g., ArrayCGH, Leukemias).
- Video: 3D denoising on standard sequences like salesman and coastguard.
Results indicate that the 1D solvers are significantly faster than previous standards like the SLEP library. In 2D image denoising, the Douglas-Rachford implementation achieved high-quality solutions faster than most competing methods. Furthermore, in bioinformatics applications, the ability to use general $\ell_p$-norms helped avoid "oversmoothing," leading to improved classification accuracy.
Conclusion
By grounding TV regularization in geometric taut-string theory and adopting a modular design, the authors have created a highly efficient and scalable library (proxTV). While the current focus is on anisotropic TV—which is computationally efficient but not rotation-invariant—the modular approach provides a foundation for future extensions into isotropic TV and other complex structured sparsity penalties.
Summary updated