Sparse K K -spatial-median clustering for high-dimensional data
Ping Zhao, Dan Zhuang, Long Feng · 2026
Read Sparse K K -spatial-median clustering for high-dimensional data by Ping Zhao, Dan Zhuang, Long Feng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00598.txt.
Introduction
Ping Zhao, Dan Zhuang, and Long Feng build a clustering method for high-dimensional data that is heavy-tailed and full of irrelevant variables. Classic K-means chases means, which outliers drag around, and it weighs every dimension equally, signal or not. Their framework swaps the mean updates for spatial medians, a robust center that resists extreme points, inside the usual assign-and-update loop.
For the assignment step, users can keep a simple Euclidean rule or use a robust Mahalanobis-type distance built from the spatial sign covariance, which accounts for differing scales and dependence among features. A hard feature-exclusion step then drops dimensions that barely separate the centers, with its threshold chosen automatically by a permutation-based gap criterion. In simulations on correlated Gaussian and heavy-tailed data, the method matched or beat K-means and sparse K-means on accuracy, with better stability across runs.
Catalog record
| CREATOR | Ping Zhao, Dan Zhuang, Long Feng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00598
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse K K -spatial-median clustering for high-dimensional data Ping Zhao, Dan Zhuang, Long Feng Abstract We propose a robust clustering framework for high-dimensional data with heavy tails and a large fraction of irrelevant variables. The method replaces the mean updates of Lloyd’s K K -means with spatial medians to enhance robustness. For the assignment step, it admits either a Euclidean rule for computational simplicity or a robust Mahalanobis-type metric constructed from the spatial sign covariance matrix to account for heterogeneous scales and feature dependence. To handle the p ≫ n p\gg n regime, we further introduce a simple hard feature-exclusion mechanism that removes weakly separating dimensions based on across-center dispersion, with the exclusion threshold selected automatically via a permutation-based Gap criterion. Simulation studies under correlated Gaussian and multivariate t t models demonstrate that the proposed approach provides competitive clustering accuracy and improved stability relative to K K -means and sparse K K -means baselines. Keywords: Robust clustering, spatial median, Euclidean distance, sparse clustering, feature exclusion, high-dimensional data, Gap statistic. 1 Introduction High-dimensional clustering arises routinely in modern applications, where the number of variables is often comparable to or substantially larger than the sample size, and only a small subset of features may truly carry cluster-discriminating information ( 14 ; 23 ; 6 ) . In such settings, classical clustering methods may deteriorate substantially because irrelevant variables can dominate dissimilarities, while heavy tails, outliers, and contamination can further destabilize mean-based procedures ( 1 ; 7 ) . These challenges have motivated sparse clustering methods that integrate clustering with feature selection or variable screening. However, in many applications, the central challenge is not sparsity alone, but the need to handle irrelevant features and distributional instability within a unified framework. Among partition-based methods, K -means ( 10 ) remains one of the most widely used clustering tools because of its simplicity and computational efficiency ( 20 ; 13 ) . Nevertheless, it performs poorly when high-dimensional data contain many irrelevant features or substantial contamination ( 25 ; 32 ) . This weakness is not merely computational: when dissimilarities are aggregated over many coordinates, even weak noise can overwhelm the true low-dimensional separation and obscure the underlying cluster structure. To address this difficulty, sparse clustering methods incorporate feature selection or variable screening directly into the clustering procedure. Existing approaches include model-based penalization ( 11 ; 22 ; 2 ) , subspace and feature-subset methods ( 24 ; 8 ; 28 ) , and objective-function-based extensions of classical clustering algorithms ( 31 ; 30 ) . Among these, sparse K -means and its variants are particularly influential, using feature weights together with \ell_{1} -type regularization to suppress irrelevant variables ( 31 ; 26 ; 17 ) . However, these developments remain largely tied to mean-based or weighted K -means-type formulations. A complementary route is to improve robustness by modifying the loss and/or the notion of cluster center. Existing robustifications of K -means, including trimmed and weighted variants ( 5 ; 19 ; 18 ; 4 ) , reduce sensitivity to outliers and contamination, but they remain closely connected to mean-based or Euclidean-type prototypes. One classical alternative is K -median, which replaces the squared \ell_{2} loss with an \ell_{1} -type distance and uses coordinatewise medians as prototypes ( 3 ; 16 ) . This improves resistance to heavy-tailed coordinates and gross contamination, but it remains inherently axis-aligned: coordinatewise medians and the \ell_{1} geometry may be sensitive to rotations and correlation structure, which is undesirable when clusters are approximately elliptically distributed. To better respect multivariate geometry while retaining robustness, a natural alternative is the spatial median (geometric median), defined as the minimizer of the sum of Euclidean norms. Compared with coordinatewise medians, the spatial median is rotation equivariant, compatible with multivariate elliptical structure, and computationally tractable via Weiszfeld-type iterations ( 27 ; 29 ) . More broadly, spatial-sign and spatial-rank methods provide a principled robust framework under elliptical models, in which the spatial median plays the role of a multivariate robust center ( 21 ; 9 ) . While robust centers address distributional fragility, they do not by themselves resolve the central difficulty of high-dimensional clustering, since most variables may still be irrelevant. In particular, continuous shrinkage methods can attenuate noisy variables, but may leave many weak coordinates with small nonzero influence. For high-dimensional clustering, it is often more desirable to obtain an explicit retained/excluded feature set, both for interpretability and for sharper separation between signal and noise. This motivates a hard-thresholding approach that performs exact feature exclusion rather than continuous weighting. In this paper, we propose Sparse K -spatial-median clustering , a partition-based clustering framework for high-dimensional data with heavy tails, approximate elliptical geometry, and a large proportion of irrelevant variables. The proposed method combines spatial-median-based cluster centers with an explicit hard-thresholding feature exclusion rule within a single iterative procedure. Specifically, cluster centers are updated as spatial medians, while a simple center-based separation score is computed for each coordinate at every iteration, and variables with scores below a threshold are excluded from the assignment step. In contrast to \ell_{1} -based sparse clustering, this design yields exact feature inclusion and exclusion through a transparent screening rule rather than continuous shrinkage. In this sense, the proposed method is closer to an \ell_{0} -type sparse clustering mechanism, while remaining computationally simple in iterative implementation. A key practical issue is the choice of the sparsity threshold that governs feature exclusion. To address this, we adopt a permutation-based tuning strategy in the spirit of the Gap statistic, following its common use in sparse clustering ( 31 ; 1 ) and building on the original framework of 26 . Specifically, we evaluate a between-cluster separation functional over candidate thresholds and compare it with a reference distribution generated by column-wise permutations, which preserve marginal feature distributions while destroying multivariate cluster structure. The selected threshold maximizes the resulting Gap criterion, thereby providing a data-driven rule for determining which coordinates are treated as noise. The main contributions of this paper are as follows: • We develop a robust partition-based clustering framework based on spatial medians, which is better suited to heavy-tailed data and approximately elliptical cluster geometry than mean-based or coordinatewise-median alternatives. • We introduce an explicit hard-thresholding feature exclusion mechanism, which yields exact and interpretable retained/excluded variable sets rather than continuous weight shrinkage. • We propose a permutation-based Gap procedure for automatic threshold selection, providing a data-driven rule for determining which coordinates are treated as noise. • We establish consistency properties of the proposed method and demonstrate its empirical effectiveness through simulation studies and real-data analyses. The remainder of the paper is organized as follows. Section 2 introduces the proposed Sparse K -spatial-median clustering framework. Section 3 establishes its corresponding theoretical properties. Section 4 reports simulation results. Section 5 demonstrates the practical performance of the proposed method through analyses of the mice protein dataset and several benchmark datasets. Section 6 concludes the paper. Appendix A contains the proofs of the consistency results. Notation. For a positive integer q , write [q]=\{1,\ldots,q\} . Vectors are denoted by bold italic symbols, for example \bm{x} , \bm{m} , and \bm{\mu} , whereas matrices are denoted by bold upright symbols, for example \mathbf{X} , \mathbf{A} , and \mathbf{\Sigma}