Clustering Data on a Union of Intersecting Subspaces

This direction is split into other directions: density-based sample filtering, subspace independence assumption. Its last version stays readable and citable here.

Version 1 of 168 papers92 conceptsfrozen 2026-10-04

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$:

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:

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.

Papers in this version

Showing 60 of 68 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_clustering_data_on_a_union_of_intersecti_a87c898d,
  title = {Clustering Data on a Union of Intersecting Subspaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/clustering-data-on-a-union-of-intersecting-subspaces/rdr_a87c898d913d424fb70031cd81552def},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_clustering_data_on_a_union_of_intersecti_a87c898d_v1,
  title = {Clustering Data on a Union of Intersecting Subspaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/clustering-data-on-a-union-of-intersecting-subspaces/rdr_a87c898d913d424fb70031cd81552def/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}