We present a new algorithm for spectral clustering based on a column-pivoted QR factorization that may be directly used for cluster assignment or to provide an initial guess for k-means. Our algorithm is simple to implement, direct, and requires no initial guess. Furthermore, it scales linearly in the number of nodes of the graph and a randomized variant provides significant computational gains. Provided the subspace spanned by the eigenvectors used for clustering contains a basis that resembles the set of indicator vectors on the clusters, we prove that both our deterministic and randomized algorithms recover a basis close to the indicators in Frobenius norm. Finally, we experimentally demonstrate that the performance of our algorithm tracks recent information theoretic bounds for exact recovery in the stochastic block model.
@cite_20: The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find 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 computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing 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.
An algorithm using a column-pivoted QR for cluster assignment of general point-cloud data with an assumption of orthogonality amongst the clusters has previously appeared in the literature in the context of spectral relaxation of the k-means objective @cite_20 . Curiously, though we find the basic idea to be powerful, this algorithmic approach seems to have been ignored and we can find no further reference to it. We expand upon this work, taking advantage of algorithmic improvements appearing in the computational chemistry literature for greater efficiency. Further, by addressing the sparse adjacency matrix case instead of the Gram matrix of point-cloud data, we are able to strongly motivate our approach based on proven spectral properties of model graphs and graphs with assumed underlying cluster structure.