A finite hyperplane traversal algorithm for 1-dimensional L^1pTV minimization, for 0

DOI10.1007/S10589-015-9738-4MaRDI QIDQ493699zbMATH OpenOpenAlexFDO

Authors Heather A. Moon, Thomas J. Asaki

Publication date 4 September 2015

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10589-015-9738-4

zbMATH Keywords

nonsmooth optimizationscalessignal processing

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Review text

This paper presents a finite hyperplane transversal (ht) algorithm for solving the 1D discrete \(L^{1}pTv\) problem, for all parameters \(\lambda\geq0\) \[ \min_{u\in \mathbb{R}^{m+1}}\left\{ G_{p}(u)\equiv\sum_{i=0}^{m-1}\left| u_{i+1} -u_{i}\right| ^{p}+\lambda\sum_{i=0}^{m}\left| f_{i}-u_{i}\right| \right\} , \] where \(0<p\leq1,\) \(f\in \mathbb{R}^{m+1}\) is some given data, with either fixed (\(u_{0}=f_{0}\) and \(u_{m}=f_{m} \)) or free boundary conditions. The ht algorithm requires only finitely many iterations to obtain a complete set of exact minimizers for all \(\lambda \geq0\). For \(p=1,\) these minimizers are global minimizers, while for \(p<1,\) the minimizers are local. Computational implementations of the ht algorithm are presented for both general and binary data. The paper shows results of time trials and considers an example of using ht for extracting scale information from daily sunspot number data.

Recommendations

• Exact algorithms for L^1-TV regularization of real-valued or circle-valued signals
• Total variation minimization with an \(H^{-1}\) constraint
• A Finite Smoothing Algorithm for Linear $l_1 $ Estimation
• An algorithm for total variation minimization and applications
• Combinatorial Image Analysis

Cites work

• Aspects of Total Variation RegularizedL¹Function Approximation
• Direct methods in the calculus of variations
• Edge-preserving and scale-dependent properties of total variation regularization
• Efficient Minimization Methods of Mixed l2-l1 and l1-l1 Norms for Image Restoration
• scientific article; zbMATH DE number 2132148 (Why is no real title available?)
• scientific article; zbMATH DE number 3551792 (Why is no real title available?)
• scientific article; zbMATH DE number 2062604 (Why is no real title available?)
• scientific article; zbMATH DE number 1827348 (Why is no real title available?)
• Minimizers of Cost-Functions Involving Nonsmooth Data-Fidelity Terms. Application to the Processing of Outliers
• Nonlinear total variation based noise removal algorithms
• Parametric maximum flow algorithms for fast total variation minimization

Cited in

(6)

• Anisotropic variation formulas for imaging applications
• \(L^{1}\mathrm{TV}\) computes the flat norm for boundaries
• Exact algorithms for L^1-TV regularization of real-valued or circle-valued signals
• There are thin minimizers of the \(L^{1}TV\) functional
• The L^1-Potts functional for robust jump-sparse reconstruction
• Rayleigh quotient minimization for absolutely one-homogeneous functionals

This page was built for publication: A finite hyperplane traversal algorithm for 1-dimensional \(L^1pTV\) minimization, for \(0<p\leq 1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q493699)