Abstract: In this paper, we address the subspace clustering problem. Given a set of data samples (vectors) approximately drawn from a union of multiple subspaces, our goal is to cluster the samples into their respective subspaces and remove possible outliers as well. To this end, we propose a novel objective function named 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 the convex program associated with LRR solves the subspace clustering problem in the following sense: When the data is clean, we prove that LRR exactly recovers the true subspace structures; when the data are 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 data corrupted by arbitrary sparse 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 clustering and error correction in an efficient and effective way.
Introduction
This paper introduces Low-Rank Representation (LRR)—a powerful framework for clustering data that lies in a union of multiple subspaces. It moves beyond traditional methods by providing a convex optimization approach that is mathematically elegant and remarkably robust to noise and outliers. LRR is a "global" approach to subspace clustering that finds the lowest-rank representation of a dataset relative to a dictionary. Unlike previous methods, it can simultaneously segment data into multiple subspaces and identify sample-specific outliers with theoretical guarantees of exact recovery.
The Subspace Clustering Problem
In many real-world scenarios, data doesn't just sit in one neat group; it belongs to a union of subspaces. For example, video frames of different moving objects or photos of different people’s faces represent distinct subspaces. The challenge is subspace clustering: how do we automatically group these data points into their respective subspaces when the data is "dirty"?
Previous methods like Principal Component Analysis (PCA) assume only a single subspace. Others, like Sparse Subspace Clustering (SSC), look at data points locally. The authors identify a gap: the need for a method that looks at the global structure of the data to handle "sample-specific corruptions"—where some data points are completely wrong (outliers) or partially corrupted.
Low-Rank Representation (LRR)
The authors propose a novel objective function: $$\min_{Z,E} \|Z\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} \quad X = AZ + E$$
- The Nuclear Norm (|Z|_*): This acts as a convex surrogate for the rank of the matrix. By minimizing this, LRR forces the representation $Z$ to be as low-rank as possible, capturing the global structure of the subspaces.
- The $\ell_{2,1}$ Norm: This is the "secret sauce" for robustness. It encourages the error matrix $E$ to be "column-sparse," meaning it assumes that while most data points are clean, a few specific samples might be completely corrupted or be outliers.
- The Dictionary ($A$): While $A$ can be any dictionary spanning the data space, the authors often use the data matrix $X$ itself as the dictionary.
By utilizing the $\ell_{2,1}$ norm, LRR specifically targets sample-specific corruptions (as seen in Figure 2c), where entire columns of the data matrix are corrupted, rather than just random entry-wise noise.
Key Insights and Ideas
- Row Space is Key: A major insight is that the membership of a data point in a subspace is determined by the row space of the data. LRR is specifically designed to recover this row space accurately, even when the data is corrupted.
- Global vs. Local: Unlike sparse representation methods that find the best individual fit for each point, LRR finds the lowest rank for the entire dataset jointly. This global view makes it more stable against noise.
- Automatic Outlier Detection: Because of the $\ell_{2,1}$ norm, the columns of the error matrix $E$ with non-zero values point directly to the outliers in the dataset.
Experimental Results
The authors evaluated LRR on two primary benchmarks: the Hopkins155 motion segmentation dataset and a custom Yale-Caltech dataset designed to test outlier detection.
- Superior Accuracy: On the Hopkins155 motion dataset, LRR achieved a mean segmentation error of 1.71%, significantly outperforming PCA (4.56%) and Robust PCA (3.26%).
- Robustness to Outliers: In the Yale-Caltech experiment, LRR achieved an 86.13% accuracy in clustering faces while maintaining an Area Under Curve (AUC) of 0.9927 for outlier detection. This means it almost perfectly separated "face" data from "junk" data.
- Error Correction: The paper demonstrates qualitatively that LRR can "clean" images. By separating the low-rank part ($XZ$) from the sparse error ($E$), it can remove shadows, specularities, or occlusions from face images.
Conclusion
LRR provides a robust, mathematically grounded framework for subspace clustering. While it faces some challenges regarding dictionary selection and computational scaling (due to SVD operations), its ability to recover global structures from corrupted data marks a significant advancement in the field. Future work could explore randomized or incremental SVDs to scale LRR to larger datasets.
Summary updated