Updating variance of a dataset [duplicate]

Question

In an application, I deal will a large number of images from which I successively extract particular values to compute their means and variances. Because storing them all would mean storing Gigas, I'd like to store only things that would allow me to compute the global means and variances. What do I have to store?

Answer 1

In the absence of information to the contrary I assume you want univariate calculations and you want the $n-1$-denominator version of variance.

One useful way is to update the sums of squares of deviations from the mean, which I'll call SSE.

Let's say that at time $t$ you have $\bar x$, $\text{SSE}$ and $s^2$, and an observation, $x_{t+1}$ and you want to have those three computed quantities at time $t+1$.

Here's how you can update them:

$t=t+1\\ e_t = x_t-\bar x\quad\text{ # note that the } \bar x \text{ term there is the previous mean} \\ \bar x = \bar x + e_t/t \\ \text{SSE} = \text{SSE} + e_t\cdot (x_t-\bar x)\quad\text{ # note that the term there is NOT } e_t^2\\ s^2 = SSE/(t-1) $

This calculation is much more stable than the raw calculation of $\sum_i^t x_i^2$ version (which you'll find in many old books, and which is not too bad when working by hand, where you can see when you're losing precision). It is not the most stable possible calculation, but is sufficient for almost all purposes. If stability does become an issue for you there are some other things that can be done.

As @January rightly points out, I've given an on-line algorithm and you seem to only want the values at the end. In that case, the above algorithm can be sped up a little, for example, by not calculating $s^2$ each iteration.

Alternatively, the algorithm suggested by @January below can be made much more stable by subtracting an estimate of the mean from each observation before taking the sums and sums of squares. Algebraically it doesn't change the mean, but it makes it substantially more stable. It doesn't need a very good estimate to make a big difference; often the first observation is sufficient (since usually the situations where, say, the first observation is a very bad estimate of the mean are the situations where it really doesn't matter).

See also https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance

Answer 2

That is not really a question for CrossValidated, but here it comes: you only need to store three values:

• current number of variables,
• current sum of squares of the variables
• current sum of the variables.

That's because variance can be expressed in terms of $\sum x_i^2$ and $(\sum x_i)^2$.

$var(X) = \frac{\sum (\bar{x} - x_i)^2}{n}$

and

$\sum( \bar{x} - x_i)^2 = \sum \bar{x}^2 - 2\cdot \bar{x} \sum x_i + \sum x_i^2 = $

$= n\cdot\bar{x}^2 - 2\cdot \bar{x} \cdot n\cdot \bar{x} + \sum x_i^2 =$

$=\sum x_i^2 - n\cdot\bar{x}^2 $

The main disadvantage of this method is that the sum of squares tends to grow very fast and might be problematic to store; Glenn's variant (in the other answer) is better in this respect, but computationally (slightly) more intensive.