Clustering, a fundamental activity in unsupervised learning, is notoriously difficult when the feature space is high-dimensional. Fortunately, in many realistic scenarios, only a handful of features are relevant in distinguishing clusters. This has motivated the development of sparse clustering techniques that typically rely on k-means within outer algorithms of high computational complexity. Current techniques also require careful tuning of shrinkage parameters, further limiting their scalability. In this paper, we propose a novel framework for sparse k-means clustering that is intuitive, simple to implement, and competitive with state-of-the-art algorithms. We show that our algorithm enjoys consistency and convergence guarantees. Our core method readily generalizes to several task-specific algorithms such as clustering on subsets of attributes and in partially observed data settings.

Summary and Contributions: This paper focuses on the problem of clustering in high dimension. K-means clustering is an extremely popular tool (especially in biomedical applications). However, as underlined by the authors, its performance is severely hindered in high-dimensional space --- leaving the data analyst no chance but to (a) apply some dimensionality reduction technique before performing the clustering or (b) selecting the features that are the most informative for the clustering and apply k-means on a subset of the features. This paper proposes a version of the later approach, choosing a sparse and interpretable subset of features. The setting is the following.

The reviewers appreciate the algorithmic contributions of this paper and believe it will be on interest to the community.

Clustering, a fundamental activity in unsupervised learning, is notoriously difficult when the feature space is high-dimensional. Fortunately, in many realistic scenarios, only a handful of features are relevant in distinguishing clusters. This has motivated the development of sparse clustering techniques that typically rely on k-means within outer algorithms of high computational complexity. Current techniques also require careful tuning of shrinkage parameters, further limiting their scalability. In this paper, we propose a novel framework for sparse k-means clustering that is intuitive, simple to implement, and competitive with state-of-the-art algorithms.