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

References

• Altman NS (1992) An introduction to kernel and nearest-neighbor nonparametric regression. Amer. Statist. 46(3):175–185.Crossref, Google Scholar
• Amini AA, Levina E (2018) On semidefinite relaxations for the block model. Ann. Statist. 46(1):149–179.Crossref, Google Scholar
• Amini AA, Razaee ZS (2021) Concentration of kernel matrices with application to kernel spectral clustering. Ann. Statist. 49(1):531–556.Crossref, Google Scholar
• Amini AA, Chen A, Bickel PJ, Levina E (2013) Pseudo-likelihood methods for community detection in large sparse networks. Ann. Statist. 41(4):2097–2122.Crossref, Google Scholar
• Ana L, Jain AK (2003) Robust data clustering. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Madison WI, volume 2.Google Scholar
• Arcones MA (1995) A Bernstein-type inequality for U-statistics and U-processes. Statist. Probab. Lett. 22(3):239–247.Crossref, Google Scholar
• Arora S, Kannan R (2001) Learning mixtures of arbitrary Gaussians. Proc. 33rd Annual ACM Symposium on Theory of Computing, 247–257 (ACM, New York).Google Scholar
• Awasthi P, Sheffet O (2012) Improved spectral-norm bounds for clustering: Approximation, randomization, and combinatorial optimization. Lecture Notes in Comput. Sci., 7408 (Springer, Heidelberg), 37–49.Crossref, Google Scholar
• Awasthi P, Bandeira AS, Charikar M, Krishnaswamy R, Villar S, Ward R (2015) Relax, no need to round: Integrality of clustering formulations. Proc. 2015 Conf. Innovations in Theoretical Comput. Sci., 191–200 (ACM, New York).Google Scholar
• Bickel PJ, Chen A, Levina E (2011) The method of moments and degree distributions for network models. Ann. Statist. 39(5):2280–2301.Crossref, Google Scholar
• Bojchevski A, Matkovic Y, Günnemann S (2017) Robust spectral clustering for noisy data: Modeling sparse corruptions improves latent embeddings. Proc. 23rd ACM SIGKDD Interat. Conf. Knowledge Discovery and Data Mining (ACM, New York), 737–746.Google Scholar
• Cai TT, Li X (2015) Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann. Statist. 43(3):1027–1059.Crossref, Google Scholar
• Chaudhuri K, Kakade SM, Livescu K, Sridharan K (2009) Multi-view clustering via canonical correlation analysis. Proc. 26th Annual Internat. Conf. Machine Learn., 129–136.Google Scholar
• Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13(1):21–27.Crossref, Google Scholar
• Cuesta-Albertos JA, Gordaliza A, Matrán C (1997) Trimmed k-means: An attempt to robustify quantizers. Ann. Statist. 25(2):553–576.Crossref, Google Scholar
• Dasgupta S (1999) Learning mixtures of Gaussians. 40th Annual Sympos. on Foundations of Comput. Sci. (IEEE), 634–644.Google Scholar
• Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. B. 39(1):1–22.Google Scholar
• Dhillon IS, Guan Y, Kulis B (2004) Kernel k-means: spectral clustering and normalized cuts. Proc. Tenth ACM SIGKDD Internat. Conf. Knowledge Discovery and Data Mining (ACM, New York), 551–556.Google Scholar
• Ding C, He X (2004) K-nearest-neighbor consistency in data clustering: incorporating local information into global optimization. Proc. 2004 ACM Symposium on Applied Comput. (ACM, New York), 584–589.Google Scholar
• Du M, Ding S, Jia H (2016) Study on density peaks clustering based on k-nearest neighbors and principal component analysis. Knowl. Base. Syst. 99:135–145.Crossref, Google Scholar
• Dua D, Graff C (2017) UCI machine learning repository. http://archive.ics.uci.edu/ml.Google Scholar
• El Karoui N (2010) On information plus noise kernel random matrices. Ann. Statist. 38(5):3191–3216.Crossref, Google Scholar
• Fei Y, Chen Y (2018) Hidden integrality of SDP relaxations for sub-Gaussian mixture models. Proc. 31st Conf. on Learn. Theory, vol. 75, 1931–1965.Google Scholar
• Fishkind DE, Sussman DL, Tang M, Vogelstein JT, Priebe CE (2013) Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown. SIAM J. Matrix Anal. Appl. 34(1):23–39.Crossref, Google Scholar
• Forero PA, Kekatos V, Giannakis GB (2012) Robust clustering using outlier-sparsity regularization. IEEE Trans. Signal Process. 60(8):4163–4177.Crossref, Google Scholar
• Franti P, Virmajoki O, Hautamaki V (2006) Fast merative clustering using a k-nearest neighbor graph. IEEE Trans. Pattern Anal. Mach. Intell. 28(11):1875–1881.Crossref, Google Scholar
• Giraud C, Verzelen N (2018) Partial recovery bounds for clustering with the relaxed K-means. Math. Stat. Learning 1(3):317–374.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM. 42(6):1115–1145.Crossref, Google Scholar
• Guédon O, Vershynin R (2016) Community detection in sparse networks via Grothendieck’s inequality. Probab. Theory Related Fields 165(3-4):1025–1049.Crossref, Google Scholar
• Hastie T, Tibshirani R (1996) Discriminant adaptive nearest neighbor classification and regression. Adv. Neural Inf. Process. Syst. 8:409–415.Google Scholar
• Heckel R, Bölcskei H (2015) Robust subspace clustering via thresholding. IEEE Trans. Inform. Theory 61(11):6320–6342.Crossref, Google Scholar
• Heckel R, Tschannen M, Bölcskei H (2017) Dimensionality-reduced subspace clustering. Info. Inference J IMA 6(3):246–283.Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• Holland PW, Laskey KB, Leinhardt S (1983) Stochastic blockmodels: First steps. Soc. Networks. 5(2):109–137.Crossref, Google Scholar
• Iguchi T, Mixon DG, Peterson J, Villar S (2015) On the tightness of an SDP relaxation of k-means. Preprint, submitted May 18, https://arxiv.org/abs/1505.04778.Google Scholar
• Joseph A, Yu B (2016) Impact of regularization on spectral clustering. Ann. Statist. 44(4):1765–1791.Crossref, Google Scholar
• Kumar A, Kannan R (2010) Clustering with spectral norm and the k-means algorithm. 51st Annual IEEE Symposium on Foundations of Computer Science (IEEE, New York), 299–308.Google Scholar
• Kumar A, Sabharwal Y, Sen S (2004) A simple linear time (1 + ε)-approximation algorithm for k-means clustering in any dimensions. 45th Annual IEEE Symposium on Foundations of Computer Science (IEEE, New York), 454–462.Google Scholar
• Kushagra S, McNabb N, Yu Y, Ben-David S (2017) Provably noise-robust, regularised k-means clustering. Preprint, submitted November 30, https://arxiv.org/abs/1711.11247.Google Scholar
• Le CM, Levina E, Vershynin R (2015) Sparse random graphs: regularization and concentration of the laplacian. Preprint submitted April 23, https://arxiv.org/abs/1502.03049.Google Scholar
• Lei J, Rinaldo A (2015) Consistency of spectral clustering in stochastic block models. Ann. Statist. 43(1):215–237.Crossref, Google Scholar
• Löffler M, Zhang AY, Zhou HH (2021) Optimality of spectral clustering in the Gaussian mixture model. Ann. Statist. 49(5):2506–2530.Crossref, Google Scholar
• Li Z, Liu J, Chen S, Tang X (2007) Noise robust spectral clustering. IEEE 11th International Conference on Computer Vision, (IEEE, New York) 1–8.Google Scholar
• Li X, Li Y, Ling S, Strohmer T, Wei K (2020) When do birds of a feather flock together? k-means, proximity, and conic programming. Math. Program. 179(1–2):295–341.Crossref, Google Scholar
• Lloyd S (1982) Least squares quantization in PCM. IEEE Trans. Inform. Theory. 28(2):129–137.Crossref, Google Scholar
• Lu Y, Zhou HH (2016) Statistical and computational guarantees of Lloyd’s algorithm and its variants. Preprint, December 7, https://arxiv.org/abs/1612.02099.Google Scholar
• McSherry F (2001) Spectral partitioning of random graphs. Proc. 42nd IEEE Sympos. Foundations of Computer Science (IEEE, New York), 529–537.Google Scholar
• Mixon DG, Villar S, Ward R (2017) Clustering subgaussian mixtures by semidefinite programming. Info. Inference J IMA 6(4):389–415.Crossref, Google Scholar
• Montanari A, Sen S (2016) Semidefinite programs on sparse random graphs and their application to community detection. Proc. 48th Annual Sympos. Theory Comput. (ACM, New York), 814–827.Google Scholar
• Newman ME (2006) Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA, 103(23):8577–8582.Crossref, Google Scholar
• Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: Analysis and an algorithm. Adv. Neural Inform. Processing Systems, 849–856.Google Scholar
• Pearson K (1936) Method of moments and method of maximum likelihood. Biometrika 28(1–2):34–59.Crossref, Google Scholar
• Peng J, Wei Y (2007) Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1):186–205.Crossref, Google Scholar
• Qin T, Rohe K (2013) Regularized spectral clustering under the degree-corrected stochastic blockmodel. Adv. Neural Inform. Processing Systems, 3120–3128.Google Scholar
• Rohe K, Chatterjee S, Yu B (2011) Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist. 39(4):1878–1915.Crossref, Google Scholar
• Rujeerapaiboon N, Schindler K, Kuhn D, Wiesemann W (2019) Size matters: Cardinality-constrained clustering and outlier detection via conic optimization. SIAM J. Optim. 29(2):1211–1239.Crossref, Google Scholar
• Schiebinger G, Wainwright MJ, Yu B (2015) The geometry of kernelized spectral clustering. Ann. Statist. 43(2):819–846.Crossref, Google Scholar
• Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8):888–905.Crossref, Google Scholar
• Shi T, Belkin M, Yu B (2009) Data spectroscopy: Eigenspaces of convolution operators and clustering. Ann. Statist. 37(6B):3960–3984.Crossref, Google Scholar
• Soltanolkotabi M, Candés EJ (2012) A geometric analysis of subspace clustering with outliers. Ann. Statist. 40(4):2195–2238.Crossref, Google Scholar
• Soltanolkotabi M, Elhamifar E, Candès EJ (2014) Robust subspace clustering. Ann. Statist. 42(2):669–699.Crossref, Google Scholar
• Sussman DL, Tang M, Fishkind DE, Priebe CE (2012) A consistent adjacency spectral embedding for stochastic blockmodel graphs. J. Amer. Statist. Assoc. 107(499):1119–1128.Crossref, Google Scholar
• Van der Vaart AW (2000) Asymptotic Statistics, vol. 3. (Cambridge University Press, Cambridge, UK).Google Scholar
• Vempala S, Wang G (2004) A spectral algorithm for learning mixture models. J. Comput. System Sci. 68(4):841–860.Crossref, Google Scholar
• Verdinelli I, Wasserman L (2018) Analysis of a mode clustering diagram. Electron. J. Stat. 12(2):4288–4312.Crossref, Google Scholar
• Vershynin R (2012) Introduction to the non-asymptotic analysis of random matrices. Eldar Y, Kutyniok G, eds. Compressed Sensing: Theory and Applications (Cambridge University Press, Cambridge, UK), 210–268.Crossref, Google Scholar
• Vinayak RK, Hassibi B (2016) Similarity clustering in the presence of outliers: Exact recovery via convex program. IEEE International Symposium on Information Theory (ISIT), 91–95.Google Scholar
• Von Luxburg U (2007) A tutorial on spectral clustering. Statistics and Computing. 17(4):395–416.Crossref, Google Scholar
• Von Luxburg U, Belkin M, Bousquet O (2008) Consistency of spectral clustering. Ann. Statist. 36(2):555–586.Crossref, Google Scholar
• Wang YX, Xu H (2013) Noisy sparse subspace clustering. Proc. 30th Internat. Conf. on Machine Learning, 28:89–97.Google Scholar
• Wang Y, Wang YX, Singh A (2018) A theoretical analysis of noisy sparse subspace clustering on dimensionality-reduced data. IEEE Trans. Inform. Theory, 65(2):685–706.Crossref, Google Scholar
• Yan B, Sarkar P (2016) On robustness of kernel clustering. Adv. Neural Inform. Processing Systems, 3098–3106.Google Scholar
• Yan B, Sarkar P (2021) Covariate regularized community detection in sparse graphs. J. Amer. Statist. Assoc. 116(534):734–745.Crossref, Google Scholar
• Yan B, Sarkar P, Cheng X (2018) Provable estimation of the number of blocks in block models. Storkey AJ, Pérez-Cruz F, eds. Internat. Conf. on Artificial Intelligence and Statistics, AISTATS 2018, Spain, Proc. Machine Learning Research, 84:1185–1194 (PMLR).Google Scholar
• Yang L, Sun D, Toh KC (2015) SDPNAL+: A majorized semismooth newton-CG augmented lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3):331–366.Crossref, Google Scholar
• Yu SX, Shi J (2003) Multiclass spectral clustering. Proc. 9th IEEE International Conference on Computer Vision, vol. 2, (IEEE, New York), 313.Google Scholar
• Yu Y, Wang T, Samworth RJ (2014) A useful variant of the Davis–Kahan theorem for statisticians. Biometrika 102(2):315–323.Crossref, Google Scholar
• Zhang Y, Rohe K (2018) Understanding regularized spectral clustering via graph conductance. Adv. Neural Inf. Process. Syst. 31:10631–10640.Google Scholar