A new approach to clustering using eigen decomposition

We propose a novel approach to relational clustering: Given a matrix of pairwise similarity values between objects our algorithm computes a partition of the objects such that similar objects belong to the same cluster and dissimilar objects belong to different clusters. The proposed approach is based on the assumption that the given similarities are products of cluster membership variables. It is based on eigen vector decomposition and minimizes the squared error between the similarities and the products of membership vectors in an efficient, non-iterative way with guaranteed global optimality. In experiments with real world data we show superior performance to conventional iterative clustering approaches.