In this variance based k-clustering paper they claim that for a cluster with S points:

$$|S|\sum_{i \in S}{\|x_i-\bar{x}\|^2} = \sum_{a,b \in S,\ a<b}{\|x_a-x_b\|^2}\,.$$

Why is that? can you please show me the derivation?


This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change.

Let us denote $|S|$ by $n$. The left hand side becomes $n \sum_{i \in S} ||x_i||^2$. The right hand side can be simplified as follows:

$$ \sum_{a < b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a||^2 + ||x_b||^2 - 2 x_a \cdot x_b $$

The first equality follows from the fact that $||x_a - x_b||^2 = ||x_b - x_a||^2$. The second is simple expansion of quadratic expression of vectors.

If you split the sum and notice that the first two terms are equal to $n \sum_{i} ||x_i||^2$. You get that $\sum_{a, b} x_a \cdot x_b = 0$. This is easy to see since:

$$ \sum_{a, b} x_a \cdot x_b = \sum_{a} x_a \cdot \sum_b{} x_b = (\sum_{i} x_i)^2 = (n \bar{x})^2 $$

which is zero since the mean vector is zero.

Of course this calculation is all well known as an identity on variance. If you have a random variable $x$ such that $Pr[x = x_i] = 1/n$. Then, your left hand side is $n^2 Var(x)$ and the right hand side is the right hand side of the last equation stated here.

  • $\begingroup$ cool. In the first equality you used the fact that $||x_a-x_a||^2 = 0$ $\endgroup$ – ihadanny Nov 2 '16 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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