Online algorithms for boxcar-ish moving averages

One problem with exponentially weighted moving averages is that the weight that older samples decays sharply even for very recent samples.

The impulse response of such an average shows this clearly. In the graph to the right, the red line is the impulse response of the exponential weighted average is shown by the red line. The impulse response of a different kind of moving average derived by John Canny in the early 80's is shown by the black line.

The Canny filter puts higher weight on the events in the recent past which makes it preferable when you don't want to forget things right away, but do want to forget them before long and also want an on-line algorithm.

The cool thing about the Canny filter is that it is only twice as much work as a simple exponential moving average. The idea is that if you take the difference between two exponentially weighted averages with different time constants, you can engineer things to give you an impulse response of the sort that you would like.

The formula for such a difference looks like this
\begin{eqnarray*}
w(x) &=& k_1 e^{-x/\alpha} - k_2 e^{-x/\beta}
\end{eqnarray*}
Here $k_1$ and $k_2$ scale the two component filters in magnitude and $\alpha$ and $\beta$ are the time constants for the filters.

It is nice to set the magnitude of the filter at delay $0$ to be exactly 1. We can use this to get a value for $k_2$ in terms of $k_1$
\begin{eqnarray*}
w(0) &=& k_1 - k_2 = 1 \\
k_2 &=& k_1 -1
\end{eqnarray*}
Similarly, we can constrain the slope of the impulse response to be $0$ at delay $0$. This gives us $\beta$ in terms $\alpha$
\begin{eqnarray*}
w'(0) &=& {k_1 \over \alpha} - {k_2 \over \beta} = 0\\
{k_1 \over \alpha} &=& {k_1-1 \over \beta} \\
\beta &=& \alpha \frac{ k_1-1} { k_1}
\end{eqnarray*}
The final result is this impulse response
\begin{eqnarray*}
w(x) = k \exp \left(-{x \over \alpha}\right)-(k-1) \exp\left(-{k x\over \alpha (k-1)}\right)
\end{eqnarray*}
We can do a bit better if we note that as $k \to \infty$, the shape of the impulse quickly converges to a constant shape with mean of $w(x) \to \frac{3a}{2}$ and a total volume of $2a$.