What is the intuition behind the single-pass algorithm (Welford's method) for the corrected sum of squares?

Question

The corrected sum of squares is the sum of squares of the deviations of a set of values about its mean.

$$ S = \sum_{i=1}^k\space\space(x_i - \bar x)^2 $$

We can calculate the mean in a streaming fashion, as follows:

$$ m_n = \frac{n-1}{n}m_{(n-1)} + \frac{1}{n}x_n $$

I understand the intuition behind this: the sum of the previous $n-1$ values was divided by $n-1$, so by multiplying those values by $\frac{n-1}{n}$, we down-weight the sum properly.

However, we can also calculate the full corrected sum of squares as follows:

$$ S_n = S_{n-1} + \frac{n-1}{n}\left( x_n - m_{n-1}\right)^2 $$

However, I don't have a good intuition for why this works. It looks like we use the previous corrected sum of squares value, and then add the square of the current value's deviation from the mean of all the previous values.

But, this algorithm doesn't make sense to me, even if it was derived logically.

These formulas are from "Note on a Method for Calculating Corrected Sums of Squares and Products" by B.P Welford.

Answer 1

Ok, so when you update $S_{n-1}$ to $S_n$ there are two things that need fixing

• you need a term $(x_n-m_n)^2$ for the error in the $n$ observation
• you need to fix up $S_{n-1}$ because it was centered at $m_{n-1}$ and should have been centered at $m_n$. The fix-up term will be something more or less like $(m_n-m_{n-1})^2$.

The single term $$\frac{n-1}{n}\left(x_n-m_{n-1}\right)^2$$ is a combination of those two pieces. In order to work it out precisely you'd need to work out the two components (which would both depend on $m_n$) and then rewrite them to depend only on $x_n$ and $m_{n-1}$ using the mean updating formula. If you do that to the first component, you get $\left(\frac{n-1}{n}\right)^2(x_n-m_{n-1})^2$, which is slightly smaller than the $\left(\frac{n-1}{n}\right)(x_n-m_{n-1})^2$ in the formula, leaving room for the second component.

I'm not going to figure out the second component, but I hope it's now more plausible that it could all work.