# Exact algorithms for L1-TV regularization of real-valued or circle-valued signals

arXiv: https://arxiv.org/abs/1504.00499 · HTML: https://mlsanity.com/paper/1504.00499/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2015.

## Built on by (most cited first, 1 of 1)

- [Tikhonov Regularization of Circle-Valued Signals](https://mlsanity.com/paper/2108.02602/) (2021)

## Abstract (arXiv)

We consider L1-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 mathscrO(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 mathscrO(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.