k-Means Clustering Is Matrix Factorization

While we know this (see the Advanced Matrix Factorization Jungle Page.), Christian really wanted to get to the bottom of this in writing. Thank you !

 

This closed form solution makes it more like a subspace clustering algorithm, from the Jungle page

 

Subspace Clustering: A = AX  with unknown X, solve for sparse/other conditions on X  

 

 Here is the derivation: k-Means Clustering Is Matrix Factorization by Christian Bauckhage

 

We show that the objective function of conventional k-means clustering can be expressed as the Frobenius norm of the difference of a data matrix and a low rank approximation of that data matrix. In short, we show that k-means clustering is a matrix factorization problem. These notes are meant as a reference and intended to provide a guided tour towards a result that is often mentioned but seldom made explicit in the literature.

Related:

• Sunday Morning Insight: Relax, no need to round: integrality of clustering formulations
• Sunday Morning Insight: Why You Should Care About Phase Transitions in Clustering

 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.