Efficient semidefinite spectral clustering via lagrange duality.

Area of Science:

• Machine Learning
• Data Mining
• Computer Vision

Background:

• Spectral clustering (SC) is a powerful technique for data partitioning.
• Traditional SC methods often struggle with the positive semidefinite (p.s.d.) constraint and Frobenius normalization.
• Existing semidefinite spectral clustering (SSC) approaches face computational complexity challenges.

Purpose of the Study:

• To develop an efficient semidefinite spectral clustering (SSC) algorithm.
• To address the positive semidefinite (p.s.d.) constraint in spectral clustering.
• To improve the accuracy of affinity matrix approximation in SSC.

Main Methods:

• Formulating SSC as a semidefinite programming (SDP) problem.
• Developing a dual algorithm based on Lagrange duality to solve the SDP efficiently.
• Proposing two algorithm versions: one for reduced memory usage, another for faster convergence.

Main Results:

• The proposed dual algorithm accurately finds the closest doubly stochastic approximation to the affinity matrix by considering the p.s.d. constraint.
• The algorithm exhibits significantly lower time complexity compared to standard interior-point SDP solvers.
• Experimental results show superior clustering performance on UCI and image datasets.

Conclusions:

• The proposed dual algorithm provides a more efficient and accurate solution for semidefinite spectral clustering (SSC).
• The method demonstrates enhanced scalability, outperforming standard interior-point SDP solvers for large-scale problems.
• This approach advances spectral clustering by effectively handling p.s.d. constraints and improving computational efficiency.