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

• URL: http://arxiv.org/abs/2511.10392v1
• Date: Fri, 14 Nov 2025 01:48:51 GMT
• Title: Enhancing Kernel Power K-means: Scalable and Robust Clustering with Random Fourier Features and Possibilistic Method
• Abstract summary: Kernel power $k$-means (KPKM) leverages a family of means to mitigate local minima issues in kernel $k$-means.<n>RFF-KPKM employs RFF to generate efficient, low-dimensional feature maps.<n>IP-RFF-MKPKM ensures the scalability of MKPKM via RFF and refines cluster assignments.
• Score: 37.202008286849875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mathcal{O}(\sqrt{k^3/n})$, (2) strong consistency with membership values, and (3) a $(1+\varepsilon)$ relative error bound achievable using the RFF of dimension $\mathrm{poly}(\varepsilon^{-1}\log 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.

Related papers

• Fourier Feature Methods for Nonlinear Causal Discovery: FFML Scoring, TRFF Scoring, and FFCI Testing in Mixed Data [1.3085880254118603]
  We present three complementary RFF-based methods forming a practical toolkit for causal discovery.<n>The FFML score approximates the exact GP marginal likelihood by replacing the $n x n$ kernel Gram matrix with a finite-dimensional feature representation.<n>The TRFF score offers robustness to heavy-tailed noise and faster runtime than FFML.
  arXiv  Detail & Related papers  (2026-05-07T06:34:19Z)
• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  We study high-probability (HP) convergence guarantees in decentralized optimization.<n>Our results establish the same conditions on the horizon as in achieving comparable times.
  arXiv  Detail & Related papers  (2026-04-30T22:45:21Z)
• Theory of Decentralized Robust Kernel-Based Learning [8.407288892993703]
  We propose a new robust kernel-based learning algorithm within the framework of reproducing kernel Hilbert spaces.<n>We show each local robust estimator generated from the decentralized algorithm can be utilized to approximate the regression function.<n>We provide rigorous selection rules for local sample size and show that, under properly selected step size and scaling parameter $sigma$, the decentralized robust algorithm can achieve optimal learning rates.
  arXiv  Detail & Related papers  (2025-06-05T16:30:05Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning [10.708457894356563]
  We propose two algorithms that achieve near-optimal sample complexity.<n>We prove that both algorithms attain a sample complexity of $widetildeOleft(|mathbfS||mathbfA| t_mathrmmix2varepsilon-2right)$ for estimating the optimal policy.<n>This represents the first finite-sample convergence guarantee for DR average-reward reinforcement learning.
  arXiv  Detail & Related papers  (2025-05-15T06:42:25Z)
• DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning [52.83811558753284]
  Decentralized learning (DFL) discards the central server and establishes a decentralized communication network. Existing DFL methods still suffer from two major challenges: local inconsistency and local overfitting.
  arXiv  Detail & Related papers  (2023-08-16T11:22:36Z)
• Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming [25.210724274471914]
  $K$-means clustering is a widely used machine learning method for identifying patterns in large datasets. In this paper, we consider an NMF-like algorithm that solves nonnegative low-rank $K$-means factorization problem. Our algorithm achieves significantly smaller mis-clustering errors compared to the existing state-the-art while maintaining scalability.
  arXiv  Detail & Related papers  (2023-05-29T00:39:55Z)
• RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features [3.0079490585515347]
  We introduce RFFNet, a scalable method that learns the kernel relevances' on the fly via first-order optimization. We show that our approach has a small memory footprint and run-time, low prediction error, and effectively identifies relevant features. We supply users with an efficient, PyTorch-based library, that adheres to the scikit-learn standard API and code for fully reproducing our results.
  arXiv  Detail & Related papers  (2022-11-11T18:50:34Z)
• Random Fourier Features for Asymmetric Kernels [24.20121243104385]
  We introduce a complex measure with the real and imaginary parts corresponding to four finite positive measures, which expands the application scope of the Bochner theorem. This framework allows for handling classical symmetric, PD kernels via one positive measure; symmetric, non-positive definite kernels via signed measures; and asymmetric kernels via complex measures. Our AsK-RFFs method is empirically validated on several typical large-scale datasets and achieves promising kernel approximation performance.
  arXiv  Detail & Related papers  (2022-09-18T03:39:18Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  We propose a simple yet effective multiple kernel clustering algorithm, termed simple multiple kernel k-means (SimpleMKKM) Our criterion is given by an intractable minimization-maximization problem in the kernel coefficient and clustering partition matrix. We theoretically analyze the performance of SimpleMKKM in terms of its clustering generalization error.
  arXiv  Detail & Related papers  (2020-05-11T10:06:40Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.