Fast digital locally monotonic regression

In [1], Restrepo and Bovik developed an elegant mathematical framework in which they studied locally monotonic regressions in R^N. The drawback is that the complexity of their algorithms is exponential in N. In this paper, we consider digital locally monotonic regressions, in which the output symbols are drawn from a finite alphabet, and, by making a connection to Viterbi decoding, provide a fast O(|A|²αN) algorithm that computes any such regression, where |A| is the size of the digital output alphabet, α stands for lomo-degree, and N is sample size. This is linear in N, and it renders the technique applicable in practice.