Sparse Subspace Clustering by Learning Approximation _0 Codes

AAAI 2017

TL;DR

This paper introduces SSC-LOMP, a novel sparse subspace clustering method that uses a learned neural network (SHNN) to efficiently approximate the computationally expensive $\ell_0$ sparse codes. This approach significantly speeds up inference while maintaining or improving clustering accuracy, achieving state-of-the-art results on the MNIST dataset.

What Problem Does This Paper Address?

Subspace clustering aims to group high-dimensional data points that lie on different linear subspaces. A crucial step in many subspace clustering methods is constructing an "affinity matrix" that captures these subspace relationships. Traditional methods often rely on regularization techniques like $\ell_1$, $\ell_2$, or nuclear norms to achieve this. However, these methods face challenges: $\ell_2$ and nuclear norms require strong assumptions, $\ell_1$ regularization leads to computationally expensive convex optimization problems, and $\ell_0$ regularization, while offering a good trade-off, still requires time-consuming algorithms like Orthogonal Matching Pursuit (OMP) when dealing with a large number of data points. The core problem this paper tackles is the computational bottleneck in obtaining a good affinity matrix for subspace clustering, particularly the slow inference of $\ell_0$ sparse codes.

Methods

The paper proposes SSC-LOMP (Sparse Subspace Clustering by Learned Orthogonal Matching Pursuit). The key innovation is the use of a Single Hidden Neural Network (SHNN), termed Learned OMP (LOMP), to approximate the $\ell_0$ sparse codes.

Here's a breakdown of the method:

  • LOMP Algorithm: This algorithm trains an SHNN to directly output approximate $\ell_0$ sparse codes. It combines an initial OMP step to get initial sparse codes, followed by gradient descent to train the SHNN's weights (W¹ and W²). The SHNN takes a data point as input and outputs its sparse representation.
  • SSC-LOMP: Once the SHNN is trained, the $\ell_0$ sparse codes for all data points can be computed very quickly by feeding them through the trained SHNN. This fast computation of sparse codes allows for rapid construction of the affinity matrix, which is then used for spectral clustering.
  • Activation Functions: The paper explores various activation functions for the SHNN, including linear, ReLU, shrinkage, and Tanh. The shrinkage function is particularly highlighted for its ability to enforce sparsity by zeroing out small coefficients.
  • Theoretical Guarantees: The authors provide theoretical conditions to ensure that the learned representation maintains the subspace-preserving property, even with the approximation introduced by the neural network.

Datasets

The proposed method was evaluated on two standard datasets:

  • MNIST: A dataset of 70,000 handwritten digit images (0-9). Feature vectors of size 3,472 were extracted and reduced to 500 dimensions using PCA. Experiments used subsets of 50, 100, 200, 400, and 600 images per class.
  • Extended YaleB: A dataset of frontal face images from 38 individuals under varying illumination conditions. Images were downsampled to 48x42 pixels. Experiments used subsets of 2, 10, 20, 30, and 38 classes.

Key Insights and Ideas

  • Neural Networks for Sparse Coding Inference: The paper demonstrates that neural networks can effectively learn to approximate computationally expensive sparse coding problems ($\ell_0$ in this case), leading to significant speedups in inference.
  • Bridging OMP and Neural Networks: LOMP successfully bridges the gap between traditional greedy algorithms like OMP and data-driven neural network approaches, leveraging the strengths of both.
  • Trade-off between Approximation and Sparsity: The use of the shrinkage activation function in the SHNN is crucial for enforcing sparsity in the learned codes, allowing the method to maintain subspace-preserving properties even with approximation errors.
  • State-of-the-Art Performance: The method not only achieves significant speedups but also matches or surpasses existing state-of-the-art subspace clustering methods in terms of clustering accuracy and normalized mutual information.

Key Results

  • Clustering Accuracy: SSC-LOMP achieved a state-of-the-art clustering accuracy of 94.32% on the MNIST dataset. It also showed significant improvements over baseline methods on both MNIST and Extended YaleB datasets. For instance, on MNIST, it achieved an average of 3.03% improvement in ACC and 2.59% in NMI compared to SSC-OMP.
  • Inference Speed: SSC-LOMP offers a substantial speedup in test inference time compared to SSC-OMP and other methods like SSC-ISTA and LRR. The paper states that SSC-LOMP is "always faster than SSC-OMP in test inference time."
  • Subspace Preserving Property: Experiments showed that SSC-LOMP yields higher SPRP (Subspace Preserving Representation Percentage) and lower SPRE (Subspace Preserving Representation Error) than SSC-OMP, indicating a better subspace-preserving representation.

Limitations and Future Work

  • Non-convexity: The optimization problem for training the SHNN is non-convex, meaning the learned solution might be a local optimum. While the paper shows good practical performance, theoretical convergence guarantees for the entire LOMP algorithm are challenging.
  • Parameter Tuning: Like most neural network-based methods, SSC-LOMP requires tuning of parameters such as the shrinkage threshold ($\theta$), the number of hidden units ($m$), and the learning rate ($\epsilon$). The paper suggests these are typical neural network parameters and are relatively easy to choose.
  • Future Work: The paper implicitly suggests that further exploration of different neural network architectures and activation functions could lead to even better performance. Extending the theoretical analysis to provide stronger convergence guarantees would also be valuable.

Summary updated

BibTeX
@inproceedings{2017sparse,
  title = {{Sparse Subspace Clustering by Learning Approximation \_0 Codes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
}
Figure