title: Efficient semidefinite spectral clustering via lagrange duality.
abstract: We propose an efficient approach to semidefinite spectral clustering (SSC), which addresses the Frobenius normalization with the positive semidefinite (p.s.d.) constraint for spectral clustering. Compared with the original Frobenius norm approximation-based algorithm, the proposed algorithm can more accurately find the closest doubly stochastic approximation to the affinity matrix by considering the p.s.d. constraint. In this paper, SSC is formulated as a semidefinite programming (SDP) problem. In order to solve the high computational complexity of SDP, we present a dual algorithm based on the Lagrange dual formalization. Two versions of the proposed algorithm are proffered: one with less memory usage and the other with faster convergence rate. The proposed algorithm has much lower time complexity than that of the standard interior-point-based SDP solvers. Experimental results on both the UCI data sets and real-world image data sets demonstrate that: 1) compared with the state-of-the-art spectral clustering methods, the proposed algorithm achieves better clustering performance and 2) our algorithm is much more efficient and can solve larger-scale SSC problems than those standard interior-point SDP solvers.
authors.forename: Yan
authors.initials: Y
authors.lastname: Yan
authors.forename: Chunhua
authors.initials: C
authors.lastname: Shen
authors.forename: Hanzi
authors.initials: H
authors.lastname: Wang