Scalable Deep k-Subspace Clustering

Tong Zhang, Pan Ji, Mehrtash Harandi, Richard I. Hartley, Ian D. Reid

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.

The k-SCN architecture featuring an encoder, decoder, and a k-subspace clustering module that operates on latent embeddings.

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.

Illustration of Riemannian gradient descent on a Grassmann manifold M, showing the update from point p toward w via the tangent space.

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

BibTeX
@inproceedings{zhang2018scalable,
  author = {Tong Zhang and Pan Ji and Mehrtash Harandi and Richard I. Hartley and Ian D. Reid},
  title = {{Scalable Deep k-Subspace Clustering}},
  booktitle = {ACCV},
  year = {2018},
  url = {https://openreview.net/forum?id=aHg8HhsADe9},
}
Figure