Robust Recovery of Subspace Structures by Low-Rank Representation

By Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, Yi Ma. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010

3,507 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/bd569acc57705863f8de3a26853471e7b93e66f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Low-Rank Tensor Constrained Multiview Subspace Clustering (2015, methodology): “To cluster the data into their respective subspaces, we firstly compute a subspace representation matrix Z following [15, 28, 21]:”
Differentially private subspace clustering (2015, background): “Three solvers are considered for the sample-aggregate framework: threshold-based subspace clustering (TSC, [14]), which has provable utility guarantee with sampleaggregation on stochastic models, along with sparse subspace clustering (SSC, [11]) and low-rank representation (LRR, [17]), the two state”
LRRNet: A Novel Representation Learning Guided Fusion Network for Infrared and Visible Images (2023, background): “The emergence of representation-learning algorithms, such as sparse representation (SR) [9], low-rank representation (LRR) and latent low-rank representation (LatLRR) [10], impacted positively on the task of image fusion.”
Deep Comprehensive Correlation Mining for Image Clustering (2019, methodology): “Traditional clustering methods [55, 19, 6], such as K-means, spectral clustering [35, 48], and subspace clustering [31, 16] may fail for two main issues: first, hand-crafted features have limited capacity and cannot dynamically adjust to capture the prior distribution, especially when dealing with l”
A closed form solution to robust subspace estimation and clustering (2011, background): “It is shown in [12] that the optimal solution for C given A is C = V1V T 1 .”
Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview (2021, neutral): “ALRR : an accelerated low-rank representation algorithm published in 2018 [30].”
Scalable Multi-view Subspace Clustering with Unified Anchors (2021, background): “Although many strategies exist in subspace clustering, such as lowrank representation subspace clustering (LRR) [17], sparse subspace clustering (SSC) [7], most of the multi-view subspace clustering methods adopt self-representation to obtain the subspace represen-”
Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit (2015, methodology): “Our conditions are broader than those of state-of-the-art methods based on (cid:96) 2 or nuclear norm regularization, and slightly weaker than those of SSC-BP.”
Multi-Task Learning for Subspace Segmentation (2015, methodology): “To the extent which this dense representation within blocks can outweigh the lack of sparsity outside of blocks, this so-called least squares represenation (LSR) method can potentially outperform SSC (equivalently for LRR in the noiseless case).”
Large-scale Multi-view Subspace Clustering in Linear Time (2019, methodology): “For example, (Wang et al. 2014) proposes a data selection approach; a scalable SSC based on orthogonal matching pursuit is developed in (You, Robinson, and Vidal 2016); a fast solver for SSC is proposed in (Pourkamali-Anaraki and Becker 2018); accelerated LRR is also developed (Fan et al. 2018; Xiao”
Saliency Detection by Multitask Sparsity Pursuit (2012, background): “In [42, Theorem 4.3], the optimal solution (with respect to the variable ) always lies within the subspace spanned by the rows of .”
Deep Domain Generalization With Structured Low-Rank Constraint (2018, background): “The rank minimization issue can be addressed by the trace norm (cid:4) · (cid:4) ∗ as a good surrogate [42].”
Structured AutoEncoders for Subspace Clustering (2018, methodology): “After obtaining deep features, we conduct SSC and LRR to achieve data clustering.”
Anomaly Detection in Hyperspectral Images Based on Low-Rank and Sparse Representation (2016, methodology): “Lowrank representation (LRR) [22], [23] can be used to find the lowest rank representation of all the pixels jointly.”
A Nonlinear Orthogonal Non-Negative Matrix Factorization Approach to Subspace Clustering (2017, methodology): “11 State-of-the-art methods in single view subspace clustering learn affinity graph matrix by imposing 12 sparseness [11], low-rank [12] or jointly sparseness and low-rank constraints [13] on representation matrix.”
Smooth Representation Clustering (2014, background): “For LRR [ 16, 15], it is obvious that EGE conditions (1) and (3) are satisﬁed.”
Consistent and Specific Multi-View Subspace Clustering (2018, methodology): “For the self-representation term, nuclear norm pursues low-rank recovery (Liu et al. 2013) and l0 norm obtains sparse representation under the widest assumption on data (Yang et al.”
Multi-view Subspace Clustering (2015, methodology): “(5) we do not adopt the low rank subspace representation for multi-view features, such as [16].”