Abstract
Traditional subspace clustering methods struggle with scalability due to the memory-intensive construction of $N \times N$ affinity matrices. This paper presents Scalable Deep $k$-Subspace Clustering (k-SCN), a framework that integrates convolutional auto-encoders with a $k$-subspace clustering module. By optimizing subspaces directly on Grassmann manifolds and bypassing affinity matrices, k-SCN achieves state-of-the-art performance on large-scale datasets like MNIST and Fashion-MNIST with significantly reduced computational costs.
Introduction
Subspace Clustering (SC) operates on the premise that data points from the same category lie in low-dimensional linear subspaces. While effective for applications like facial recognition or motion segmentation, traditional SC methods face two major hurdles: scalability and non-linearity. Most state-of-the-art methods rely on constructing an $N \times N$ affinity matrix and performing spectral clustering. For a dataset like MNIST ($N=70,000$), this requires roughly 37GB of memory, making it prohibitive for standard hardware. Furthermore, real-world data is rarely perfectly linear. The authors propose k-SCN to address these issues through an end-to-end trainable, scalable architecture.
Methodology
Architecture
The k-SCN framework utilizes a Convolutional Auto-Encoder (CAE) integrated with a $k$-subspace clustering module. The encoder maps input images into a latent embedding space, while the decoder reconstructs the images to ensure the embeddings preserve essential features. Unlike $k$-means, which clusters points around centroids, the $k$-subspace module clusters points around $k$ different low-dimensional subspaces.
Loss Function
The network is trained using a joint loss function: $$\mathcal{L} = \mathcal{L}_{reconstruction} + \lambda \mathcal{L}_{subspace\_clustering}$$ This dual objective forces the encoder to find a latent representation that is both representative of the original data and "subspace-friendly."
Optimization on Grassmann Manifolds
A key innovation of this work is the optimization of subspaces ($\mathbf{S}_i$). For large datasets, the authors treat subspaces as points on a Grassmann manifold. They employ Riemannian gradient descent to update these subspaces, ensuring they remain orthogonal and properly structured without the computational burden of a full Singular Value Decomposition (SVD) every iteration.
Experiments and Results
The authors evaluated k-SCN on the full 70,000-sample versions of MNIST and Fashion-MNIST, a significant departure from previous works that often used small subsets.
- Accuracy: k-SCN achieved 87.14% accuracy on MNIST, outperforming deep clustering baselines like DEC (84.3%) and DCN (83.31%). On the more challenging Fashion-MNIST, it reached 63.78% accuracy, a notable improvement over DCN's 56.14%.
- Efficiency: The entire pipeline (pre-training and fine-tuning) took less than 8 minutes for 10,000 samples. In contrast, traditional algorithms often require over 40 minutes just for the clustering phase on pre-extracted features.
- Scalability: By using $k$-subspace logic rather than spectral clustering, the memory requirement drops from $O(N^2)$ to $O(N)$, enabling the processing of "big data" on standard hardware.
Conclusion
k-SCN demonstrates that subspace priors are often more accurate reflections of underlying data geometry than centroid priors in high-dimensional spaces. By leveraging manifold optimization, the clustering process becomes a seamless part of the neural network's training loop. While the method is sensitive to initialization and requires hyperparameter tuning for the subspace dimension ($p$), it represents a significant step forward in making subspace clustering viable for large-scale, non-linear datasets.
Summary updated