Efficient Incomplete Multiple Kernel Clustering With Approximation Theoretical Guarantees

Multiple kernel clustering (MKC) algorithms achieve superior clustering performance but struggle with datasets that contain missing features. Consequently, researchers have developed incomplete multiple kernel clustering (IMKC) to address this challenge. However, existing IMKC algorithms generally suffer from low computational efficiency and lack theoretical approximation guarantees. This low efficiency makes IMKC algorithms incapable of handling large-scale datasets, limiting their applicability. The lack of theoretical approximation guarantees, in turn, leads to clustering results that are poorly interpretable and unreliable. To address these limitations, this paper proposes the Efficient Incomplete Multiple Kernel Clustering (EIMKC) algorithm, a scalable approximation framework that enables standard MKC solvers to handle incomplete kernels. Specifically, EIMKC first applies an eigen-approximation to incomplete kernels to generate a set of reduced-size base kernel matrices, which are then used to estimate kernel weights through a standard MKC algorithm. It then performs kernel imputation and consensus embedding learning in a unified alignment objective. We instantiate EIMKC with two representative MKC solvers, MKKM-MR and SMKKM, and validate it both theoretically and experimentally. Theoretically, we establish high-probability upper bounds on the learned kernel weights and the consensus embedding projector with respect to the complete-kernel solutions. Extensive experiments on multiple benchmark datasets demonstrate that the proposed EIMKC clearly outperforms current IMKC algorithms in both efficiency and clustering performance.