Relation between pairwise distance sum and sum of distance to mean (gap statistic)

Question

I'm trying to understand the gap statistic used for optimal choice of $k$ in k-means clustering. I'm trying to understand part of the explanation which includes this equality:

$D_k=\sum_{ij}\Vert x_i-x_j\Vert^2=2n\sum_{i}\Vert x_i-\mu\Vert^2$

Where $\sum_{ij}\Vert x_i-x_j\Vert^2$ is the sum of pairwise distances in a cluster and $\mu$ is the centroid for that cluster. I don't understand how that is derived.

I've had a look at this question (Link between variance and pairwise distances within a variable) and the answer makes sense to me.

Assuming our data is centered about the (known) mean, which it is, by definition of the centroid, then the equality holds:

$\sum_{ij}(X_i-X_j)^2=2\sum X_i^2$

But I don't see how $2\sum X_i^2 = 2n\sum_{i}\Vert x_i-\mu\Vert^2$

If $2\sum X_i^2 = 2\operatorname{Var}(X)$

Then wouldn't $2\sum X_i^2 = \frac{2}{n}\sum_i(x_i-\mu)^2$?

Answer 1

To show that $$\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}\left\|x_i - x_j\right\|^2 =2n\sum\limits_{i=1}^{n}\left\|x_i- \mu\right\|^2,$$ firstly note that $$\mu = \frac{1}{n}\sum\limits _{j =1}^{n}x_j.$$ Hence $$\begin{align*} 2n\sum\limits_{i=1}^{n}\left\|x_i- \mu\right\|^2 &= 2n\sum\limits_{i=1}^{n}\left\|x_i- \frac{1}{n}\sum\limits _{j =1}^{n}x_j\right\|^2 \\ &= 2n \sum\limits_{i=1}^{n}\left( \left\|x_i\right\|^2 -2x_i^T\left(\frac{1}{n}\sum\limits _{j =1}^{n}x_j\right) + \left\| \frac{1}{n}\sum\limits _{j =1}^{n}x_j\right\|^2 \right) \quad (\text{using }\left\|a-b\right\|^2 = \left\|a\right\|^2 -2a^Tb + \left\|b\right\|^2) \\ &= 2n \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 -4 \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j + 2n^2 \left\| \frac{1}{n}\sum\limits _{j =1}^{n}x_j\right\|^2 \\ &= 2n \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 -4 \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j + 2\left\| \sum\limits _{j =1}^{n}x_j\right\|^2 \\ &= 2n \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 -4 \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j + 2\sum\limits_{i=1}^{n}\sum\limits _{j=1}^{n}x_i^Tx_j \\ &= 2n \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 -2\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j \\ &= n \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 -2\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j + n\sum\limits_{j=1}^{n}\left\|x_j\right\|^2 \\ &= \sum\limits_{i=1}^{n}\sum\limits _{j=1}^{n}\left\|x_i\right\|^2 -2\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j + \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\left\|x_j\right\|^2 \\ &= \sum\limits_{i=1}^{n}\sum\limits _{j=1}^{n} \left(\left\|x_i\right\|^2 -2x_i^T x_j + \left\|x_j\right\|^2\right) \\ &= \sum\limits_{i=1}^n\sum\limits_{j=1}^{n}\left\|x_i - x_j\right\|^2, \end{align*}$$ as required.

---

Note that we made use of several algebra facts along the way, such as $$\left\|\sum\limits_{j=1}^n x_j\right\|^2 = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}x_i^T x_j,$$ and that summing something that does not depend on one of the summation indices introduces a factor of $n$, e.g. $$\sum\limits_{i=1}^{n}\left\|\frac{1}{n}\sum\limits_{j=1}^n x_j\right\|^2 = n \left\|\frac{1}{n}\sum\limits_{j=1}^n x_j\right\|^2$$ and $$n\sum\limits_{j=1}^{n}\left\|x_j\right\|^2 = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\left\|x_j\right\|^2.$$

Answer 2

A simpler way, without losing generality, is to take the center of gravity as the origin of the space (even if it means doing a translation of the cluster).:

$$ \mu = \frac{1}{n}\sum\limits _{j =1}^{n}x_j = 0 $$

So the sum of distances to mean is:

$$ I = \sum\limits_{i=1}^{n}\left\|x_i\right\|^2 $$

And the pairwise distance sum is:

$$ D = \sum\limits_{i=1}^n\sum\limits_{j=1}^{n}\left\|x_i - x_j\right\|^2 $$

With:

$$\left\|x_i - x_j\right\|^2 = \left\|x_i\right\|^2 + \left\|x_j\right\|^2 - 2<x_i, x_j>$$

Then:

$$ \begin{align*} D &= \sum\limits_{j=1}^n\left(\sum\limits_{i=1}^n \left\|x_i\right\|^2\right) + \sum\limits_{i=1}^n\left(\sum\limits_{j=1}^{n}\left\|x_j\right\|^2\right) - 2<\sum\limits_{i=1}^n x_i, \sum\limits_{j=1}^{n}x_j> \\ &= 2 n I - 2 \left\|n\mu\right\|^2 \end{align*} $$

It gives the result:

$$ \sum_{1\leq i \leq j \leq n}\Vert x_i-x_j\Vert^2=2n\sum_{i=1}^{n}\Vert x_i-\mu\Vert^2 $$