High-dimensional data—such as a collection of face images or video frames of moving objects—often appears chaotic. However, these datasets usually possess a hidden, simpler structure: they lie on or near a union of several low-dimensional "subspaces." The goal of subspace clustering (or subspace segmentation) is to automatically group these data points into their respective subspaces without knowing the number of subspaces or their dimensions beforehand.
The Self-Expressiveness Property
The core intuition behind modern subspace clustering, popularized by Ehsan Elhamifar and Rene Vidal in Sparse Subspace Clustering: Algorithm, Theory, and Applications, is the self-expressiveness property.
In a linear subspace, any data point can be represented as a linear combination of other points from that same subspace. If we have a data matrix $X$, we can write $X = XC$, where $C$ is a coefficient matrix. Ideally, $C$ should be block-diagonal: a point in Subspace A should only be "explained" by other points in Subspace A, making the coefficients for points in Subspace B zero.
To find this block-diagonal structure, researchers use different regularizations on $C$:
- Sparse Subspace Clustering (SSC): Uses the $\ell^1$-norm to find the fewest possible points to represent each data point.
- Low-Rank Representation (LRR): Introduced by Guangcan Liu and Zhouchen Lin in Robust Subspace Segmentation by Low-Rank Representation, this method looks for a globally low-rank $C$ to capture the holistic structure of the data.
Moving Beyond Independent Subspaces
Early theoretical proofs for these methods relied on a strict assumption: the subspaces must be independent or disjoint. In this idealized world, subspaces are essentially orthogonal, making it easy to tell them apart.
However, real-world data is rarely so polite. As Ruijiang Li and Bin Li point out in Groupwise Constrained Reconstruction for Subspace Clustering, images of different human faces share common structural features like eyes and mouths. This means the subspaces for "Person A" and "Person B" actually overlap or share common directions.
Recent work has shifted toward proving that clustering is possible even when subspaces intersect. Mahdi Soltanolkotabi and Emmanuel J. Candès demonstrated in Robust Subspace Clustering that separation is achievable as long as the "affinity" (measured by principal angles) between subspaces is not too high. Essentially, as long as each subspace has some "innovation"—unique dimensions that the others don't share—spectral methods can still pull them apart Clustering a union of linear subspaces via matrix factorization and innovation search.
Overcoming the Complexity Bottleneck
A major hurdle for these methods is scalability. Building the affinity matrix $C$ typically requires solving an optimization problem for every data point, leading to $O(N^2)$ or $O(N^3)$ complexity. This makes standard SSC or LRR impossible for "Big Data."
To solve this, researchers have introduced several "fast" variants:
- Greedy Heuristics: Abolfazl Hashemi and Haris Vikalo developed Accelerated Sparse Subspace Clustering (ASSC), which uses orthogonal least-squares to achieve the speed of greedy algorithms with the accuracy of optimization.
- Factorization: Jicong Fan proposed k-Factorization Subspace Clustering (k-FSC), which bypasses the affinity matrix entirely by factorizing the data into $k$ groups, allowing for linear-time processing of millions of points.
- Sampling: Methods like Scalable Sparse Subspace Clustering (SSSC) by Lei Zhang use a small representative sample of the data to build the subspace structure and then project the remaining points onto it.
Why It Works: The Spectral Correction
The final step in most of these algorithms is spectral clustering. Even if the coefficient matrix $C$ has some "false connections" (non-zero entries between different subspaces), the spectral step acts as a powerful filter. Gen Li and Yuantao Gu proved in Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph that spectral methods can effectively correct these errors, provided the sampling density within each subspace is high enough to outweigh the noise between them.