Sparse Subspace Clustering with Entropy-Norm

Liang Bai, Jiye Liang

This paper provides a fascinating theoretical bridge between two heavyweights in the clustering world: Sparse Subspace Clustering (SSC) and Spectral Clustering (SC). By introducing an "entropy-norm" regularizer, the authors demonstrate that these two seemingly distinct approaches are actually two sides of the same coin.

TL;DR

The authors prove that Spectral Clustering using a Gaussian kernel is mathematically equivalent to Sparse Subspace Clustering when an entropy-norm is used for regularization. This insight leads to a new algorithm, SSC+E, which achieves the high accuracy of subspace clustering with the massive computational speedups of analytical kernel methods.

The Problem: Bridging SC and SSC

High-dimensional data (such as images, text, and genomic data) often resides in low-dimensional "subspaces." For example, different photos of the same face under varying lighting conditions tend to lie near a low-dimensional linear subspace. To cluster this data, researchers typically use one of two methods:

  1. Spectral Clustering (SC): Fast and simple, but relies on a pre-defined similarity matrix (often using a Gaussian kernel) that might not capture the underlying subspace structure perfectly.
  2. Sparse Subspace Clustering (SSC): Highly effective at finding subspaces by representing each point as a sparse linear combination of others. However, it is computationally expensive—requiring complex iterative optimization with $O(n^3)$ complexity—and doesn't always produce the symmetric, non-negative similarity matrices that spectral methods require.

While both are state-of-the-art, there was no explicit theoretical connection between them. The authors set out to determine if SC could be viewed as a specific type of SSC.

Methods: The Entropy-Norm Regularizer

The core innovation is the introduction of the Entropy-Norm as a regularization term. In standard SSC, researchers use an $L_1$-norm ($\|Z\|_1$) to force the representation matrix $Z$ to be sparse. The authors instead propose an objective function using the entropy-norm:

$$F = \mathcal{L}(X, XZ) + \lambda \sum_{i=1}^n \sum_{j=1}^n z_{ij} \ln z_{ij}$$

By applying Lagrangian multipliers to minimize this function, they derived an analytical solution for the similarity coefficients ($z_{ij}$). They discovered that when the loss function $\mathcal{L}$ is based on Euclidean distance, the optimal solution for $z_{ij}$ takes the exact form of a Gaussian kernel.

This means that by simply calculating a Gaussian similarity matrix and running a standard spectral solver, you are effectively performing a version of Sparse Subspace Clustering. They call this unified approach SSC+E.

Key Insights

  • The Theoretical Bridge: The Gaussian kernel isn't just a heuristic choice for Spectral Clustering; it is the mathematically optimal sparse representation when using entropy as a regularizer.
  • Analytical vs. Iterative: Standard SSC requires many iterations to converge. SSC+E has an analytical solution, meaning you can compute the similarity matrix directly in one step.
  • Better Properties: Unlike standard SSC, which can produce negative or asymmetric values that require "hacks" to fix (like $W = |Z| + |Z^T|$), SSC+E naturally produces a symmetric, non-negative similarity matrix.

Experimental Results

The authors evaluated their theory and the SSC+E algorithm on 10 diverse benchmark datasets, ranging from Small/UCI datasets (Iris, Wine) to Image/Vision (Yale, COIL) and Speech (Isolet). These datasets range from 150 to over 6,400 objects, providing a robust test of both accuracy and scalability.

The experimental results were striking, particularly regarding speed and clustering performance:

  • Speedup: On the COIL dataset, traditional SSC took approximately 70,766 seconds (nearly 20 hours). In contrast, SSC+E finished in just 0.534 seconds.
  • Scalability: For the Landsat Satellite dataset, standard SSC would take over 60 hours to run, whereas SSC+E handled it in roughly 4.5 seconds.
  • Accuracy: SSC+E outperformed both standard SSC and another modern variant, Clustering with Adaptive Neighbors (CAN), on 9 out of 10 datasets in terms of Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI).
ARI comparison across varying lambda values
NMI comparison across varying lambda values

As shown in the performance plots above, SSC+E maintains a clear and stable advantage over both SSC and CAN across different values of the regularization parameter $\lambda$.

Limitations and Future Work

  • Constraint Assumptions: The theoretical equivalence relies on specific constraints (like the sum of rows/columns equaling a constant). While standard in the field, they may not hold for every specialized clustering task.
  • Kernel Parameter Sensitivity: Like all kernel methods, SSC+E depends on the selection of the $\lambda$ parameter. While the paper provides a range for testing, automated parameter selection remains a challenge.
  • Large-Scale Limits: While $O(n^2)$ for matrix construction is much better than $O(n^3)$, it still poses challenges for "Big Data" (millions of points). Future work could involve combining this entropy-norm approach with Nyström methods or other matrix approximation techniques to reach sub-quadratic complexity.

Summary updated

Abstract

In this paper, we provide an explicit theoretical connection between Sparse subspace clustering (SSC) and spectral clustering (SC) from the perspective of learning a data similarity matrix. We show that spectral clustering with Gaussian kernel can be viewed as sparse subspace clustering with entropy-norm (SSC+E). Compared to SSC, SSC+E can obtain an analytical, symmetrical, nonnegative and nonlinearly-representational similarity matrix. Besides, SSC+E makes use of Gaussian kernel to compute the sparse similarity matrix of objects, which can avoid the complex computation of the sparse optimization program of SSC. Finally, we provide the experimental analysis to compare the efficiency and effectiveness of sparse subspace clustering and spectral clustering on ten benchmark data sets. The theoretical and experimental analysis can well help users for the selection of high-dimensional data clustering algorithms.
BibTeX
@inproceedings{bai2020sparse,
  author = {Liang Bai and Jiye Liang},
  title = {{Sparse Subspace Clustering with Entropy-Norm}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
}
Figure