Adapted from CIL 2012 Master solution.
1. Convergence of the K-Means algorithm
(Convergence of the K-Means Algorithm) The K-means algorithm converges since at each iteration it either reduces or keeps the same the value of the objective function J, where
with the constraint
When initialising the algorithm we set
This makes the value of minimal considering that we have to assign the value to one and only one and to all others.
We note that the centroids are updated with this equation:
The derivative of the constraint with respect to yields:
which can be reformulated to:
which then yields the equation for the centroid update step.
Computing the second derivative of results in .
Considering the argument in step 1 and 2 convergence guaranteed for the cost function:
2. Recasting K-Means into a Matrix Factorisation Problem
We note that step 2 of K-means minimises
with the constraint and the values being either or .
thus is minimised with .
Computing the derivative of
since is either 0 or 1 we can conclude that the 3rd step solves
It follows that K-means minimises the objective matrix factorisation problem given by: