Modular proximal optimization for multidimensional total-variation regularization

2014/11/03 by Álvaro Barbero, Suvrit Sra, Barbero, Álvaro +1 · 5 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1411.0589

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

openalex publication_date 2014/11/03 · arxiv created 2017/12/30 · arxiv updated 2018/01/03 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28

Abstract

We study TV regularization, a widely used technique for eliciting structured sparsity. In particular, we propose efficient algorithms for computing prox-operators for ℓ_p-norm TV. The most important among these is ℓ₁-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.

Citations

• Fast and Flexible ADMM Algorithms for Trend Filtering
• A Limited Memory Algorithm for Bound Constrained Optimization
• A Dynamic Programming Algorithm for the Fused Lasso and L 0 -Segmentation
• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• Nonlinear total variation based noise removal algorithms
• The Group Lasso for Logistic Regression
• Reflection methods for user-friendly submodular optimization
• Proximal Splitting Methods in Signal Processing
• Numerical optimization

Cited by

• Measuring Uncertainty Calibration
• cryoSENSE: Compressive Sensing Enables High-throughput Microscopy with Sparse and Generative Priors on the Protein Cryo-EM Image Manifold
• Asymptotic Distribution of Constrained Nearly-Isotonic Graph Fused Lasso
• Total variation on a tree
• Convex Optimization for Parallel Energy Minimization

Related

• Learning to solve TV regularized problems with unrolled algorithms
• Closed-Form Approximation of the Total Variation Proximal Operator
• Parallel proximal methods for total variation minimization
• Total variation regularization with variable Lebesgue prior
• A Complex Constrained Total Variation Image Denoising Algorithm with Application to Phase Retrieval