A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers

Prateek R. Srivastava (), Purnamrita Sarkar () and Grani A. Hanasusanto ()
Additional contact information
Prateek R. Srivastava: Graduate Program in Operations Research and Industrial Engineering (ORIE), University of Texas at Austin, Austin, Texas 78712
Purnamrita Sarkar: Department of Statistics and Data Sciences, University of Texas at Austin, Austin, Texas 78712
Grani A. Hanasusanto: Graduate Program in Operations Research and Industrial Engineering, University of Texas at Austin, Austin, Texas 78712

Operations Research, 2023, vol. 71, issue 1, 224-244

Abstract: We consider the problem of clustering data sets in the presence of arbitrary outliers. Traditional clustering algorithms such as k -means and spectral clustering are known to perform poorly for data sets contaminated with even a small number of outliers. In this paper, we develop a provably robust spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of data points. We analyze the performance of our algorithm under the assumption that the “good” data points are generated from a mixture of sub-Gaussians (we term these “inliers”), whereas the outlier points can come from any arbitrary probability distribution. For this general class of models, we show that the misclassification error decays at an exponential rate in the signal-to-noise ratio, provided the number of outliers is a small fraction of the inlier points. Surprisingly, this derived error bound matches with the best-known bound for semidefinite programs (SDPs) under the same setting without outliers. We conduct extensive experiments on a variety of simulated and real-world data sets to demonstrate that our algorithm is less sensitive to outliers compared with other state-of-the-art algorithms proposed in the literature.

Keywords: Machine Learning and Data Science; spectral clustering; sub-Gaussian mixture models; kernel methods; semidefinite programming; outlier detection; asymptotic analysis (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2317 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:1:p:224-244

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().