Spectral Relaxation for K-means Clustering

The popular K-means clustering partitions a data set by minimiz-ing a sum-of-squares cost function. A coordinate descend method is then used to nd local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by com-puting a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by comput-ing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.