FAST DIGITAL LOCALLY MONOTONIC REGRESSION

Locally monotonic regression is the optimal counterpart of iterated me dian filtering, In a previous paper, Restrepo and Bovik developed an e legant mathematical framework in which they studied locally monotonic regressions in R(N). The drawback is that the complexity of their algo rithms is exponential in N. In this paper, we consider digital locally monotonic regressions, in which the output symbols are drawn from a f inite alphabet and, by making a connection to Viterbi decoding, provid e a fast O(\A\(2) alpha N) algorithm that computes any such regression , where \A\ is the size of the digital output alphabet, alpha stands f or lomo degree, and N is sample size, This is linear in N, and it rend ers the technique applicable in practice.