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:
- 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.
- 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).
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