Recovering the Number of Clusters From a Laplacian Matrix by Nuclear Norm Penalization

Spectral clustering is a powerful technique for data partitioning, but determining the optimal number of clusters remains challenging. This article introduces ALLE (ALgebraic Laplacian Estimator), an automatic method for estimating the number of clusters within the spectral clustering framework. By formulating the cluster recovery problem as a penalized minimization task, ALLE is able to systematically recover the number of clusters and the embedding space by assuming for the Laplacian matrix a low-rank plus sparse decomposition. Specifically, ALLE recovers the low-rank representation of the Laplacian matrix using nuclear norm plus ℓ1-norm penalization. ALLE is computed via a proximal gradient algorithm alternating Singular Value Thresholding and Soft Thresholding, and it’s very good performance is shown via a simulation study.