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

Spectral clustering is a powerfultechniquefordatapartitioning,butdeterminingtheoptimalnumberofclustersremainschallenging. 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-normpenalization.ALLEiscomputedviaaproximalgradientalgorithmalternatingSingularValueThresholdingandSoft Thresholding, and it’s very good performance is shown via a simulation study.