Exact algorithms for $L^1$-TV regularization of real-valued or circle-valued signals

Abstract

We consider $L^1$-TV regularization of univariate signals with values on the real line or on the unit circle. While the real data space leads to a convex optimization problem, the problem is non-convex for circle-valued data. In this paper, we derive exact algorithms for both data spaces. A key ingredient is the reduction of the infinite search spaces to a finite set of configurations, which can be scanned by the Viterbi algorithm. To reduce the computational complexity of the involved tabulations, we extend the technique of distance transforms to non-uniform grids and to the circular data space. In total, the proposed algorithms have complexity $\mathcal{O}(KN)$ where $N$ is the length of the signal and $K$ is the number of different values in the data set. In particular, the complexity is $\mathcal{O}(N)$ for quantized data. It is the first exact algorithm for TV regularization with circle-valued data, and it is competitive with the state-of-the-art methods for scalar data, assuming that the latter are quantized.

References in corpus (4)

• Total variation regularization for manifold-valued data
• Extensions of smoothing via taut strings
• Mumford-Shah and Potts Regularization for Manifold-Valued Data with Applications to DTI and Q-Ball Imaging
• Total variation on a tree

Cited by in corpus (5)

• Total Generalized Variation for Manifold-valued Data
• Mumford-Shah and Potts Regularization for Manifold-Valued Data with Applications to DTI and Q-Ball Imaging
• Bayesian selection for the l2-Potts model regularization parameter: 1D piecewise constant signal denoising
• Tikhonov Regularization of Circle-Valued Signals
• An Inexact Semi-smooth Newton Method on Riemannian Manifolds with Application to Duality-based Total Variation Denoising