Confusion about convergence of k-means algorithm

Question

Andrew Ng's lecture notes here has the statement "it is possible for k-means to oscillate between a few different clusterings — i.e., a few different values for c and/or μ—that have exactly the same value of J, but this almost never happens in practice.)"

I thought that k-means is theoretically guaranteed to converge to a local optima. If so, how come it would oscillate between different clusterings? Maybe it is guaranteed to converge in terms of the optimized cost function (J), but not in terms of the cluster assignments? Is that the case mentioned above?

Answer 1

During the iterations, $J$, a nonnegative function decreases, hence by monotone convergence theorem, the objective value converges.

However, the convergence of the objective function does not rule out the possibilites of $(\hat{c}, \hat{\mu})$ and $(\tilde{c}, \tilde{\mu})$ having the same objective value.