High-dimensional data often appears complex, but it frequently concentrates around a collection of low-dimensional linear or affine structures. For instance, face images under varying illumination, motion trajectories in video streams, and text documents of different topics naturally form distinct low-dimensional subspaces. Subspace clustering is the task of partitioning these data points into their respective groups without supervision.
However, the mathematical elegance of traditional subspace clustering comes with a severe computational penalty. As noted by Babak Hosseini et al. in Non-Negative Local Sparse Coding for Subspace Clustering, many standard methods rely on affinity matrices that scale quadratically ($O(n^2)$) or cubically ($O(n^3)$) with the number of data points $n$. When datasets scale to hundreds of thousands or millions of samples, this creates an insurmountable computational bottleneck.
To make subspace clustering practical for real-world applications, researchers have developed distinct strategies to break this complexity wall.
The Root of the Bottleneck: Self-Expression
To understand why traditional subspace clustering scales poorly, we must look at the self-expressive property. Traditional algorithms, such as Sparse Subspace Clustering (SSC), assume that each data point can be represented as a linear combination of all other data points in the dataset.
Self-Expression: [ Point i ] = c_1*[Point 1] + c_2*[Point 2] + ...
+ c_n*[Point n]
└─────────────────── n coefficients ───────────────────┘
This formulation requires solving an optimization problem to find an $n \times n$ coefficient matrix. As Maryam Abdolali et al. point out in Scalable and robust sparse subspace clustering using randomized clustering and multilayer graphs, the number of optimization variables grows with the square of the dataset size, making standard convex solvers unusable for large datasets.
Furthermore, downstream steps typically require Singular Value Decomposition (SVD) or matrix inversions on this $n \times n$ matrix to perform spectral clustering. As explained by the authors of Feature concatenation multi-view subspace clustering and Multi-view Low-rank Sparse Subspace Clustering, these operations incur a cubic $O(n^3)$ time complexity. Even algebraic methods, which offer strong theoretical guarantees, face exponential complexity relative to the number of subspaces, a limitation that Manolis C. Tsakiris demonstrates applies even when extending these methods to affine spaces in Algebra Clustering of Affine Subspaces.
To bypass these limitations, modern research focuses on three primary scaling paradigms.
Strategy 1: From Self-Expression to Basis Representation
The most direct way to achieve linear scaling ($O(n)$) is to change how data points are represented. Instead of forcing every point to be a combination of all other $n$ points, we can represent them using a much smaller, fixed set of learnable subspace bases or anchor points.
Basis Representation: [ Point i ] = c_1*[Basis 1] + c_2*[Basis 2] + ...
+ c_k*[Basis k]
└─────────────────── k coefficients ───────────────────┘
(where k << n, decoupling complexity from dataset size)
This insight forms the foundation of modern linear-time architectures. In Efficient Deep Embedded Subspace Clustering, Jinyu Cai et al. introduced a deep embedded subspace clustering method that replaces the traditional self-expressive layer with a set of learnable subspace bases. By decoupling the representation from the total number of samples, the computational complexity drops from $O(n^2)$ to $O(n)$.
Similarly, in Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images, Xianlu Li et al. applied this basis-representation paradigm to hyperspectral image clustering. This shift allows deep clustering networks to scale efficiently to massive, high-resolution imagery while simultaneously preserving local spatial continuity and non-local spectral similarities.
Strategy 2: Greedy Optimization via Matching Pursuits
A second strategy retains the self-expressive framework but replaces slow, exact convex optimization algorithms (such as Basis Pursuit) with fast, greedy approximations.
In Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit, Chong You et al. proposed SSC-OMP. Instead of optimizing over the entire dataset simultaneously, the algorithm leverages Orthogonal Matching Pursuit (OMP) to greedily select the most representative points for each sample one by one. This algorithmic shift yields a massive speedup of three to four orders of magnitude, enabling sparse subspace clustering to handle over 100,000 data points.
Building on this direction, Michael Tschannen et al. provided the first rigorous analytical performance characterization for greedy matching pursuit algorithms in Noisy subspace clustering via matching pursuits. The authors proved that these highly efficient greedy methods can match the accuracy of slower state-of-the-art techniques while remaining robust to severe noise and parameter tuning.
Strategy 3: Sketching and Randomized Sampling
When a dataset is too large to process even with fast optimization, a third alternative is to operate on a compressed or intelligently sampled version of the data.
Panagiotis A. Traganitis et al. developed a randomized framework called SkeVa-SC (Sketching and Validation Subspace Clustering) in Efficient subspace clustering of large-scale data streams with misses. Instead of computing an affinity matrix for the entire dataset, the algorithm uses non-parametric kernel density estimation to sample a small, highly representative "sketch" of the data. The core clustering is performed only on this compact subset, and the results are subsequently projected back to the remaining data points.
1. Large Dataset ───(Smart Sampling)───► 2. Compact "Sketch"
│
(Subspace Clustering)
▼
4. Full Clustering ◄───(Out-of-Sample)─── 3. Clustered Sketch
Results Projection
By shifting the heavy lifting to a small fraction of the data, sketching frameworks bypass the quadratic scaling bottleneck entirely, allowing subspace clustering to scale to massive streaming datasets.
Alternative Paradigms: Clustering by Classification
Rather than modifying the optimization or sampling of self-expressive models, some approaches restructure the clustering problem entirely. For instance, Vasileios Zografos treats the unsupervised problem as a "clustering by classification" task in Discriminative Subspace Clustering. By training an ensemble of quadratic classifiers on automatically generated weak labels, this method bypasses sparse representation entirely, maintaining low computational complexity while achieving high robustness across motion and face datasets.
Key Foundational Work
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation (2011) — contributed 1 concept elements to this direction.
MKPM: A multiclass extension to the kernel projection machine (2011) — contributed 1 concept elements to this direction.
Towards Min Max Generalization in Reinforcement Learning (2010) — contributed 1 concept elements to this direction.