Correntropy Induced L2 Graph for Robust Subspace Clustering

Canyi Lu, Jinhui Tang, Min Lin, Liang Lin, Shuicheng Yan, Zhouchen Lin

Introduction

Subspace clustering is a cornerstone of computer vision, enabling the grouping of high-dimensional data points—such as face images or motion trajectories—into their respective low-dimensional subspaces. However, real-world data is frequently contaminated by non-Gaussian noise, pixel corruption, and physical occlusions. Traditional methods like Sparse Subspace Clustering (SSC) and Least Squares Regression (LSR) often rely on the Frobenius norm (Mean Squared Error), which is notoriously sensitive to outliers. Large errors from a few corrupted pixels can dominate the optimization process, leading to a breakdown in clustering accuracy.

Methodology: The Correntropy Induced Metric

To address these limitations, this paper proposes the Correntropy Induced L2 (CIL2) graph. The core innovation lies in replacing global error metrics with the Correntropy Induced Metric (CIM), derived from Information Theoretic Learning (ITL).

Unlike the quadratic L2 norm, CIM is a local metric that utilizes a Gaussian kernel to measure similarity. As shown in the comparison below, while L2 error grows quadratically and L1 grows linearly, the CIM "saturates" for large errors. This means that once an error exceeds a certain threshold (becoming an outlier), its influence on the total objective function is capped, effectively allowing the model to ignore heavily corrupted data points.

Comparison of L1, L2, and CIM loss functions showing the saturation effect of CIM for large errors.

The authors further introduce rCIL2, a row-based variant designed to handle contiguous occlusions (like a scarf or sunglasses) by treating entire rows of the error matrix as potential outliers.

Optimization and Unified Framework

The resulting non-convex objective function is solved using a multiplicative half-quadratic optimization technique. This approach transforms the problem into an iteratively reweighted least squares task, ensuring computational efficiency and convergence. Notably, the authors demonstrate that several existing methods (SSC, LRR, MSR) can be viewed as special cases within this unified half-quadratic framework.

Experimental Evaluation

The proposed methods were rigorously tested on three benchmark datasets: Yale, ORL, and AR Face Databases. To simulate real-world challenges, the researchers applied various synthetic corruptions, including:

  • Random pixel corruption (up to 90%).
  • Random block occlusions.
  • "Unrelated image" occlusions (e.g., overlaying a monkey face on a human face).

Key Results

CIL2 and rCIL2 consistently outperformed state-of-the-art techniques across all noise scenarios.

  • Robustness to Random Noise: On the Yale dataset with 50% pixel corruption, CIL2 maintained approximately 50% accuracy, while standard LSR dropped to roughly 35%.
  • Handling Contiguous Occlusions: The rCIL2 variant proved exceptionally effective for real-world occlusions in the AR dataset, achieving 85.2% accuracy for faces with sunglasses and 78.4% for those with scarves.
  • Performance Stability: As shown in the figure below, the proposed methods exhibit much slower performance degradation compared to traditional methods like LRR or SSC as the percentage of occlusion increases.
Clustering performance (Accuracy and NMI) on the AR database under varying levels of random block occlusion.

Conclusion

The Correntropy Induced L2 Graph provides a robust framework for subspace clustering by intelligently weighting errors. By leveraging the saturation property of correntropy, the model preserves the "grouping effect" of L2 regularization while remaining resilient to extreme outliers. Future work may involve automating the selection of the kernel parameter ($\sigma$) and extending the framework to other high-dimensional data domains beyond facial recognition.

Summary updated

BibTeX
@inproceedings{lu2013correntropy,
  author = {Canyi Lu and Jinhui Tang and Min Lin and Liang Lin and Shuicheng Yan and Zhouchen Lin},
  title = {{Correntropy Induced L2 Graph for Robust Subspace Clustering}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  doi = {10.1109/iccv.2013.226},
}
Figure