Recursive Update for Sum of Squared Differences

1. Defining the Sum of Squared Differences

Recall the definition of sample variance for $n$ data points:
$s_n^2=\frac{1}{n-1}{\sum }_{i=1}^n(x_i-{\mu }_n{)}^2$
where ${\mu }_n$ is the sample mean of those $n$ points.

Our objective is to compute this value in an online fashion. We already have an online formula for the mean, ${\mu }_n$. Now we need one for the sum of squared differences. Let's define this aggregate value, which is often called $M_k$ or $S_k$, for the first $k$ data points:

$M_k={\sum }_{i=1}^k(x_i-{\mu }_k{)}^2$

Our goal is to find a recursive formula that expresses $M_k$ using only the previous value $M_{k-1}$ and information from the new data point $x_k$.

2. The Algebraic Derivation

The derivation for $M_k$ is more involved than the one for the mean, but it's a fantastic exercise in algebraic manipulation. It beautifully combines the definition of $M_k$ with the recursive mean formula we derived previously.

There are several ways to derive the update rule. We will follow a direct, step-by-step approach that starts from the definition of $M_k$ and substitutes in our formula for ${\mu }_k$. Given your math background, this should be a satisfying path to the solution.

1. Start with the definition of $M_k$:
   $M_k={\sum }_{i=1}^k(x_i-{\mu }_k{)}^2$

2. Substitute the recursive formula for ${\mu }_k$:
   We know that ${\mu }_k={\mu }_{k-1}+\frac{x_k-{\mu }_{k-1}}{k}$. Let's plug this in.
   $M_k={\sum }_{i=1}^k{\left(x_i-\left({\mu }_{k-1}+\frac{x_k-{\mu }_{k-1}}{k}\right)\right)}^2$

3. Rearrange the terms inside the square:
   Let's group the terms to create a binomial $(a-b{)}^2$, where $a=(x_i-{\mu }_{k-1})$ and $b=\frac{x_k-{\mu }_{k-1}}{k}$.
   $M_k={\sum }_{i=1}^k{\left((x_i-{\mu }_{k-1})-\frac{x_k-{\mu }_{k-1}}{k}\right)}^2$

4. Expand the square and distribute the summation:
   Using $(a-b{)}^2=a^2-2ab+b^2$, we get three separate sums:
   $M_k={\sum }_{i=1}^k(x_i-{\mu }_{k-1}{)}^2-{\sum }_{i=1}^{k}2(x_i-{\mu }_{k-1})\frac{x_k-{\mu }_{k-1}}{k}+{\sum }_{i=1}^k{\left(\frac{x_k-{\mu }_{k-1}}{k}\right)}^2$
   Let's analyze each of these three terms.

   Term 1: ${\sum }_{i=1}^k(x_i-{\mu }_{k-1}{)}^2$
   We can split this sum at $i=k-1$:
   ${\sum }_{i=1}^{k-1}(x_i-{\mu }_{k-1}{)}^2+(x_k-{\mu }_{k-1}{)}^2$
   The first part is exactly the definition of $M_{k-1}$. So, Term 1 is $M_{k-1}+(x_k-{\mu }_{k-1}{)}^2$.

   Term 2: $-{\sum }_{i=1}^{k}2(x_i-{\mu }_{k-1})\frac{x_k-{\mu }_{k-1}}{k}$
   The fraction is constant with respect to the summation index $i$, so we can pull it out:
   $-\frac{2(x_k-{\mu }_{k-1})}{k}{\sum }_{i=1}^k(x_i-{\mu }_{k-1})$
   Now, let's look at the remaining sum: ${\sum }_{i=1}^k(x_i-{\mu }_{k-1})={\sum }_{i=1}^{k-1}(x_i-{\mu }_{k-1})+(x_k-{\mu }_{k-1})$.
   The first part of this, ${\sum }_{i=1}^{k-1}(x_i-{\mu }_{k-1})$, is the sum of deviations from the mean for the first $k-1$ elements, which is zero.
   So, the whole sum simplifies to just $(x_k-{\mu }_{k-1})$.
   Plugging this back in, Term 2 becomes $-\frac{2(x_k-{\mu }_{k-1}{)}^2}{k}$.

   Term 3: ${\sum }_{i=1}^k{\left(\frac{x_k-{\mu }_{k-1}}{k}\right)}^2$
   The term being summed is constant, so we just multiply it by $k$:
   $k\cdot \frac{(x_k-{\mu }_{k-1}{)}^2}{k^2}=\frac{(x_k-{\mu }_{k-1}{)}^2}{k}$
   Term 3 is $\frac{(x_k-{\mu }_{k-1}{)}^2}{k}$.

