Abstract
Traditional subspace clustering assumes data lies in linear subspaces, an assumption frequently violated by real-world non-linear distortions. This paper introduces Adaptive Low-Rank Kernel Subspace Clustering (LRKSC), a method that learns a low-rank kernel matrix to map non-linear data into a linear feature space. By jointly optimizing the kernel mapping and the clustering objective, LRKSC effectively "uncurls" complex manifolds, achieving state-of-the-art performance on motion segmentation and face clustering benchmarks.
Introduction
Subspace clustering aims to group data points belonging to different low-dimensional structures. A cornerstone of modern methods like Sparse Subspace Clustering (SSC) is the self-expressiveness property: the assumption that a data point can be represented as a linear combination of others in the same subspace.
However, real-world data often undergoes non-linear transformations. For instance, perspective distortion in video sequences makes object trajectories non-linear. While "kernel tricks" can map data into higher-dimensional spaces, standard kernels (e.g., RBF or Polynomial) are static and unaware of the underlying subspace structure. They may inadvertently map data into a high-dimensional "cloud" where the low-rank structure is lost, rendering clustering difficult.
Methodology: Adaptive Low-Rank Kernels
The proposed LRKSC framework moves beyond fixed kernels by jointly optimizing for the clustering and the kernel mapping itself. The core idea is to ensure that the data remains low-rank in the implicit feature space.
Key technical components include:
- Adaptive Kernel Learning: The method solves for a kernel matrix $K = B^T B$. By minimizing the nuclear norm of $B$, the algorithm ensures the feature space representation is low-rank.
- Self-Expressiveness in Feature Space: The self-expressiveness property is enforced within the high-dimensional space, ensuring mapped points are representable by their neighbors.
- Guided Regularization: To avoid trivial solutions, the learned kernel is regularized to stay near a pre-defined "guide" kernel (e.g., a polynomial kernel).
- Robustness: A variation includes a sparse outlier term to handle gross corruptions like shadows or occlusions.
- Optimization: The non-convex objective is solved using the Alternating Direction Method of Multipliers (ADMM).
Experimental Evaluation
The method was rigorously tested on four computer vision benchmarks:
- Hopkins155: 155 video sequences for motion segmentation.
- Extended Yale B: 38 subjects under varying illumination.
- ORL: 40 subjects with diverse expressions and fewer samples per subject.
- COIL-100: 100 objects viewed from multiple angles.
Results and Discussion
LRKSC consistently outperformed both linear and fixed-kernel baselines. On the challenging Hopkins155 sequence "2RT3RCR," which features heavy perspective distortion, LRKSC achieved 98.04% accuracy compared to SSC's 64.38%.
The results highlight several key insights:
- The Necessity of Low-Rank Structures: For subspace clustering to succeed in a feature space, that space must maintain a low-rank structure. Adaptive learning "uncurls" manifolds into linear subspaces that SSC can process.
- Robustness in Data-Starved Scenarios: On the ORL dataset, where samples per subject are limited, LRKSC proved significantly more robust than fixed-kernel methods which often fail to span the subspace.
- Scalability: As shown in the face clustering results, LRKSC maintains a lower error rate even as the number of subjects increases.
Conclusion
LRKSC demonstrates that an adaptive kernel is significantly more powerful than a "one-size-fits-all" fixed kernel for non-linear subspace clustering. While the method currently relies on a manually selected "guide" kernel and hyperparameters, future work involving Multiple Kernel Learning (MKL) could automate these selections. This research paves the way for more generalized techniques capable of handling increasingly complex non-linear data structures.
Summary updated