Modular proximal optimization for multidimensional total-variation regularization

Abstract

We study \emph{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 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.

67 pages, 32 figures, new non-iterative fast TV algorithm, extensive new experiments, corresponds to the github proxtv repository now

References in corpus (5)

• Pathwise coordinate optimization
• Fast and Flexible ADMM Algorithms for Trend Filtering
• Reflection methods for user-friendly submodular optimization
• Convex Optimization for Parallel Energy Minimization
• A Derivative-Free Approach to Total Variation Regularization

Cited by in corpus (25)

• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• Tensor Completion for Radio Map Reconstruction using Low Rank and Smoothness
• A Class of Nonconvex Penalties Preserving Overall Convexity in Optimization-Based Mean Filtering
• Trend Filtering on Graphs
• Scalable Variational Inference in Log-supermodular Models
• Adaptive Three Operator Splitting
• Convex Optimization for Parallel Energy Minimization
• Penalized matrix decomposition for denoising, compression, and improved demixing of functional imaging data
• Element-wise estimation error of a total variation regularized estimator for change point detection
• Adaptive Non-Parametric Regression With the $K$-NN Fused Lasso
• Interpretable Low-Dimensional Regression via Data-Adaptive Smoothing
• Primal-Dual Active-Set Methods for Isotonic Regression and Trend Filtering
• Active-set Methods for Submodular Minimization Problems
• On the convergence rate of the three operator splitting scheme
• Exponential Family Trend Filtering on Lattices
• Combinatorial Preconditioners for Proximal Algorithms on Graphs
• A causal fused lasso for interpretable heterogeneous treatment effects estimation
• How Likely are Ride-share Drivers to Earn a Living Wage? Large-scale Spatio-temporal Density Smoothing with the Graph-fused Elastic Net
• A principled approach for generating adversarial images under non-smooth dissimilarity metrics
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• On efficiently solving the subproblems of a level-set method for fused lasso problems
• Total variation on a tree
• GapTV: Accurate and Interpretable Low-Dimensional Regression and Classification
• Total Variation Regularized Tensor-on-scalar Regression