Abstract: One of the existing sparse clustering approaches, 𝓁₁-k-means, maximizes the weighted between-cluster sum of squares subject to the 𝓁₁ penalty. In this paper, we propose a sparse clustering method based on an 𝓁_∞ / 𝓁₀ penalty, which we call 𝓁₀-k-means. We design an efficient iterative algorithm for solving it. To compare the theoretical properties of 𝓁₁ and 𝓁₀-k-means, we show that they can be explained explicitly from a thresholding perspective based on different thresholding functions. Moreover, 𝓁₁ and 𝓁₀-k-means are proven to have a screening consistent property under Gaussian mixture models. Experiments on synthetic as well as real data justify the outperforming results of 𝓁₀ with respect to 𝓁₁-k-means.

Key words and phrases: High-dimensional data clustering, screening property, sparse k-means.