Robust Subspace Segmentation by Simultaneously Learning Data Representations and Their Affinity Matrix

Xiaojie GuoIJCAI 2015

Abstract: Subspace segmentation is a critical task in computer vision, aiming to cluster high-dimensional data into low-dimensional subspaces. Traditional methods often decouple representation learning from affinity matrix construction, leading to suboptimal performance in noisy environments. This paper proposes a unified framework that simultaneously learns data representations and their affinity matrix. By enforcing mutual consistency through a Laplacian regularizer and utilizing a Hadamard product for the final affinity, the proposed method demonstrates superior robustness and accuracy across multiple datasets.

Introduction

Subspace segmentation involves grouping data points that lie in a union of low-dimensional subspaces. A common example is clustering face images of different individuals under varying illumination. Most existing approaches follow a two-stage pipeline: first, learning a representation matrix $R$ where data is expressed as linear combinations of other points ($X \approx XR$), and second, constructing an affinity matrix $A$ from $R$. However, this disjoint process often fails when data is corrupted by noise or shadows, as the learned representation does not account for the final clustering structure.

Methodology

The authors bridge this gap with a unified optimization framework. The core of their approach is a mathematical "handshake" between the representation $R$ and the affinity matrix $A$. The objective function minimizes reconstruction error while incorporating a Laplacian regularizer, $\text{tr}(RL_A R^T)$. This term ensures that points with high similarity in $A$ have similar feature representations in $R$.

To handle the non-convex nature of the joint optimization, the authors employ an Augmented Lagrangian Multiplier (ALM) with an Alternating Direction Minimizing (ADM) strategy. This iterative process alternates between solving for $R$ and $A$. Additionally, a $k$-nearest neighbors constraint is applied to $A$ to maintain graph sparsity and reduce noise. The final affinity matrix used for spectral clustering is derived via the Hadamard product ($A \odot R$), which acts as a double-filter to keep only the most consistent connections.

Experimental Evaluation

The model was evaluated on four distinct types of data:

  1. Synthetic Data: Used to test robustness against varying levels of white Gaussian noise.
  2. Extended Yale B: A challenging face dataset containing 38 subjects under extreme lighting conditions (shadows).
  3. USPS: A dataset of 10 classes of handwritten digits ($0-9$).
  4. UMIST: A face dataset featuring 20 subjects with significant pose variations.

Results and Discussion

The proposed method consistently outperformed classic algorithms like Sparse Subspace Clustering (SSC), Low-Rank Representation (LRR), and Least Squares Regression (LSR). On the Extended Yale B dataset, the proposed method achieved 74.48% accuracy, significantly higher than LSR2 (57.73%) and SSC (45.89%).

Robustness to noise: The proposed joint learning method (Affinity+Representation) maintains high accuracy even as noise levels increase, outperforming disjoint approaches. The affinity matrices show clearer block-diagonal structures for the proposed method under noise.

The visual evidence in Figure 1 highlights how the joint learning process preserves the block-diagonal structure of the affinity matrix even at a noise level of $N=0.25$, whereas the standard affinity matrix becomes significantly more cluttered and unreliable.

Parameter Sensitivity and Limitations

While robust, the method's performance is influenced by the choice of the neighbor count $k$.

Accuracy vs k: The clustering accuracy is sensitive to the number of nearest neighbors (k), with an optimal range typically found between 3 and 20.

As shown in Figure 2, the accuracy peaks at low values of $k$ and tends to stabilize or decline as $k$ increases, depending on the underlying data structure. Other limitations include the need to tune hyperparameters ($\lambda_1, \lambda_2, \lambda_3$) and potential scalability issues for extremely large datasets due to the memory requirements of the $n \times n$ affinity matrix.

Conclusion

By simultaneously optimizing for data representations and their affinity matrix, this framework provides a more robust solution for subspace segmentation. The mutual reinforcement between the two components allows the model to handle significant noise and corruption, setting a new benchmark for accuracy in challenging computer vision tasks.

Summary updated

BibTeX
@inproceedings{guo2015robust,
  author = {Xiaojie Guo},
  title = {{Robust Subspace Segmentation by Simultaneously Learning Data Representations and Their Affinity Matrix}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure