Clustering in large graphs and matrices

We consider the problem of dividing a set of m points in Euclidean n-space into k clusters (m, n are variable while k is fixed), so as to minimize the sum of distances squared of each point to its “cluster center”. This formulation differs in two ways from the most frequently considered clustering problems in the literature, namely, here we have k fixed and m, n variable, and we use the sum of squared distances as our measure; we will argue that our problem is natural in many contexts. We consider a relaxation of the discrete problem: find the k-dimensional subspace V so that the sum of distances squared to V (of the m points) is minimized. We show: (i) The relaxation can be solved by the Sin-gular Value Decomposition (SVD) of Linear Algebra. (ii) The solution of the relaxation can be used to get a 2-approximation algorithm for the original problem. More importantly, (iii) we argue that in fact the relax-ation provides a generalized clustering which is useful in its own right. Finally, (iv) we show that the SVD of a randomly chosen submatrix (according to a suit-able probability distribution) of the matrix provides an approximation to the SVD of the whole matrix, thus yielding a very fast randomized algorithm. This cam be applied to problems of very large size which typically arise in modern applications.