Stella X. Yu : Papers / Google Scholar

Multiclass Spectral Clustering
Stella X. Yu and Jianbo Shi
International Conference on Computer Vision, Nice, France, 11-17 Oct 2003
Paper | Slides

We propose a principled account on multiclass spectral clustering. Given a discrete clustering formulation, we first solve a relaxed continuous optimization problem by eigendecomposition. We clarify the role of eigenvectors as a generator of all optimal solutions through orthonormal transforms. We then solve an optimal discretization problem, which seeks a discrete solution closest to the continuous optima. The discretization is efficiently computed in an iterative fashion using singular value decomposition and non-maximum suppression. The resulting discrete solutions are nearly global-optimal. Our method is robust to random initialization and converges faster than other clustering methods. Experiments on real image segmentation are reported.

clustering, spectral graph partitioning, kmeans, image segmentation