Fast digital locally monotonie regression

Nicholas D. Sidiropoulos

Research output: Contribution to journalArticle

9 Scopus citations


Locally monotonie regression is the optimal counterpart of iterated median filtering. In a previous paper, Restrepo and Bovik developed an elegant mathematical framework in which they studied locally monotonie regressions in RN. The drawback is that the complexity of their algorithms is exponential in N. In this paper, we consider digital locally monotonie regressions, in which the output symbols are drawn from a finite alphabet and, by making a connection to Viterbi decoding, provide a fast O(|4|2a.N) algorithm that computes any such regression, where \A\ is the size of the digital output alphabet, a stands for lomo degree, and N is sample size. This is linear in N, and it renders the technique applicable in practice.

Original languageEnglish (US)
Pages (from-to)389-395
Number of pages7
JournalIEEE Transactions on Signal Processing
Issue number2
StatePublished - Jan 1 1997

Cite this