What is K means objective function?

Question

In elements of statistical learning book it is given like below image, i am not able to understand how it got to second line. Can someone help ?

Answer 1

It is an important statistical result to be able to show the following:

$$ \sum_{i=1}^n \sum_{j=1}^n (x_i - x_j)^2 = 2n \sum_{i=1}^n (x_i - \bar{x})^2$$

The proof is with double summation:

$$ \begin{eqnarray} \sum_{i=1}^n \sum_{j=1}^n (x_i - x_j)^2 &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x} + \bar{x} - x_j)^2 \\ &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x})^2 + (x_j - x_j)^2 - 2(x_i - \bar{x})(x_j - \bar{x})\\ &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x})^2 + (x_j - x_j)^2\\ &=& 2n \sum_{i=1}^n (x_i - \bar{x})^2 \end{eqnarray} $$

Where the third term in the RHS of the second line is orthogonal and sums to 0 .

Answer 2

It's a non-obvious thing, so you'll have to chew on the math a little bit.

First thing to do: show that it is sufficient to solve this for the one dimensional case.

It's not too hard, so this is a good exercise to practice your statistics 101 skills. Give it a try. Try approaching it from both sides, and use the binomial expansion.

The key result in here is the Konig-Huygens theorem.