Kolmogorov-Zurbenko filter - Calculation of coefficients

Question

I'm currently researching the Kolmogorov-Zurbenko filter and trying to implement it myself as a way to smooth one-dimensional signal strength values.

The basic filter per se is pretty easy to implement by using two loops:

for each iteration do:
    for each point do:
        movingAverage(point)

Since this filter is going to be applied quite often and performance is an issue, I'd like to precalculate the coefficients $a^{m, k}_s$ - see https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Zurbenko_filter#Definition - once so that the iteration loop may be replaced by one simple multiplication (see the last few lines in the definition section).

To do this, $c^{k, m}_s$ has to be calculated: $$a^{m, k}_s = \frac{c^{k, m}_s}{m^k}$$ The problem is that I have trouble understanding how to do that.

The definition section of the linked wiki article states that $c^{k, m}_s$ may be obtained by the equation following, but when I try to remove the sum and the factor $z$ (since I want to calculate $c$ for one specific values of $s$ respectively $r$) from this equation, I end up with $c^{k, m}_s = 1$, regardless of the parameters.

Obviously I'm missing something here - I'd appreciate any hints. Thanks!

Answer 1

From that link, you see that the terms $c^{k,m}_s$ are defined as the coefficients of a polynomial: $$ \sum^{k(m-1)}_{r = 0}z^rc^{k, m}_{r - k(m - 1)/2}=(1 + z + ... + z^{m-1})^k $$ which means that to compute them you need to expand the power $(1 + z + \dotsb + z^{m-1})^k$ for appropriate values of $k$ and $m$.

---

The case $m = 2$ is fairly simple, because then by the binomial theorem you know that $$ (1+z)^k = \sum_{r = 0}^k \binom{k}{r} z^r $$ hence $$ c^{k,2}_{r - k/2} = \binom{k}{r} := \frac{k!}{r! (k-r)!} $$

For a simple example, consider $k = 3$, $m = 2$. Then $$ (1 + z + ... + z^{m-1})^k = (1 + z)^3 = 1 + 3 z + 3 z^2 + z^3 $$ means that $$ c^{3,2}_{\pm 3/2} = 1 \qquad c^{3,2}_{\pm 1/2} = 3 $$

---

For the general case, it may be useful to observe that $c^{k,m}_s = c^{k,m}_{-s}$.

Also, according to this answer you can use the discrete Fourier transform to speed up the computation of the powers of a polynomial.

Answer 2

Actually, to factor filters tend to speed up calculations, so you don't have to multiply together to determine the coefficients. I think it would be possible to make faster by applying the uniform filter several times (if implemented fast), especially as the moving average filter has very little overhead. You can store sum of m values, then for the next value in the signal remove the leftmost and add the rightmost - one addition and one subtraction, instead of having to multiply and ackumulate $m$ numbers with a filter.