Spectral clustering is a widely used technique for data partitioning, due to its ability to capture complex and non-linear cluster structures through the spectral properties of similarity graphs. A crucial and still open issue within this framework is the automatic determination of the number of clusters. In this paper, we propose ALLE (ALgebraic Laplacian Estimator), a fully automatic method for estimating the number of clusters directly from the Laplacian matrix. The method formulates cluster recovery as a penalized optimization problem based on a low-rank plus sparse decomposition of the normalized Laplacian. The low-rank structure, recovered via nuclear norm penalization, encodes the intrinsic cluster structure, while an -norm penalty accounts for noise and perturbations. The resulting optimization problem is efficiently solved using a proximal gradient algorithm alternating singular value and soft thresholding.
Di Nuzzo, C., Farne, M. (2026). An Algebraic Approach to Recover the Number of Clusters from the Laplacian Matrix. Cham : Springer [10.1007/978-3-032-30881-8_38].
An Algebraic Approach to Recover the Number of Clusters from the Laplacian Matrix
Farne, Matteo
2026
Abstract
Spectral clustering is a widely used technique for data partitioning, due to its ability to capture complex and non-linear cluster structures through the spectral properties of similarity graphs. A crucial and still open issue within this framework is the automatic determination of the number of clusters. In this paper, we propose ALLE (ALgebraic Laplacian Estimator), a fully automatic method for estimating the number of clusters directly from the Laplacian matrix. The method formulates cluster recovery as a penalized optimization problem based on a low-rank plus sparse decomposition of the normalized Laplacian. The low-rank structure, recovered via nuclear norm penalization, encodes the intrinsic cluster structure, while an -norm penalty accounts for noise and perturbations. The resulting optimization problem is efficiently solved using a proximal gradient algorithm alternating singular value and soft thresholding.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.



