Consensus-aware sparse subspace clustering via coreset selection

Subspace clustering aims to recover low-dimensional subspaces from high-dimensional data and assign each data point to its corresponding subspace. State-of-the-art subspace clustering methods rely on self-expressive models to represent each data point as a linear combination of other data points. However, these methods typically suffer from scalability challenges when dealing with large-scale datasets. In particular, the limited capacity to capture similarities among data points within the same subspace leads to poor connectivity of the affinity matrix, often resulting in over-segmentation. In this paper, we propose a scalable self-expressive model based on consensus learning with selectively sampled subsets to address the connectivity issue. Our core insight is that an ideal alignment between global and local solutions across multiple small subsets plays a key role in promoting dense connections in the affinity matrix for large-scale datasets. To this end, our model is designed to flexibly fuse sparse local solutions obtained from small subsets in a consensus-aware manner to derive a global solution that captures richer pairwise relationships within each subspace. Moreover, we introduce a selective subsampling strategy to generate subsets that effectively approximate the spatial support of the original dataset. This contributes to the reliability of solved local solutions, which further enables robust clustering even in imbalanced datasets. Extensive experiments on synthetic and five real-world datasets show that our method achieves state-of-the-art performance, in terms of clustering accuracy and connectivity.