An efficient Nyström spectral clustering algorithm using incomplete Cholesky decomposition. (30th December 2021)

• Record Type: Journal Article
• Authors: Jia, Hongjie; Wang, Liangjun; Song, Heping; Mao, Qirong; Ding, Shifei
• Is Part Of: Expert systems with applications. Volume 186(2021)
• Publication Date: 2021-12-30
• Subjects: Spectral clustering -- Nyström approximation -- Incomplete Cholesky decomposition -- Large data set; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115813
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A new matrix factorization strategy is designed for Nyström spectral clustering. Incomplete Cholesky decomposition is introduced to accelerate Nyström approximation. An efficient Nyström spectral clustering algorithm called ICD-NSC is proposed. The effectiveness of ICD-NSC is demonstrated by comprehensive experiments. Abstract: Nyström method can estimate the eigenvectors of a large kernel matrix with the eigenvectors of a small sampled sub-matrix. However, we may encounter two problems when using Nyström method to speed up spectral clustering: one problem is the approximate eigenvectors generated by standard Nyström method are sub-optimal, so they may impair the performance of spectral clustering; another one is the accurate Nyström approximation needs a sufficient number of samples, which will increase the eigen-decomposition cost on the sampled sub-matrix. To solve these problems, this paper proposes an efficient Nyström spectral clustering algorithm using incomplete Cholesky decomposition, in which a new matrix factorization strategy is designed for Nyström spectral clustering to meet the orthogonal constraints, and an efficient eigensolver based on incomplete Cholesky decomposition is developed to accelerate the Nyström approximation. In this way, the obtained approximate orthogonal eigenvectors will help to improve the clustering quality, and the developed eigenvector calculation method will help to reduce the clustering complexity. The experimental results show that the proposed algorithm performs well on many challenging data sets, and it can accomplish more complex clustering tasks with limited computing resources.