Spare simple MKKM with semi-infinite linear program optimization

Multiple kernel clustering (MKC) optimally combines a group of predefined kernel matrices to improve clustering performance. Although demonstrating promising performance in various applications, most of existing approaches adopt the min-min formulation, which could be sensitive to perturbation with adversarial samples. Moreover, existing MKC algorithms often involve several hypermeters preventing them into further real applications. To address these issues, we propose a parameter-free effective sparse simple multiple kernel k-means algorithm with max-min optimization formulation in this paper. To be specific, we propose to optimize the widely used unsupervised kernel alignment criterion by minimizing the kernel coefficient and maximizing the clustering partition matrix. Unlike traditional min-min formulation, the max-min kernel alignment is robust to adversarial sample perturbation and free of hyper-parameters. An optimization method based on semi-infinite linear program is designed to solve the complicated optimization problem. Extensive experiments on six multiple kernel benchmark data sets demonstrate the effectiveness of the proposed method.