Nonlinear Kernels in Linear Time: Order-Invariant Large-Scale Multiview Subspace Clustering

Multiview clustering (MVC) has garnered considerable attention owing to its capability to uncover intrinsic data structures by integrating complementary information across multiple views. However, existing large-scale MVC methods still suffer from two notable limitations: 1) tensor-based modeling may implicitly exploit the sequential structure of sorted samples, introducing hidden prior information that conflicts with the unsupervised learning setting, 2) they lack the ability to characterize complex nonlinear structures of multiview data under linear computational complexity. To address these issues, we propose a novel large-scale MVC model for effectively handling nonlinear data, which not only avoids employing the latent priors of sorted samples to enhance order invariance in high-order tensor modeling, but also captures complex nonlinear sample relationships while preserving linear scalability in the number of samples. Then, an efficient ADMM-based alternating optimization algorithm with linear complexity is developed to solve the proposed model. More importantly, the convergence guarantee of the algorithm is theoretically established. Extensive experiments conducted under sorted and shuffled settings on diverse benchmark datasets, including large-scale dataset with more than 100,000 samples, demonstrate that our proposed method achieves superior clustering performance against state-of-the-art methods.