Abstract
We propose a new subspace clustering model to segment data which is drawn from multiple linear or affine subspaces. Unlike the well-known sparse subspace clustering (SSC) and low-rank representation (LRR) which transfer the subspace clustering problem into two steps' algorithm including building the affinity matrix and spectral clustering, our proposed model directly learns the different subspaces' indicator so that low-rank based different groups are obtained clearly. To better approximate the low-rank constraint, we suggest to use Schatten p-norm to relax the rank constraint instead of using trace norm. We tactically avoid the integer programming problem imposed by group indicator constraint to let our algorithm more efficient and scalable. Furthermore, we extend our discussion to the general case in which subspaces don't pass the original point. The new algorithm's convergence is given, and both synthetic and real world datasets demonstrate our proposed model's effectiveness.
Introduction
Subspace clustering is a fundamental task in computer vision and machine learning, aimed at partitioning high-dimensional data into clusters that lie on low-dimensional subspaces. Common applications include motion segmentation in video sequences and face clustering under varying illumination.
Traditional methods like Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) typically rely on a two-step pipeline: first constructing an affinity matrix based on data self-representation, and then applying spectral clustering. However, this approach often suffers from suboptimality due to the disconnect between the two steps, reliance on loose rank approximations (like the trace norm), and an inherent bias toward linear subspaces that pass through the origin.
Methodology
The proposed model addresses these limitations by directly learning a discrete group indicator matrix, effectively performing segmentation in a single optimization step.
Schatten p-norm Relaxation and Rank Squaring
While the trace norm is a popular convex surrogate for the rank function, it often fails to provide a tight enough approximation for clean subspace separation. The model utilizes the Schatten $p$-norm (where $0 < p < 1$) to more accurately reflect the true rank of the data matrices. Additionally, by minimizing the square of the ranks rather than a simple sum, the model avoids trivial solutions and successfully partitions data into multiple distinct low-rank groups.
Handling Affine Subspaces
Many existing models assume subspaces are linear. However, real-world data often lies on affine subspaces—subspaces that are shifted away from the origin. As shown in the figure below, a line not passing through the origin results in a rank-2 matrix representation, whereas a line through the origin is rank-1.
By introducing a shift vector into the objective function, the model "re-centers" these affine subspaces, allowing for more flexible and accurate modeling of complex datasets.
Optimization
An iterative re-weighted algorithm is employed to solve the resulting non-convex problem. This approach avoids the integer programming challenges typically associated with group indicator constraints, ensuring the algorithm remains computationally efficient and scales linearly with the number of data points.
Experimental Results
The model was evaluated on several benchmarks, including the Hopkins 155 motion segmentation dataset and various facial image datasets (MSRA, JAFFE, XM2VTS).
On the Hopkins 155 dataset, the proposed method achieved a state-of-the-art mean accuracy of 98.59%, with significantly lower variance than competing methods like SSC and LRR. On the MSRA face dataset, it reached 93.11% accuracy, demonstrating superior performance in handling high-dimensional image data. Synthetic tests further confirmed the model's robustness to noise and its ability to perfectly recover intersecting subspace structures even where traditional Euclidean-distance-based methods failed.
Conclusion
By integrating group indicator learning with a tighter rank approximation and affine subspace support, this model provides a robust and efficient framework for subspace clustering. The results demonstrate that directly learning group structures while accounting for the affine nature of real-world data leads to significant improvements in segmentation accuracy across a variety of domains.
Summary updated