4
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Tim, mdewey, John, Peter Flom Aug 13 '17 at 10:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Do you mean that you wish to update the mean and variance - that is, given a computed mean and variance on the first $t-1$ observations you want to compute them on $t$ observations? Are these univariate variances, or variance-covariance matrices? In the univariate case, you only need store a few values. $\endgroup$ – Glen_b Oct 8 '13 at 8:39
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1, you are totally right about the stability -- $x_i^2$ can grow very fast. However, that depends on your implementation; keeping track of sum and sum of squares is less computationally intensive. $\endgroup$ – January Oct 8 '13 at 9:05
  • $\begingroup$ @January It's not so much the way the sum of squares grows but when the standard deviation is very small compared to the mean that runs into the big problem. You can get catastrophic loss of precision when subtracting the square of the mean. I am also not so sure your version is actually less computationally intensive. $\endgroup$ – Glen_b Oct 8 '13 at 9:14
  • $\begingroup$ Looking at the algorithms as described, mine has one fewer multiplication/division operations and two more addition/subtraction operations. Which is faster depends on the relative speeds of those, which is platform dependent. However, there's a way to save a multiplication/division off January's outline, so that algorithm is potentially faster by two addition/subtraction operations per iteration. (A couple of subtractions is a cheap price to pay for the increase in stability) $\endgroup$ – Glen_b Oct 8 '13 at 9:37
  • $\begingroup$ um, yes, but only if you are calculating the SSE and mean in each step, which would not be very clever (if I understand the problem correctly, he only wants to calculate the variance and mean at the end). And then I have a single multiplication, two sums and one increment in each step, vs. your three multiplications, three sums and one increment. $\endgroup$ – January Oct 8 '13 at 9:54
  • $\begingroup$ @January That's a good point; I took him to be wanting them at each step, but it looks it's not the case. In the case where they're only required at the end, I could save some calculations from my algorithm as well, but yours would still be a little faster. $\endgroup$ – Glen_b Oct 8 '13 at 10:31
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Actually I think the question is on topic here, falling under 'statistical computing' but it would also be on topic at SO. $\endgroup$ – Glen_b Oct 8 '13 at 9:16
  • 1
    $\begingroup$ The biggest problem with this one in raw form isn't storage (though that can be an issue), it's catastrophic loss of precision whenever the standard deviation is very small compared to the mean. $\endgroup$ – Glen_b Aug 12 '17 at 7:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.