k-Means Clustering Is Matrix Factorization

Abstract

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.

Cited by in corpus (7)

• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• Coordinating Filters for Faster Deep Neural Networks
• Towards Fair Deep Clustering With Multi-State Protected Variables
• Kernel Correlation-Dissimilarity for Multiple Kernel k-Means Clustering
• Robust and Efficient Fuzzy C-Means Clustering Constrained on Flexible Sparsity
• Smart, Adaptive Energy Optimization for Mobile Web Interactions
• The PRIMPing Routine -- Tiling through Proximal Alternating Linearized Minimization