Efficient semidefinite spectral clustering via lagrange duality
| dc.contributor.author | Yan, Y. | |
| dc.contributor.author | Wang, H. | |
| dc.contributor.author | Shen, C. | |
| dc.date.issued | 2014 | |
| dc.description.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. | |
| dc.description.statementofresponsibility | Yan Yan, Chunhua Shen and Hanzi Wang | |
| dc.identifier.citation | IEEE Transactions on Image Processing, 2014; 23(8):3522-3534 | |
| dc.identifier.doi | 10.1109/TIP.2014.2329453 | |
| dc.identifier.issn | 1057-7149 | |
| dc.identifier.issn | 1941-0042 | |
| dc.identifier.orcid | Shen, C. [0000-0002-8648-8718] | |
| dc.identifier.uri | http://hdl.handle.net/2440/85745 | |
| dc.language.iso | en | |
| dc.publisher | Institute of Electrical and Electronics Engineers (IEEE) | |
| dc.rights | © 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission | |
| dc.source.uri | https://doi.org/10.1109/tip.2014.2329453 | |
| dc.subject | Spectral clustering; doubly stochastic normalization; semidefinite programming; Lagrange duality | |
| dc.title | Efficient semidefinite spectral clustering via lagrange duality | |
| dc.type | Journal article | |
| pubs.publication-status | Published |