Minimal Sample Subspace Learning: Theory and Algorithms

Zhenyue Zhang, Yuqing Xia

Abstract

Subspace segmentation is a critical task in machine learning, aiming to group data points into their respective low-dimensional linear subspaces. Traditional methods often struggle when subspaces are heavily intersected or when the mathematical definition of a "correct" segmentation is ambiguous. This paper introduces the Minimal Sample Subspace (MSS) learning framework, which utilizes a rank-restricted self-expressiveness model. By focusing on the sum of ranks of individual segments, the proposed approach ensures unique and connected segmentations even in challenging scenarios. We present hybrid and relaxed optimization strategies that outperform state-of-the-art methods on synthetic and real-world datasets like Extended YaleB and Hopkins 155.

Introduction

Subspace segmentation involves partitioning a collection of data points such that each group belongs to a single linear subspace. This task is foundational for applications ranging from face clustering under varying illumination to motion segmentation in computer vision. While methods like Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) have seen success, they face significant hurdles when subspaces overlap extensively or when data is corrupted by noise.

Figure 1: Visualization of three intersecting subspaces in 3D space. The MSS framework aims to correctly identify these planes even when they share common lines or points.

The primary challenges addressed here are heavy intersection—where sparsity and global rank priors fail—and the lack of a rigorous theoretical definition for "minimal" segmentation in finite sample sets. The MSS framework fills this gap by defining the conditions under which a segmentation is unique and providing robust algorithms to compute it.

The Minimal Sample Subspace (MSS) Framework

The core of the MSS approach is the concept of self-expressiveness: every data point in a subspace can be represented as a linear combination of other points within that same subspace.

Defining Minimality

A sample-spanned subspace is defined as "minimal" if it is rank-deficient, but any subset of its samples with a smaller rank is of full rank. This definition prevents the trivial over-segmentation of data into overly small, meaningless clusters.

Rank-Sum Restriction

A key innovation is the shift from minimizing the global rank (as in LRR) to a prior on the sum of the ranks of individual segments. The authors prove that restricting the rank sum to the true total dimension $d$ ensures that the diagonal blocks of the representation matrix remain "connected." This connectivity is vital for the stability of subsequent spectral clustering steps, preventing the fracturing of true clusters.

Optimization Strategies

To solve the MSS problem, the paper introduces several algorithmic improvements:

  1. Hybrid Optimization (MSS-HO): Primal and "pseudo-dual" optimization problems often converge to different local minima. MSS-HO alternates between these perspectives, allowing the algorithm to "jump out" of local optima and find the globally minimal segmentation, particularly in cases of heavy intersection.
  2. Manifold Conjugate Gradient (MCG): For noiseless data, the authors utilize a gradient descent approach on the Grassmann manifold.
  3. Relaxed Optimization (MSS-RO): To handle noisy real-world data, a relaxed model is solved using the Alternating Direction Method of Multipliers (ADMM), providing robustness against shadows and illumination changes.

Experimental Evaluation

The proposed methods were rigorously tested against synthetic and benchmark datasets.

Synthetic Data

In scenarios specifically designed with high-dimensional pairwise intersections, MSS-HO achieved a 0% error rate. In contrast, standard methods like SSC and LRR failed significantly, with error rates ranging from 10% to 60%.

Real-World Benchmarks

  • Extended YaleB: In face clustering tasks, MSS-RO achieved a median error of 0.25% for 2-individual clusters. As the complexity increased to 10 individuals, MSS-RO maintained a low mean error of 1.82%, significantly outperforming SSC (7.29%) and LRR (12.50%).
  • Hopkins 155: On motion segmentation tasks, MSS-RO proved superior on "hard" video sequences, correctly identifying segments that were previously considered ambiguous to other algorithms.

Conclusion

Minimal Sample Subspace learning provides a robust theoretical and algorithmic foundation for subspace segmentation. By leveraging rank-sum restrictions and hybrid optimization, the framework overcomes the limitations of traditional sparsity and low-rank methods. While the requirement for an estimated rank sum and $O(n^3)$ complexity present areas for future optimization, the MSS framework sets a new standard for accuracy in complex, overlapping data environments.

Summary updated

BibTeX
@article{zhang2019minimal,
  author = {Zhenyue Zhang and Yuqing Xia},
  title = {{Minimal Sample Subspace Learning: Theory and Algorithms}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
}
Figure