MLT Quiz 1: 23 February 2025 (January 2025 term)

For the Lloyd's algorithm, what would be the correct relationship among the following three quantities?

(1) $\sum_{i=1}^{n} ||x_i - \mu^t_{z_i^{t+1}}||^2$,
(2) $\sum_{i=1}^{n} ||x_i - \mu^t_{z_i^t}||^2$,
(3) $\sum_{i=1}^{n} ||x_i - \mu^{t+1}_{z_i^{t+1}}||^2$

where $\mu^t_{z_i^t}$ and $\mu^{t+1}_{z_i^{t+1}}$ refer to means of cluster $z_i$ in iterations, $t$ and $t+1$ respectively, and $\mu^t_{z_i^{t+1}}$ refer to the mean of the cluster $z_i$ where $x_i$ is going to move in the next iteration, i.e., $(t+1)$-th iteration.