K-Means

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, up 25% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 39

All topics

Two-Point Local Optimality in $k$ -Means via Boundary-Point Screening
Oct 5, 2026Wenlong Lyu, Xujie Xiao, Yuheng JiaK-Means Optimal Sample Complexity
School of Computer Science and Engineering Southeast University Nanjing, Jiangsu 211189, China
Neither Black nor White: Balancing Semantic and Collaborative Signals with Graph-Informed Semantic IDs (GrIS)
Oct 1, 2026Aleksei Medvedev, Alejandro Ariza-Casabona, Steven Derby +3Sequential Recommendation Semantic Relationships
Huawei Ireland Research Centre Dublin, Ireland
Riemannian Difference-of-Convex Optimization for K-Means Clustering
Sep 28, 2026Meng Xu, Bo Jiang, Hanfu Zhang +2K-Means Nonconvex
AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China +1
Copula Adapted Directed Acyclic Graph for Cluster Representation of Biomedical Data
Sep 14, 2026Heranga K. Rathnasekara, Norou Diawara, Manar D. SamadCausal Discovery Methods Causal Graph
Department of Mathematics and Statistics Old Dominion University, Norfolk, VA 23529, USA · Department of Computer Science North Carolina Agricultural and Technical State University Greensboro, NC 27411, USA
A Sub-4 Approximation for Fair $k$ -Means
Sep 7, 2026Kangke Cheng, Guanlin Mo, Shihong Song +1K-Means Approximation Algorithms
University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK
CLUES-WEASEL: No additional clues required to choose your time series clustering algorithm
Sep 7, 2026Johann FaouziTime-Series Classification Clustering
Univ Rennes, Ensai, CNRS, CREST - UMR 9194, F-35000 Rennes, France.
DK-GBMKKM: Dynamic Kernel-Space Granular-Ball Multiple Kernel $k$ -Means Clustering
Sep 1, 2026Xiaoyu Lian, Yuchao Zhang, Shuyin Xia +2Granular-Ball Computing K-Means
Chongqing University of Posts and Telecommunications · Chongqing Open University
PRQ-KMeans: Projection Residual Quantization for Semantic ID Tokenization
Aug 25, 2026Yunxiao Luo, Siyuan Wang, Ben Chen +2K-Means Projection
1Kuaishou Technology
Multi-perspective Imbalance-Conscious 6G Beamforming Optimization and Performance
Aug 13, 2026Chukwunonso Henry Nwokoye, Blessing Oluchi Iloka, Chikwue V. Umeugoji +2Beamforming Unsupervised
Liberal Arts & Professional Studies York University, Toronto, Canada · Physics, Engineering & Computer Science University of Hertfordshire England, United Kingdom · IT Services, Joint Admissions & Matn. Board Lagos, Nigeria +1
Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms
Aug 11, 2026Florian Beier, Stephan EcksteinGromov--Wasserstein K-Means
Department of Mathematics, University of Tübingen, Germany
Randomizing the Number of Centers in k-means++
Jul 28, 2026Vaclav RozhonK-Means Approximation Algorithms
Lloyd's $K$ -Means Clustering Algorithm Is Frank-Wolfe in Disguise
Jul 28, 2026Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-JulienK-Means Convex Optimization
Department of Mathematics & Statistics and School of Data Science Old Dominion University Norfolk, VA 23529, USA · Information Systems & Analytics Department Miami University Oxford, OH 45056, USA · Canada CIFAR AI Chair Department of Computer Science and Operations Research & Mila Université de Montréal Montréal (QC) Canada
The K-SCAN Clustering Algorithm
Jul 27, 2026Filip Kosiorowski, Grzegorz SrokaK-Means Clustering
The Faculty of Mathematics and Applied Physics, Rzeszów University of Technology, Powstańców Warszawy 12, 35-959 Rzeszów, Poland · Department of Analysis Nonlinear, Rzeszów University of Technology, Powstańców Warszawy 12, 35-959 Rzeszów, Poland
K-Survival Means
Jul 27, 2026Abdallah AlabdallahSurvival Predictions Clustering
Center for Applied Intelligent Systems Research (CAISR), Halmstad, Sweden
Data-Native Global Optimization for Big Data K-means Clustering
Jul 17, 2026Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva +1K-Means Clustering
AI Research Lab, Satbayev University, Almaty, 050000, Kazakhstan · Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan
An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence
Jul 15, 2026Damien Lesens, Jérémy E. Cohen, Bora UçarNonnegative Matrix Factorization Kullback-Leibler Divergence
ENS de Lyon · Univ. Lyon, INSA-Lyon, UCBL, UJM, CNRS, Inserm, CREATIS UMR 5220, U1294, F-69621, Lyon, France. · CNRS and LIP (UMR5668, Université de Lyon - ENS de Lyon - UCBL - CNRS - Inria), 46 allée d'Italie, Lyon, France.
An interpretable Good--Turing restart criterion for k-means++
Jul 9, 2026Renato Cordeiro de AmorimK-Means Top-K
School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK.
Sensitivity Sampling with Predictions for k-Means Clustering
Jul 6, 2026Cristian Boldrin, Fabio VandinK-Means Clustering
University of Padova, Padova, Italy
A Clustering-Based Framework for Identifying Suspicious Trading Patterns in Capital Market
Jul 5, 2026Asif Zaman, Romona Magdalene Sarkar, Sabiha Khair Ohi +1Fraud Detection Clustering
Department of Computer Science & Engineering American International University-Bangladesh Dhaka,Bangladesh
Statistical Properties of $k$ -means Clustering for Data Missing Completely at Random
Jul 2, 2026Xin GuanK-Means Clustering
Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan
MNAR- $k$ -means: A $k$ -means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability
Jun 30, 2026Xin GuanK-Means Imputation
Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan
Active Learning with Low-Rank Structure for Data Selection
Jun 14, 2026Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni +3Geometry-Aware Uncertainty Coresets Low-Rank Structure
Google Research. · University of California, Berkeley. · Institute of Science and Technology Austria (ISTA). +2
Towards Data-free and Training-free Compression for Speech Foundation Models Using Parameter Clustering
Jun 10, 2026Haoning Xu, Zhaoqing Li, Huimeng Wang +4Task-Aware Compression Unstructured Pruning
The Chinese University of Hong Kong, Hong Kong SAR, China · National Research Council Canada, Canada
Orthogonality and Dimensionality in Airline Cluster Analysis using PCA and Kernel PCA
Jun 6, 2026Andreas SchlapbachPrincipal Component Analysis K-Means
Swiss Federal Railways (SBB), Switzerland
UniFair: A unified fair clustering approach based on separation and compactness
Jun 3, 2026Antonia Karra, Vasiliki Papanikou, Georgios Vardakas +2Clustering Algorithmic Fairness
University of Ioannina, Greece · Archimedes/Athena Research Center, Greece
PE-means: Improved Differentially Private $k$ -means Clustering through Private Evolution
May 29, 2026Thomas Humphries, Zinan Lin, Sergey YekhaninK-Means Clustering
University of Waterloo · Microsoft Research
No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval
May 28, 2026Lixuan Guo, Yifei Wang, Tiansheng Wen +3Retrieval Layer Bottlenecks
Stony Brook University · Xidian University · Amazon AGI SF Lab +4
Clustering as Reasoning: A $k$ -Means Interpretation of Chain-of-Thought Graph Learning
May 24, 2026Xuanting Xie, Zhaochen Guo, Bingheng Li +4Graph Representation Learning Chain-of-Thought Reasoning
University of Electronic Science and Technology of China, 611731, Chengdu, China · Singapore Management University, 188065, Singapore · Michigan State University, East Lansing, 48824, MI, USA +1
Simple KNN-Based Outlier Detection Achieves Robust Clustering
May 8, 2026Tianle Jiang, Yufa ZhouK-Means Clustering
Duke University
Drawing Lines in Psychological Space: What K-means Clustering Reveals in Simulated and Real Psychometric Data
May 7, 2026Pedro Henrique Ramos Pinto, Maria Jullyanna Ferreira Marques, Luiz Carlos Serramo LopezK-Means Clustering
Postgraduate Program in Cognitive and Behavioral Neuroscience (PPGNeC) - Federal University of Paraíba (UFPB) - João Pessoa, PB - Brazil · Center for Health Sciences (CCS) - Federal University of Paraíba (UFPB) - João Pessoa, PB - Brazil
Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing
Apr 30, 2026Silvio Martinico, Franco Maria Nardini, Cosimo Rulli +1Clustering K-Means
University of Pisa & ISTI–CNR · Pisa, Italy · ISTI–CNR +1
An effective variant of the Hartigan $k$ -means algorithm
Apr 23, 2026François Clément, Stefan SteinerbergerK-Means Approximation Algorithms
Coexisting Tempo Traditions in Beethoven's Piano and Cello Sonatas: A K-means Clustering Analysis of Recorded Performances, 1930-2012
Apr 17, 2026Ignasi SoleBeethoven K-Means
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
Apr 17, 2026Nicole Funk, Annika Hennes, Johanna Hillebrand +1K-Means Approximation Algorithms
Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany
BalLOT: Balanced $k$ -means clustering with optimal transport
Dec 5, 2025Wenyan Luo, Dustin G. MixonK-Means Optimal Transport Approach
Department of Mathematics, The Ohio State University, Columbus, Ohio, USA · Translational Data Analytics Institute, The Ohio State University, Columbus, Ohio, USA
Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters
Aug 11, 2025Richard J. Fawley, Renato Cordeiro de AmorimK-Means Shapley Value
School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.
Scalable unsupervised feature selection via weight stability
Jun 6, 2025Xudong Zhang, Renato Cordeiro de AmorimFeature Selection K-Means
School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.
Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means
Jul 15, 2024Max Dupré la Tour, David SaulpicK-Means Approximation Algorithms
Anisotropic View Distance Metric for High-Dimensional Data: Theory, Geometry, and Fast Computation
Jun 10, 2022Yiqun Zhang, Hou-biao LiK-Means Distance
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China

