Fast variance calculation

Suppose to have a sequence $X$ of $m$ samples and for each $i^{th}$ sample you want to calculate a local mean $\mu_{X}(i)$ and a local variance $\sigma^2_{X}(i)$ estimation over $n \ll m$ samples of $X$.

Excluding the "boundary" samples of $X$, one can incrementally calculate the local mean estimation as follows:

$$S(i+1) = S(i) + X(i+1+\frac{n}{2}) - X(i-\frac{n}{2}) \\ \mu_{X}(i+1) = \frac{1}{n} S(i+1)$$

where we suppose to have the previous value of $S(i)$ which is

$$S(i) = \sum_{k=i-n/2}^{i+n/2}{X(k)}$$

and therefore without needing to compute the whole $S(i)$ for each $i$.

I'm looking for a similar "fast" way to calculate a local variance $\sigma^2_{X}(i)$ estimation. Notice I could accept an approximate extimation of this measure too, if precise enough. Can you help me? Thank you very much in advance for your attention.

EDIT: now my doubt is the following:

the local variance at $(i+1)^{th}$ sample should be:

\begin{align} \sigma^2_{X}(i+1) &= \frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{(X(k) - \mu_{X}(i+1))^2} \\ &= \frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{ \left((X(k))^2 + (\mu_{X}(i+1))^2 - 2\mu_{X}(i+1)X(k) \right)} \\ &= \frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{(X(k))^2} + \frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{(\mu_{X}(i+1))^2} - \frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{2\mu_{X}(i+1)X(k)} \\ &= \mu_{X^2}(i+1) + (\mu_{X}(i+1))^2 - 2\mu_{X}(i+1)\frac{1}{n}\sum_{k=i+1-n/2}^{i+1+n/2}{X(k)} \\ &= \mu_{X^2}(i+1) + (\mu_{X}(i+1))^2 - 2(\mu_{X}(i+1))^2 \\ &= \mu_{X^2}(i+1) - (\mu_{X}(i+1))^2 \end{align}

where $\mu_{X^2}(i+1)$ can be calculated by doing $$\mu_{X^2}(i+1) = \frac{1}{n}K(i+1)$$ as proposed by Kartik Audhkhasi, and $(\mu_{X}(i+1))^2$ can be computed by using the already computed $\mu_{X}(i+1)$. Therefore, given $$\mu_{X^2}(i+1) = \frac{1}{n}K(i+1) \quad,\quad \mu_{X}(i+1) = \frac{1}{n}S(i+1)$$ the final result is: \begin{align} \sigma^2_{X}(i+1) &= \mu_{X^2}(i+1) - (\mu_{X}(i+1))^2 \\ &= \frac{1}{n}K(i+1) - \frac{1}{n^2}(S(i+1))^2 \\ &= \frac{1}{n}\left(K(i+1) - \frac{1}{n}S(i+1)S(i+1)\right) \end{align}

Could this method be correct and what's the difference with the one proposed below by Kartik Audhkhasi. In other words, why it has been proposed an update formula which requires to store the previous mean value too for variance calculation?

Thank you again for your attention.

-
The command to get $\ll$ is \ll. –  joriki Aug 24 '12 at 5:05
The above solution is similar to the one I mentioned. You end up with the same equation for $\sigma_X^2(i+1)$ after the initial derivation as I did for $V(i)$. The final result indicates that you can compute the sums $K(i+1)$ and $S(i+1)$ apriori and then compute the variance. I essentially wrote the same result in a different form. –  Kartik Audhkhasi Aug 24 '12 at 14:05
i finally understood. really thank you very much for your attention. –  Alfatau Aug 24 '12 at 16:11

I think one can adopt a similar approach to the mean computation. Specifically, consider the following sum of squares:

$K(i) = \sum_{j=i-n/2}^{i+n/2} X(j)^2$

Hence, we can write the following update formula for $K$:

$K(i+1) = K(i) + X(i+1+n/2)^2 - X(i-n/2)^2$

The relation between $K$ and the variance ($V$) is simple:

$V(i) = \frac{1}{n}\sum_{j=i-n/2}^{i+n/2}[X(j) - \mu(i)]^2 = \frac{1}{n}K(i) - \mu(i)^2$

Using the above two formulae, you can get the following update for the variance:

$V(i+1) = V(i) + \mu(i)^2 - \mu(i+1)^2 + \frac{1}{n}[X(i+1+n/2)^2 - X(i-n/2)^2]$

So you can use this in conjunction with the mean update formula.

Note: I am assuming biased estimator for variance. You can use the unbiased one by having $n-1$ in the denominator and deriving the corresponding update formula.

-

I believe your final result is correct as well as the one proposed by Kartik Audhkhasi.

While his formula for the computation of $V(i+1)$ riequires keeping $\mu(i)$ in memory, It does not require storing and updating $K(i+1)$ at every step.

-
ok, i understood. thank you very much. –  Alfatau Aug 24 '12 at 16:11