High-dimensional data, such as a collection of 1-megapixel images, technically exists in a million-dimensional space. However, the meaningful content of that data rarely fills the entire volume. Instead, data points typically lie on or near a union of much lower-dimensional "slices" known as subspaces.
Subspace clustering is the task of simultaneously finding these hidden subspaces and grouping the data points that belong to each one. The breakthrough that makes modern subspace clustering work is a simple but powerful geometric observation known as the self-expression property.
The Intuition of Self Expression
Imagine several sheets of paper (2D subspaces) tilted at different angles in a 3D room. If you pick a point on one of those sheets, you can describe its position using a combination of other points on that same sheet. Crucially, you cannot easily describe it using points from a different sheet without using a lot of "energy" or creating a very complex mapping.
As formalized by Ehsan Elhamifar in Sparse Subspace Clustering: Algorithm, Theory, and Applications, the self-expression property states that each data point in a union of subspaces can be efficiently represented as a linear combination of other points from the same subspace.
In this framework, the dataset acts as its own dictionary. To cluster the data, we look for a coefficient matrix $C$ such that $X = XC$, where $X$ is our data. If we force $C$ to be sparse, the math naturally favors picking "neighbors" from the same subspace to reconstruct each point. This coefficient matrix then serves as an affinity graph: if point A helps reconstruct point B, they likely belong to the same cluster.
From Linear Slices to Deep Manifolds
Traditional methods like Sparse Subspace Clustering (SSC) work beautifully when the subspaces are perfectly flat (linear). However, real-world data is often warped or "curled." To handle this, researchers moved the self-expression principle into the latent space of neural networks.
In Deep Subspace Clustering Networks, Pan Ji, Mathieu Salzmann, and their colleagues introduced a "self-expressive layer." This is a fully connected layer without an activation function or bias, placed between an encoder and a decoder. The encoder "unfolds" the non-linear data into a linear latent space, the self-expressive layer learns the subspace relationships, and the decoder ensures the original data can still be reconstructed.
This approach, further refined by zhao kang in Structure Learning with Similarity Preserving, allows the model to preserve the "DNA" of data relationships—the similarity matrix—even when the input space is highly complex.
The Quest for the Block Diagonal
The "holy grail" of a self-expression matrix is a block-diagonal structure. In a perfect world, the matrix $C$ would only have non-zero values in blocks corresponding to each cluster, with zeros everywhere else (meaning no point is ever reconstructed using points from a different cluster).
To encourage this, researchers like Junjian Zhang have introduced Block Diagonal Priors. By explicitly penalizing connections that fall outside these blocks during training, the network learns a much cleaner affinity matrix, which significantly improves the accuracy of the final spectral clustering step.
Solving the Scalability Problem
For years, the biggest weakness of self-expressive methods was the $N \times N$ coefficient matrix. If you have a million data points, you need a trillion-element matrix, which is computationally impossible for most hardware. Furthermore, these models were "transductive," meaning they couldn't easily handle new data points without retraining the whole matrix.
Julian Busch and Thomas Seidl addressed this in Learning Self-Expression Metrics for Scalable and Inductive Subspace Clustering. They replaced the explicit $N \times N$ matrix with a Siamese network that learns a metric for self-expression. Instead of storing every relationship, the network learns the rule for how points in a subspace relate to one another. This shift reduced parameter counts by over 99% and allowed the models to generalize to unseen data for the first time.
Robustness and Missing Data
The self-expression property is surprisingly resilient. Mahdi Soltanolkotabi and Emmanuel J. Candès provided a geometric analysis proving that these methods can succeed even when subspaces overlap or when the data is heavily corrupted by outliers.
This robustness extends to missing information. Brian Eriksson and Laura Balzano demonstrated in High-Rank Matrix Completion and Subspace Clustering with Missing Data that even if a matrix is globally high-rank and full of holes, we can perfectly recover it by treating it as a union of low-rank subspaces. By identifying local "neighborhoods" that obey the self-expression property, the model can fill in missing entries far more efficiently than standard matrix completion techniques.