5. Combine the simplified terms:
   Now we assemble the pieces:
   $M_k=\underset{\text{Term 1}}{\underbrace{M_{k-1}+(x_k-{\mu }_{k-1}{)}^2}}\underset{\text{Term 2}}{\underbrace{-\frac{2(x_k-{\mu }_{k-1}{)}^2}{k}}}\underset{\text{Term 3}}{\underbrace{+\frac{(x_k-{\mu }_{k-1}{)}^2}{k}}}$
   Combine the last two terms:
   $M_k=M_{k-1}+(x_k-{\mu }_{k-1}{)}^2-\frac{(x_k-{\mu }_{k-1}{)}^2}{k}$

6. Factor and simplify to the final form:
   Factor out the common term $(x_k-{\mu }_{k-1}{)}^2$:
   $M_k=M_{k-1}+(x_k-{\mu }_{k-1}{)}^2\left(1-\frac{1}{k}\right)$
   $M_k=M_{k-1}+(x_k-{\mu }_{k-1}{)}^2\frac{k-1}{k}$
   This is a valid recursive formula. However, there is an even more elegant and common form. If we recall that ${\mu }_k-{\mu }_{k-1}=\frac{x_k-{\mu }_{k-1}}{k}$, we can rewrite $x_k-{\mu }_k$ as:
   $x_k-{\mu }_k=(x_k-{\mu }_{k-1})-({\mu }_k-{\mu }_{k-1})=(x_k-{\mu }_{k-1})-\frac{x_k-{\mu }_{k-1}}{k}=(x_k-{\mu }_{k-1})\frac{k-1}{k}$
   By substituting this relationship into our equation, we arrive at the classic update rule:
   $M_k=M_{k-1}+(x_k-{\mu }_{k-1})(x_k-{\mu }_k)$

This final formula is remarkable. It tells us that the new sum of squared differences is the old one plus a correction term. This correction is the product of the new data point's deviation from the old mean and its deviation from the new mean.

3. Reviewing the Derivation in Context

Different sources present this derivation with slight variations in notation and approach. To reinforce your understanding, please review the derivations presented in the following resources. They arrive at the same fundamental update rule.

This image provides a concise summary of both the mean and variance update rules, which are the core of Welford's algorithm.

Conclusion

In this lesson, we derived the heart of Welford's algorithm: the recursive update rule for the sum of squared differences from the mean. This derivation is a crucial piece of the puzzle, building upon our previous work on the recursive mean.

Key Takeaways:

• The sum of squared differences from the mean, $M_k={\sum }_{i=1}^k(x_i-{\mu }_k{)}^2$, can be updated recursively.
• The standard update rule is $M_k=M_{k-1}+(x_k-{\mu }_{k-1})(x_k-{\mu }_k)$.
• This formula allows us to maintain a running sum of squared differences in O(1) time and space for each new data point, just like the mean.

Preview of the Next Lesson:

We have now derived both update rules needed for Welford's algorithm. But why is this method numerically stable? In the next lesson, we will analyze the structure of these update formulas and explain why Welford's algorithm avoids the catastrophic cancellation that makes the naive single-pass formula fail. This will connect the mathematical theory back to the practical problem of floating-point precision that we explored in the first module.