Oct 5, 2026, cs.LGJ/K move · Enter open · S save

Two-Point Local Optimality in $k$ -Means via Boundary-Point Screening

Wenlong Lyu, Xujie Xiao, Yuheng Jia

School of Computer Science and Engineering Southeast University Nanjing, Jiangsu 211189, China

K-Means Optimal Sample Complexity Kernel Method

Open paper AskPDF arXiv

Lloyd's algorithm and the discrete local (D-local) optimization method (Li et al., 2025) for

k

-means provide only weak local-optimality guarantees, and their solution quality remains sensitive to initialization. In this paper, we introduce

r

-point local optimality, under which no reassignment of at most

r

samples decreases the objective function, and focus on

r=2

. The main computational obstacle is the

\mathcal{O}(n^2(k^2+d))

cost of exhaustive two-point certification for

n

samples in

d

dimensions and

k

clusters. To address this challenge, we prove that (i) every improving two-point move of a D-local optimum must involve a cluster shared by both reassignments, and (ii) only certificate-defined boundary points can participate in an improving pair. Exploiting this structure, we propose Boundary-Point-Screened Two-Point Local Search (BPS-2PLS), which terminates at a two-point local optimum. For fixed

k,d

and nonvanishing cluster occupancy, the number

m

of retained candidates satisfies

m=\mathcal{O}_{\mathbb{P}}(\log n)

under i.i.d. sampling from a bounded-support distribution with bounded density or from a Gaussian mixture. Across twelve benchmarks, BPS-2PLS attains the lowest available mean WCSS on ten. In a subsampling study, screening retains 0.10% to 2.81% of samples on average at the largest tested sizes. The code is available at https://github.com/lwl-learning/BPS-2PLS.

Momentum

Related topics

Latest papers 39