Scattering Transform Based Image Clustering using Projection onto Orthogonal Complement

Angel Villar-Corrales, Veniamin I. Morgenshtern

Introduction

Image clustering remains a fundamental challenge in computer vision due to high intra-class variance. While Deep Neural Networks (DNNs) have achieved high accuracy, they often function as "black boxes" with significant computational overhead. This paper introduces Projected-Scattering Spectral Clustering (PSSC), a framework that matches the performance of deep learning models while remaining mathematically interpretable and significantly faster.

The PSSC Framework

The PSSC pipeline consists of three distinct mathematical stages designed to linearize class differences and reduce intra-class variability.

The PSSC framework pipeline: Scattering Network, POC, and Spectral Clustering.
  1. Scattering Transform (ScatNet): Instead of learned convolutional layers, PSSC utilizes a predefined hierarchical network of wavelet filters. This transform provides a representation that is invariant to small translations and robust to deformations.
  2. Projection onto Orthogonal Complement (POC): The core innovation of this work. By projecting scattering coefficients onto the orthogonal complement of shared high-variance directions, the method discards non-discriminative features common across classes.
  3. Ultra-Scalable Spectral Clustering (U-SPEC): To ensure the framework scales to large datasets, an efficient version of spectral clustering is employed, utilizing hybrid sampling and approximate k-nearest neighbor searches to overcome $O(N^3)$ complexity.

The Power of Projection

A key discovery in this research is the "Shared Subspace" phenomenon: in the scattering domain, different classes often share their primary directions of variance. While standard dimensionality reduction techniques like PCA typically retain these top eigenvectors, POC does the opposite. By removing the top two eigenvectors—which represent shared, non-discriminative information—the framework drastically enhances cluster separability.

Visualization of POC's effect on a synthetic dataset compared to standard k-Means.

As shown in the synthetic visualization, standard k-Means fails to correctly partition overlapping distributions. However, applying POC before clustering allows for a much cleaner separation by focusing on the unique variances of each group.

Experimental Evaluation

The authors evaluated PSSC on standard benchmarks including MNIST, USPS, and Fashion-MNIST.

  • Accuracy: On the MNIST dataset, PSSC achieved 96.5% accuracy, matching state-of-the-art deep clustering models like DEPICT and JULE.
  • Efficiency: PSSC demonstrated massive speed gains. While deep models like JULE required approximately 12,500 seconds to cluster MNIST, PSSC completed the task in just 182 seconds—a nearly 70x speedup.
  • Ablation Study: The necessity of the POC step was confirmed; removing it resulted in a drop in MNIST accuracy from 96.5% to 94.2%.

Conclusion

PSSC offers a compelling alternative to deep learning for image clustering, providing a "provably stable" pipeline that avoids common issues like vanishing gradients or stochastic initialization. While currently optimized for centered images like digits and apparel, future work will explore adapting the scattering transform and projection logic for more complex natural scenes and high-resolution datasets.

Summary updated

Abstract

In the last few years, large improvements in image clustering have been driven by the recent advances in deep learning. However, due to the architectural complexity of deep neural networks, there is no mathematical theory that explains the success of deep clustering techniques. In this work we introduce Projected-Scattering Spectral Clustering (PSSC), a state-of-the-art, stable, and fast algorithm for image clustering, which is also mathematically interpretable. PSSC includes a novel method to exploit the geometric structure of the scattering transform of small images. This method is inspired by the observation that, in the scattering transform domain, the subspaces formed by the eigenvectors corresponding to the few largest eigenvalues of the data matrices of individual classes are nearly shared among different classes. Therefore, projecting out those shared subspaces reduces the intra-class variability, substantially increasing the clustering performance. We call this method 'Projection onto Orthogonal Complement' (POC). Our experiments demonstrate that PSSC obtains the best results among all shallow clustering algorithms. Moreover, it achieves comparable clustering performance to that of recent state-of-the-art clustering techniques, while reducing the execution time by more than one order of magnitude.
BibTeX
@inproceedings{villarcorrales2020scattering,
  author = {Angel Villar-Corrales and Veniamin I. Morgenshtern},
  title = {{Scattering Transform Based Image Clustering using Projection onto Orthogonal Complement}},
  booktitle = {ICDAR@ICMR},
  year = {2020},
  doi = {10.1145/3463944.3469098},
}
Figure