Re: Efficient Moving Average and Moving Variance Calculations
- From: kronecker@xxxxxxxxxxx
- Date: Sun, 18 May 2008 23:37:47 -0700 (PDT)
On May 19, 12:28 am, "John E. Hadstate" <jh113...@xxxxxxxxxxx> wrote:
Steven Smith in "Digital Signal Processing" describes an
efficient algorithm for computing a moving average. This
algorithm is also mentioned in the Wikipedia article describing
Moving Average:
http://en.wikipedia.org/wiki/Moving_average
Rick Lyons once asked in this newsgroup about an efficient
algorithm for computing "moving variance":
http://groups.google.com/group/comp.dsp/browse_frm/thread/330ac90a92f...
With minimal effort, one can modify the "Moving Average"
algorithm to efficiently compute a "Moving Variance" and a
"Moving Average" simultaneously at each time step.
Notice that one of the equations for computing a sample
variance over a window with N samples can be written as:
N * Sum(X**2) - (Sum(X)**2)
V = ---------------------------
N * (N - 1)
where X is the input.
To implement this efficiently, allocate two history buffers,
one for values of X and one for values of X**2, each containing
room for N points. These buffers need to be initialized,
perhaps to the first sample of X and X**2 or perhaps to zero,
your choice. Then initialize two variables, SX1 to be the
Sum(elements in X history buffer) and SX2 to be Sum(elements in
X**2 history buffer).
Then, at each time-step k, compute:
X1 = (new sample value)
X2 = X1 * X1
Y1 = (oldest X1 value from X1 history buffer)
Y2 = (oldest X2 value from X2 history buffer)
Overwrite oldest value in X1 history buffer with X1.
Overwrite oldest value in X2 history buffer with X2.
SX1(k) = SX1(k-1) + X1 - Y1
SX2(k) = SX2(k-1) + X2 - Y2
Calculate Moving Average:
M = SX1 / N
Calculate Moving Variance:
V = (N * SX2 - (SX1 * SX1)) / (N * (N - 1))
A simpler way is to do this....
s(k+1)=beta*s(k)+(1-beta)*u^2(k)
where beta is a forgetting factor less than unity.
u is the input and s is the variance.
The correct equation for recursive variance can be found by addoing an
extra sample to batch variance
s(k+1)=s(k)+(1/(k+1)[s(k)-u^2(k)]
if I rememebr right which converges for stationary u when k->
infinity. No use for tracking though - you need the forgetting factor
version or a moving window as has been explained.
There is one more method which estimated the inverse of variance
should you need that one!
K.
.
- Follow-Ups:
- Re: Efficient Moving Average and Moving Variance Calculations
- From: John E. Hadstate
- Re: Efficient Moving Average and Moving Variance Calculations
- References:
- Efficient Moving Average and Moving Variance Calculations
- From: John E. Hadstate
- Efficient Moving Average and Moving Variance Calculations
- Prev by Date: image downsampling : easy to implement algorithms
- Next by Date: An integrator with a Difference?
- Previous by thread: Re: Efficient Moving Average and Moving Variance Calculations
- Next by thread: Re: Efficient Moving Average and Moving Variance Calculations
- Index(es):
Relevant Pages
|
Loading
