How to explain the connection between SVD and clustering?

Question

Is there an intuitive explanation for how SVD is related to co-clustering when performing SVD on a covariance matrix?

(i.e. the SVD is performed on the matrix $E[X Y^{\top}]$ where $X \in \mathbb{R}^n$ and $Y \in \mathbb{R}^m$.)

How does the projections $U$ and $V$ in the decomposition $U \Sigma V^{\top}$ relate to clustering? If I take some instance of $X$ and project it through $U$, what do I get?

(note I am talking about thin svd, so that $\Sigma$ is of dimensions lower than $n$ and $m$, and $U^{\top}x$ for some instance $x$ of $X$ is projected into that lower dimension.)

Answer 1

Perhaps this will help, taken from the Wikipedia article on PCA (PCA is very similar to SVD):

"Relation between PCA and K-means clustering

It has been shown recently (2001,2004) that the relaxed solution of K-means clustering, specified by the cluster indicators, is given by the PCA principal components, and the PCA subspace spanned by the principal directions is identical to the cluster centroid subspace specified by the between-class scatter matrix. Thus PCA automatically projects to the subspace where the global solution of K-means clustering lies, and thus facilitates K-means clustering to find near-optimal solutions."

The way I see it, dimensionality reduction is distinct from clustering but it can help clustering high-dimensional data by reducing to a "useful" low dimensional representation.

Answer 2

I had the similar question in mind when trying to comparing methods like SVD, PCA, and LSA (latent Sementic Analysis), and NMF (Non-negative Matrix Factorization).

To concur Bitwise's point, the NMF wikipedia page http://en.wikipedia.org/wiki/Non-negative_matrix_factorization states that "It has been shown [27][28] NMF is equivalent to a relaxed form of K-means clustering: matrix factor W contains cluster centroids and H contains cluster membership indicators, when using the least square as NMF objective. This provides theoretical foundation for using NMF for data clustering."

The citations are:

[27] C. Ding, X. He, H.D. Simon (2005). "On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering". Proc. SIAM Int'l Conf. Data Mining, pp. 606-610. May 2005

[28] Ron Zass and Amnon Shashua (2005). "A Unifying Approach to Hard and Probabilistic Clustering". International Conference on Computer Vision (ICCV) Beijing, China, Oct., 2005.