Optimal Median Smoothing

Median smoothing of a series of data values is considered. Naive programming of such an algorithm would result in large amount of computation, especially when the series of data values is long. By maintaining a heap structure that we update when moving along the data we obtain an optimal median smoothing algorithm. Description and Purpose High variability in a given series X 1 ; : : :; X N may obscure important structural features which would become evident if the data were replaced by a smoother, which, due to the robustness of the median, will often give a superior result to It is common terminology to call the series X i the running median of order K = 2k + 1 and we refer to X i?k ; : : :; X i+k as the window of size K around X i : In this note we describe an eecient running median algorithm using the HEAP data structure and we mention an interesting recent lower bound which shows that the algorithm has, up to constants, optimal running time. An obvious approach (METHOD 1) to the computation of X i could use the fast median algorithm of Schh onhage, Patterson and Pippenger (1976) with which each X i could be obtained in at most 3K steps. As is usual, we count each pairwise comparison as a STEP and argue that the running time of any "reasonable" implementation would be proportional to this complexity measure.