This is a work we have posted and given a spotlight talk on NIPS 09 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications (DISCML). You can find it on:
Fast Gradient Clustering (FGC) tackles the two fundamental clustering problems: the minimal sum-of-squares (MSSC) and normalized cut (N-cut). Both of these two problems are 0-1 programming with nonlinear object function, so various approximation algorithms are proposed for a practical solution. The most well-known are K-means and Spectral clustering.
However, the two approximation algorithms are loose relaxations of the original problem and thus has several shortcomings. K-means is sensitive to the initial clustering centroids. Spectral clustering is a loose convex relaxation and post-processing based on K-means is indispensable, which ruins the global optimality of the solutions.
In Fast Gradient Clustering, we adopt an unified and tighter SDP relaxation of the original clustering problems and develop an algorithm much faster then standard SDP solves to optimize it. The dual problem of the SDP relaxation is formulated as an unconstrained maximum eigenvalue minimization and then smoothed. FGC applies Nesterov’s method to optimize the smooth dual problem with fast convergence rate $O(1/k^2)$ and merely gradient decent time cost in each iterate. The gradient computation can further be accelerated by approximated matrix exponential calculation.
The experiments shows FGC is more stable in optimization and its clustering results are superior than K-means and Spectral clustering on common used datasets.
FGC has a lot of potential applications in image segmentation and text clustering owing to its robustness, high accuracy and fast speed.