Re: Efficient Moving Average and Moving Variance Calculations

On May 21, 3:56 am, robert bristow-johnson <r...@xxxxxxxxxxxxxxxxxxxx>
wrote:
On May 20, 4:40 am, kronec...@xxxxxxxxxxx wrote:



It's hard to explain with just a text editor

oh, you need to learn how to do "ASCII math" (a relative of "ASCII
art").

assume your reader is viewing it with a mono-spaced font, make liberal
use of spaces and parenths. don't use tabs.

here, i'll show you. since this is "comp.dsp" and DSP is still often
considered a sub-discipline of electrical engineering, and since EE's
use the symbol u(t) or u[n] to mean the "unit step
function" (continuous or discrete time), and since i made reference to
the unit step function in this thread, i am changing your "u" to a
general input "x". sticking with the convention of most DSP lit
nowadaze, we use brackets "[]" for the discrete time or discrete
frequency independent variable (e.g. "x[n]") and pareths for
continuous independent variable, "x(t)". some people might use
brackets instead of parenths to group together multiple terms, but i
don't. often i use "*" for an explicit multiply. i seldom need a
symbol for convolution, but if i do, i use "(*)" to differentiate it
from a simple multiply.

but if you take the variance with N samples you get S[N].
We then add one term to the summation to get S[N+1] and write S[N+1]
in terms of S(N) with the extra term (x[N+1])^2/(N+1). also use the fact
that N/(N+1) = 1-1/(N+1). It works out and you get recursive variance.
It will converge when N gets large for stationary signals. This is not
an approximation like exponential smoothing is. (I am not claiming the
expression with beta in it is exact - it is the other one I quoted).

Ok so here we go - for N samples

N
S[N] = (1/N) SUM (x[k])^2 (1)
k=1

Add a term

N+1
S[N+1] = (1/(N+1)) SUM (x[k])^2 (2)
k=1

N
= (1/(N+1)) SUM (x[k])^2 + (1/(N+1))*(x[N+1])^2
k=1

= (N/(N+1))*S[N] + (1/(N+1))*(x[N+1])^2

= S[N] + (1/(N+1))*( (x[N+1])^2 - S[N] )

QED
This is the right expression - .

fine. nice and easily read. took me less than 4 minutes.

now, an issue that you're not dealing with. let's suppose, for the
time being, that the mean of x[k] is zero (or it had the mean
subtracted out) so that the mean square, S[N] represents the "sample
variance". it is a known fact in statistical analysis that the sample
variance, as computed by the mean square of the samples, is a slightly
biased estimator of the true population variance and has to be
multiplied by N/(N-1) to unbias it. this is in that thread that John
referred to and, because i was asked about it, i proved this
explicitly in this post:http://groups.google.com/group/comp.dsp/msg/1d89215c51200101?dmode=so...
.

now let's suppose there is a mean and we estimate it with

N
m[N] = (1/N) SUM x[k]
k=1

and you compute the variance as:

V[N] = N/(N-1) * ( S[N] - (m[N])^2 )

you'll get the same variance John does for all of x[k] such that
1 <= k <= N. but it's not a *moving* variance (as is John's), if we
use the recursive summation you do, since that summation *never*
forgets and goes all the way back to x[1]. it is a comprehensive
variance of all of the samples ever taken. no forgetting factor.
it's like an integrator that is never reset. that's how it is
different from what John put forth, which remembers only the most
recent N samples.

now that exponentially weighted calculation using a recursive IIR
filter *does* have a forgetting factor, and, even though i do not have
the notes on me to prove it (but if i feel like "recreational
mathematics", i can re-derive it), i do believe that a compensating
factor similar to N/(N-1) is needed to unbias the variance estimator,
but i do not remember precisely what it is, but suspect that it is (1
+ (1-beta)/2) because i seem to remember that it was related to the
"mean length" of the impulse response of either filter (the
exponentially weighted IIR or the constant weighted FIR).

r b-j

I agree and that's why I said that it only applies for stationary
signals otherwise it is useless (which is normally the case in fact!).
That is where the other methods come into their own but strictly
speaking it is no longer variance when it is time-varying.
The forgetting factor method is an ad-hoc IIR filtering but does work.
It is only first order and you can improve on this I am sure with
higher order FIR filters to get smoother results with tracking as
well. It is quite an important point really since this problem crops
up all the time when you least expect it.

K.
.

Relevant Pages

  • Re: Efficient Moving Average and Moving Variance Calculations
    ... you need to learn how to do "ASCII math" (a relative of "ASCII ... brackets instead of parenths to group together multiple terms, ... variance, as computed by the mean square of the samples, is a slightly ... this is in that thread that John ...
    (comp.dsp)
  • Re: strange behaviour of ntp peerstats entries.
    ... variance truly does minimize the offset variance. ... the filter reduces the variance by some 10 ... delay variance IS reduced, ...
    (comp.protocols.time.ntp)
  • RE: Excel 2007 Pivot Table - Problem with custom field?
    ... add the Variance field to the Row Label area (as well as the Value ... I am trying to do what l think is pretty basic calculation & filter ... Report Filter = Company ...
    (microsoft.public.excel)
  • Re: Lowpass filtering for OFDM introduces interference?
    ... Evaluating this at some arbitrary k = k_0, this relationship is clearly not affected by the size of the DFT, nor by the amount of noise at any other k. ... variance of vshould be reduced leading to a reduced noise variance of ... Because each bin of the DFT is a matched correlation filter. ...
    (comp.dsp)
  • Re: strange behaviour of ntp peerstats entries.
    ... variance truly does minimize the offset variance. ... the filter reduces the variance by some 10 ... A 9ms delay from a collision introduces a 4ms change in the ...
    (comp.protocols.time.ntp)