Fast digital locally monotonic regression

Restrepo and Bovik [1993] 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 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