# Enhancing Kernel Power K-means: Scalable and Robust Clustering with Random Fourier Features and Possibilistic Method

arXiv: https://arxiv.org/abs/2511.10392 · HTML: https://mlsanity.com/paper/2511.10392/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 47 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)

## Abstract (arXiv)

Kernel power k-means (KPKM) leverages a family of means to mitigate local minima issues in kernel k-means. However, KPKM faces two key limitations: (1) the computational burden of the full kernel matrix restricts its use on extensive data, and (2) the lack of authentic centroid-sample assignment learning reduces its noise robustness. To overcome these challenges, we propose RFF-KPKM, introducing the first approximation theory for applying random Fourier features (RFF) to KPKM. RFF-KPKM employs RFF to generate efficient, low-dimensional feature maps, bypassing the need for the whole kernel matrix. Crucially, we are the first to establish strong theoretical guarantees for this combination: (1) an excess risk bound of O(√k3/n), (2) strong consistency with membership values, and (3) a (1+varepsilon) relative error bound achievable using the RFF of dimension poly(varepsilon-1log k). Furthermore, to improve robustness and the ability to learn multiple kernels, we propose IP-RFF-MKPKM, an improved possibilistic RFF-based multiple kernel power k-means. IP-RFF-MKPKM ensures the scalability of MKPKM via RFF and refines cluster assignments by combining the merits of the possibilistic membership and fuzzy membership. Experiments on large-scale datasets demonstrate the superior efficiency and clustering accuracy of the proposed methods compared to the state-of-the-art alternatives.