Efficient spectral embedding representation approximation for large-scale data clustering

• An efficient approximate spectral embedding representation (ASER) method for large-scale data is presented. • The spectral embedding representations of the anchors are directly used to approximate those of the original samples. • ASER conducts spectral representation approximation in the embedding space instead of approximating the similarity matrix. • Extensive experimental results on several datasets show the effectiveness of ASER. Spectral clustering is a prevalent clustering method in which an affinity matrix is constructed based on all samples (the number is n ), leading to high computational complexity and making it infeasible for dealing with large-scale data directly. In this study, we introduce an Approximate Spectral Embedding Representation method (ASER). By employing an anchor-based strategy, the spectral embedding representation of the selected anchors (the number is m , m ≪ n ) is used to approximate the spectral embedding representation of the original samples. Unlike available methods that approximate the similarity matrix based on an anchor graph, we directly implement the approximation in the spectral embedding space. Moreover, the properties of the formed anchor graph are inherited from the original space to the spectral embedding space. The time complexity of conducting spectral clustering is significantly reduced from O ( n 3 ) to be linear with respect to n , without relying on any acceleration operations for eigenvalue decomposition. Experimental results on toy examples and benchmark datasets with large sizes demonstrate the effectiveness and efficiency of the proposed model.