On the Consistency and Large-Scale Extension of Multiple Kernel Clustering

Existing multiple kernel clustering (MKC) algorithms have two ubiquitous problems. From the theoretical perspective, most MKC algorithms lack sufficient theoretical analysis, especially the consistency of learned parameters, such as the kernel weights. From the practical perspective, the high complexity makes MKC unable to handle large-scale datasets. This paper tries to address the above two issues. We first make a consistency analysis of an influential MKC method named Simple Multiple Kernel $k$ -Means (SimpleMKKM). Specifically, suppose that $\hat{\boldsymbol{\gamma }}_{n}$ are the kernel weights learned by SimpleMKKM from the training samples. We also define the expected version of SimpleMKKM and denote its solution as $\boldsymbol{\gamma }^*$ . We establish an upper bound of $\Vert \hat{\boldsymbol{\gamma }}_{n}-\boldsymbol{\gamma }^*\Vert _\infty$ in the order of $\widetilde{\mathcal {O}}(1/\sqrt{n})$ , where $n$ is the sample number. Based on this result, we also derive its excess clustering risk calculated by a standard clustering loss function. For the large-scale extension, we replace the eigen decomposition of SimpleMKKM with singular value decomposition (SVD). Consequently, the complexity can be decreased to $\mathcal {O}(n)$ such that SimpleMKKM can be implemented on large-scale datasets. We then deduce several theoretical results to verify the approximation ability of the proposed SVD-based method. The results of comprehensive experiments demonstrate the superiority of the proposed method. The code is publicly available at https://github.com/weixuan-liang/SVD-based-SimpleMKKM .