Fast and accurate spectral clustering via augmented Lagrangian

Authors

Ramin Toosi, Mohammadreza Sadeghi, Hossein B Yazdi, Mohammad Ali Akhaee

Abstract

Spectral clustering is one of the most popular general-purpose clustering methods due to its effectiveness and applications in various contexts. Spectral clustering, in its original form, is a two-step method. First, a new representation in which data points could be easily clustered is found. Then, a simple clustering algorithm like k-means is applied. In this paper, we propose a novel and highly accurate method for spectral clustering, called spectral clustering via augmented Lagrangian (SCAL). Specifically, we formalize the spectral clustering problem as a constrained optimization problem, which is challenging to solve due to the orthogonality constraint. This constraint ensures the orthogonality of the dimensions of the new representation where samples of a specific cluster are as close as possible to each other. We then use the augmented Lagrangian method to dispose of the orthogonality constraint and form a new unconstrained cost function. Finally, the new unconstrained problem is solved using the Adam optimization technique. The proposed method is compared to the state-of-the-art methods using synthetic and real-world datasets. Results show that SCAL significantly outperforms other methods in terms of accuracy.