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.
2026
Statistical Science: From Theory to Applied Research III. SIS-FENStatS 2026
230
235
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].
Di Nuzzo, Cinzia; Farne, Matteo
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/1088735
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact