Convergence of online $k$-means

Sanjoy Dasgupta, Gaurav Mahajan, Geelon So

We prove asymptotic convergence for a general class of $k$-means algorithms performed over streaming data from a distribution: the centers asymptotically converge to the set of sta…