Robust Recovery of Subspace Structures by Low-Rank Representation

Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, Yi Ma

TL;DR

This paper introduces Low-Rank Representation (LRR), a novel method for simultaneously clustering data points into their underlying subspaces and correcting errors (like outliers or noise). LRR achieves robust subspace segmentation and error correction by finding the lowest-rank representation of data with respect to a dictionary, offering theoretical guarantees even with corrupted data.

What Problem Does This Paper Address?

Many real-world datasets, such as those in computer vision (motion, faces, textures), can be effectively modeled as originating from a union of multiple linear subspaces. The challenge lies in accurately identifying these subspaces and assigning data points to them, especially when the data is "noisy" or "corrupted." This corruption can take various forms: small perturbations around the true subspaces (noise), gross corruption of individual data points (outliers), or a combination of both. Traditional methods often struggle with these imperfections, leading to inaccurate segmentation or failure to identify outliers. This paper aims to develop a method that can robustly recover the underlying subspace structure and simultaneously clean the data.

Methods

The core of the paper is the Low-Rank Representation (LRR) method. LRR tackles the problem by formulating it as a convex optimization problem. Given a data matrix $X$ and a dictionary matrix $A$, LRR seeks to find a representation $Z$ such that $X \approx AZ$. The key idea is to find the lowest-rank representation $Z$ that can reconstruct $X$. This is achieved by minimizing the nuclear norm of $Z$ (a convex surrogate for rank) subject to the constraint $X = AZ + E$, where $E$ represents the error term.

The authors propose a generalized formulation: $\min \text{rank}(Z) + \lambda \|E\|$, where $\lambda$ is a regularization parameter balancing the low-rank representation and the error term. They then relax the rank function to the nuclear norm and use the $\ell_{2,1}$-norm for the error term $E$ to specifically handle sample-specific corruptions and outliers. This convex optimization problem is solved efficiently using the Augmented Lagrange Multiplier (ALM) method.

A crucial aspect is the choice of the dictionary $A$. While $A$ can be learned, the paper shows that using the data matrix $X$ itself as the dictionary ($A=X$) is effective for subspace segmentation and outlier detection, especially when dealing with sample-specific corruptions. This choice simplifies the problem and allows for theoretical guarantees.

Datasets

The paper evaluates LRR on two primary datasets:

  • Hopkins155: A benchmark dataset for motion segmentation, containing 156 video sequences. While generally clean, some sequences exhibit notable error levels.
  • Yale-Caltech: A dataset created by combining images from the Extended Yale Database B and Caltech101. This dataset is specifically designed to test robustness to outliers and corruptions, with non-face images acting as outliers.

Key Insights and Ideas

  • Row Space is Key for Segmentation: The paper establishes that the row space of the data matrix (specifically, $V V^T$ from its SVD) is directly related to subspace membership. Recovering this row space is thus a direct path to accurate subspace segmentation.
  • LRR as a Generalization: LRR is presented as a generalization of existing methods like Principal Component Analysis (PCA) and Robust PCA (RPCA). It extends their capabilities to handle multiple subspaces and various error types.
  • Dictionary Choice Matters: While learning a dictionary is a future direction, the paper demonstrates that using the data matrix itself as the dictionary ($A=X$) is a surprisingly effective strategy for subspace segmentation and outlier detection, particularly for sample-specific corruptions.
  • Theoretical Guarantees: A significant contribution is the theoretical analysis proving that LRR can recover the true row space and identify outliers under certain conditions, even when the data is corrupted. This provides a strong foundation for its robustness.
  • Unified Framework: LRR offers a unified framework for subspace segmentation, outlier detection, and error correction, addressing these challenges simultaneously rather than as separate problems.

Key Results

  • Robust Segmentation: LRR consistently outperforms PCA and RPCA on the Hopkins155 dataset, achieving significantly lower segmentation errors (e.g., 1.71% mean error for LRR vs. 4.56% for PCA).
  • Outlier Detection: On the Yale-Caltech dataset, LRR demonstrates superior performance in both segmentation accuracy (ACC) and outlier detection (AUC) compared to PCA, RPCA, and SR. For instance, LRR achieved an AUC of 0.9927, while PCA and RPCA achieved 0.9653 and 0.9863, respectively.
  • Parameter Sensitivity: LRR shows remarkable robustness to its main parameter $\lambda$, performing well across a wide range of values on many sequences, unlike some other methods that are highly sensitive.
  • Subspace Number Estimation: The paper proposes an effective method for estimating the number of subspaces, achieving a mean absolute error of 0.25 on the Hopkins155 dataset.
  • Error Correction Visualization: The paper provides visual examples showing how LRR effectively corrects errors in corrupted images, decomposing them into a low-rank "clean" component and a sparse "error" component.

Limitations and Future Work

  • Dictionary Learning: The paper acknowledges that learning an optimal dictionary $A$ could further improve LRR's performance, especially for complex error types beyond sample-specific corruptions.
  • Parameter Selection: While LRR is less sensitive to its parameter $\lambda$ than some other methods, selecting the optimal parameter for various datasets and error types remains a challenge.
  • Theoretical Extension: The proofs for exact recovery of the row space are specific to the $A=X$ case. Extending these proofs to more general dictionary matrices is an open area.
  • Computational Cost: While LRR is efficient, its optimization procedure can require more iterations than some other methods, leading to higher computational costs in some scenarios.
  • Complex Datasets: Handling more complicated datasets with a mix of noise, outliers, and corruptions, and solving model selection problems for these scenarios, are areas for future research.

Summary updated

Abstract

In this work we address the subspace recovery problem. Given a set of data samples (vectors) approximately drawn from a union of multiple subspaces, our goal is to segment the samples into their respective subspaces and correct the possible errors as well. To this end, we propose a novel method termed Low-Rank Representation (LRR), which seeks the lowest-rank representation among all the candidates that can represent the data samples as linear combinations of the bases in a given dictionary. It is shown that LRR well solves the subspace recovery problem: when the data is clean, we prove that LRR exactly captures the true subspace structures; for the data contaminated by outliers, we prove that under certain conditions LRR can exactly recover the row space of the original data and detect the outlier as well; for the data corrupted by arbitrary errors, LRR can also approximately recover the row space with theoretical guarantees. Since the subspace membership is provably determined by the row space, these further imply that LRR can perform robust subspace segmentation and error correction, in an efficient way.
BibTeX
@article{liu2013robust,
  author = {Guangcan Liu and Zhouchen Lin and Shuicheng Yan and Ju Sun and Yong Yu and Yi Ma},
  title = {{Robust Recovery of Subspace Structures by Low-Rank Representation}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2013},
  url = {https://openreview.net/forum?id=kLbOMaX8Xq5i},
}
Figure