New theory proves k-means works for missing data with √n rates

Classical k-means clustering fails on incomplete data, and existing missing-data adaptations lack asymptotic theoretical guarantees. Xin Guan's paper fills this gap by rigorously proving the statistical properties of k-means under general missing mechanisms, with deeper results for the Missing Completely at Random (MCAR) case. The work establishes a √n-excess risk bound, consistency of estimated cluster centers, and—under MCAR—a √n-convergence rate and asymptotic normality. These results provide the first theoretical foundation for applying k-means to incomplete datasets with confidence.

The analysis reveals a critical condition: to achieve √n-rate convergence to the true cluster centers, all k true centers must be distinct in every dimension. This poses significant challenges in high-dimensional regimes, where dimensions may be redundant or not all discriminative. The paper also gives a sufficient condition involving missing probability and cluster separation. Numerical simulations on synthetic incomplete datasets support the theory, confirming that the proposed missing-data k-means can match the performance of fully observed clustering under the right conditions.