Robust Recovery of Subspace Structures by Low-Rank Representation

Guangcan LiuZhouchen LinShuicheng YanJu SunYong YuYi Ma

article2010TPAMI3,535 citations

Introduces Low-Rank Representation (LRR), providing exact theoretical recovery guarantees for clustering data sampled from multiple subspaces even in the presence of severe outliers and arbitrary corruptions.

Listen

The paper introduces Low-Rank Representation (LRR) to solve the subspace clustering problem, in which data samples drawn approximately from a union of linear subspaces must be grouped into their respective subspaces while errors such as noise, outliers, and corruptions are removed. This task arises in motion segmentation, face recognition, and image processing, where a single low-rank model is often insufficient and existing methods such as PCA or robust PCA degrade when multiple subspaces are present or when errors are sample-specific.

The work sets out to show that a convex nuclear-norm program, using the observed data matrix itself as dictionary, can recover the row space of the clean data matrix and thereby determine the correct segmentation, while simultaneously identifying or correcting errors. The method is analyzed under three increasingly realistic assumptions (clean data, sparse column-wise corruptions or outliers, and a mixture of dense noise with sparse corruptions) and is solved by an augmented Lagrange multiplier algorithm whose per-iteration cost scales linearly with the number of samples once a low-rank dictionary is available.

On the Hopkins 155 motion benchmark the approach yields a mean segmentation error of 1.71 percent across all 156 sequences, roughly half the error of the next-best baseline, while also correctly predicting the number of subspaces in 78 percent of sequences. On a composite Yale-Caltech collection containing 1 204 face images and 609 non-face outliers, LRR simultaneously achieves 86 percent segmentation accuracy and an AUC of 0.993 for outlier detection, outperforming PCA, two RPCA variants, and sparse-representation clustering. Theoretical results establish that, when the fraction of outliers is below a data-dependent threshold, any minimizer exactly recovers the row space and the indices of the outliers; for denser noise the method still guarantees approximate recovery whose error is bounded by the ambient dimension plus the rank of the clean data.

These guarantees imply that practitioners can replace fragile single-subspace preprocessing steps with a single convex program that both clusters and cleans data, reducing the need for manual outlier removal or separate denoising stages. The recovered row-space matrix can be fed directly into spectral clustering, and the sparse error term itself supplies a saliency or discriminative-feature map useful for downstream recognition tasks.

Further gains are expected from learning an explicit low-rank dictionary that satisfies the row-space recovery condition, from tightening the parameter-selection rule for the trade-off weight λ, and from extending the formulation to incorporate multiple feature modalities. The main practical limitations are that performance remains sensitive to λ when error levels are high and that the current analysis assumes the dictionary spans the row space of the clean data; both issues warrant additional study before deployment on very large or heavily corrupted collections.

Columbia University Microsoft National University of Singapore Peking University Shanghai Jiao Tong University University of Illinois Urbana-Champaign feature space low-rank representation robust subspace clustering subspace segmentation methods

arXiv: 1010.2955

Paper: Robust Face Recognition via Sparse Representation, John Wright et al. (2009). Reading the sparse representation framework for face recognition provides essential context for extending l1-minimization techniques to robust subspace recovery and error correction.

No sufficiently relevant recommendations were found.

Cover for Robust Recovery of Subspace Structures by Low-Rank Representation

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.

Topics

feature space

Keywords

low-rank representation robust subspace clustering subspace segmentation methods rank minimization matrix completion robust PCA nuclear norm minimization spectral clustering affinity matrix convex optimization

I. INTRODUCTION
II. RELATED WORK
III. PRELIMINARIES AND PROBLEM STATEMENT
A. Summary of Main Notations
B. Relations Between Segmentation and Row Space
C. Problem Statement
A. Low-Rank Representation
B. Analysis on the LRR Problem
C. Recovering Low-Rank Matrices by Convex Optimization
V. SUBSPACE CLUSTERING BY LRR
A. Exactness to Clean Data
B. Robustness to Outliers and Sample-Specific Corruptions
C. Robustness in the Presence of Noise, Outliers and Sample-Specific Corruptions
Algorithm 2 Subspace Segmentation
Algorithm 3 Estimating the Subspace Number k
D. Algorithms for Subspace Segmentation, Model Estimation and Outlier Detection
VI. EXPERIMENTS
A. Experimental Data
B. Baselines and Evaluation Metrics
C. Results on Hopkins155
D. Results on Yale-Caltech
VII. CONCLUSION AND FUTURE WORK
APPENDIX
A. Terminologies
B. Proofs
C. Evaluation Metrics

Knowls

Knowl 1 — Low-Rank Representation for Matrix Recovery and Subspace Modeling
model/method
Low-Rank Representation (LRR) represents an observed data matrix $X = [x_1, \dots, x_n] \in \mathbb{R}^{d \times n}$ as linear combinations of the columns of a dictionary matrix $A \in \mathbb{R}^{d \times m}$ corrupted by an error matrix $E \in \mathbb{R}^{d \times n}$ , seeking the lowest-rank representation matrix $Z \in \mathbb{R}^{m \times n}$ :

$\min_{Z, E} \text{rank}(Z) + \lambda \|E\|_\ell \quad \text{s.t.} \quad X = AZ + E$

where $\lambda > 0$ is a trade-off parameter and $\|\cdot\|_\ell$ is a matrix norm modeling corruption. To obtain a tractable convex program, the matrix rank is relaxed to the nuclear norm $\|Z\|_* = \sum_i \sigma_i(Z)$ (sum of singular values). For sample-specific corruptions and outliers (where column supports of $E$ are sparse), the error is regularized by the matrix $\ell_{2,1}$ norm $\|E\|_{2,1} = \sum_{j=1}^n \|[E]_{:,j}\|_2$ , yielding the convex optimization problem:

$\min_{Z, E} \|Z\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} \quad X = AZ + E$

For dense Gaussian noise, $\|E\|_F^2$ is used; for random entrywise corruptions, $\|E\|_1 = \sum_{i,j} |[E]_{ij}|$ is used. In unsupervised subspace clustering where no clean external dictionary is available, the data matrix itself is chosen as the dictionary ( $A = X$ ).
Knowl 2 — Closed-Form Solution and Rank Equivalence for Clean Low-Rank Representation
theoretical result
Let $A \in \mathbb{R}^{d \times m}$ with $A \neq 0$ , and let $X \in \mathbb{R}^{d \times n}$ lie in the column span of $A$ ( $X \in \text{span}(A)$ ). Consider the clean nuclear norm minimization problem:

$\min_{Z} \|Z\|_* \quad \text{s.t.} \quad X = AZ$

This convex problem has a unique minimizer given in closed form by:

$Z^* = A^\dagger X$

where $A^\dagger$ is the Moore-Penrose pseudoinverse of $A$ . Furthermore, this unique solution satisfies:

$\text{rank}(Z^*) = \text{rank}(X)$

Consequently, $Z^* = A^\dagger X$ is also a global minimum rank solution to the non-convex rank minimization problem $\min_Z \text{rank}(Z) \text{ s.t. } X = AZ$ .

In the self-representation setting ( $A = X$ ), if $X$ has skinny Singular Value Decomposition $X = U \Sigma V^T$ , the unique minimizer is the Shape Interaction Matrix (SIM) orthogonal projector onto the row space of $X$ :

$Z^* = X^\dagger X = V V^T$
Knowl 3 — Block-Diagonal Property of LRR over Independent Subspaces
theoretical result
Let $\{S_i\}_{i=1}^k$ be a collection of $k$ independent linear subspaces in $\mathbb{R}^d$ , defined such that $S_i \cap \sum_{j \neq i} S_j = \{0\}$ for all $i \in \{1, \dots, k\}$ , where each subspace has dimension $r_i > 0$ . Let $A = [A_1, A_2, \dots, A_k] \in \mathbb{R}^{d \times m}$ and $X = [X_1, X_2, \dots, X_k] \in \mathbb{R}^{d \times n}$ , where each $A_i \in \mathbb{R}^{d \times m_i}$ consists of $m_i$ samples spanning $S_i$ with $\text{rank}(A_i) = r_i$ , and each $X_i \in \mathbb{R}^{d \times n_i}$ consists of $n_i$ samples drawn strictly from $S_i$ .

The unique optimal solution $Z^*$ to the clean LRR problem $\min_Z \|Z\|_* \text{ s.t. } X = AZ$ is strictly block-diagonal:

$Z^* = \text{diag}(Z_1^*, Z_2^*, \dots, Z_k^*) = \begin{bmatrix} Z_1^* & 0 & \cdots & 0 \\ 0 & Z_2^* & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & Z_k^* \end{bmatrix}$

where each submatrix $Z_i^* \in \mathbb{R}^{m_i \times n_i}$ satisfies $\text{rank}(Z_i^*) = \text{rank}(X_i)$ for all $i \in \{1, \dots, k\}$ . Cross-subspace representation coefficients between samples from distinct subspaces are identically zero.
Knowl 4 — Exact Row Space Recovery and Outlier Detection via Self-Dictionary LRR
theoretical result
Let $X = X_0 + E_0 \in \mathbb{R}^{d \times n}$ be an observed data matrix composed of clean authentic samples $X_0 \in \mathbb{R}^{d \times n}$ drawn strictly from a union of low-rank subspaces and sample-specific outliers $E_0 \in \mathbb{R}^{d \times n}$ . Let $X_0$ have rank $r_0$ and skinny singular value decomposition $X_0 = U_0 \Sigma_0 V_0^T$ . Let $I_0 = \{i : [X_0]_{:,i} = 0, [E_0]_{:,i} \neq 0\}$ denote the column indices of the outliers, and let $\gamma = |I_0| / n$ be the outlier fraction.

Consider self-representation LRR:

$\min_{Z, E} \|Z\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} \quad X = XZ + E$

where $\|E\|_{2,1} = \sum_{i=1}^n \|[E]_{:,i}\|_2$ .

There exists a positive threshold $\gamma^* > 0$ such that for any outlier fraction $\gamma \le \gamma^*$ , setting the regularization parameter to:

$\lambda = \frac{3}{7 \|X\| \sqrt{\gamma^* n}}$

where $\|X\|$ is the spectral norm of $X$ , guarantees that any optimal solution $(Z^*, E^*)$ exactly recovers both the row space projector of the clean data and the outlier support:

$U^* (U^*)^T = V_0 V_0^T \quad \text{and} \quad I^* = I_0$

where $U^*$ is the orthonormal basis matrix for the column space of $Z^*$ (left singular vectors of the skinny SVD $Z^* = U^* \Sigma^* (V^*)^T$ ), and $I^* = \{i : \|[E^*]_{:,i}\|_2 \neq 0\}$ is the column support of $E^*$ .
Knowl 5 — Inexact Augmented Lagrange Multiplier Algorithm for LRR
algorithm
The Inexact Augmented Lagrange Multiplier (Inexact ALM) algorithm minimizes the augmented Lagrangian of the LRR problem $\min_{Z,E} \|Z\|_* + \lambda \|E\|_{2,1} \text{ s.t. } X = AZ + E$ with auxiliary variable $J = Z$ :

$\mathcal{L} = \|J\|_* + \lambda \|E\|_{2,1} + \text{tr}(Y_1^T(X - AZ - E)) + \text{tr}(Y_2^T(Z - J)) + \frac{\mu}{2}\left(\|X - AZ - E\|_F^2 + \|Z - J\|_F^2\right)$
Input: Data matrix $X \in \mathbb{R}^{d \times n}$ , dictionary $A \in \mathbb{R}^{d \times m}$ , regularization parameter $\lambda > 0$ .
Initialize: $Z = J = 0$ , $E = 0$ , $Y_1 = 0$ , $Y_2 = 0$ , $\mu = 10^{-6}$ , $\mu_{\max} = 10^6$ , $\rho = 1.1$ , $\varepsilon = 10^{-8}$ .
while $\|X - AZ - E\|_\infty \ge \varepsilon$ or $\|Z - J\|_\infty \ge \varepsilon$ do
     $M = Z + Y_2 / \mu$
    Compute SVD $M = U_M \Sigma_M V_M^T$
     $J = U_M \text{diag}(\max(0, \Sigma_M - 1/\mu)) V_M^T$
     $Z = (I + A^T A)^{-1} (A^T (X - E) + J + (A^T Y_1 - Y_2) / \mu)$
     $Q = X - AZ + Y_1 / \mu$
    for $i = 1$ to $n$ do
        if $\|[Q]_{:,i}\|_2 > \lambda / \mu$ then
             $[E]_{:,i} = \frac{\|[Q]_{:,i}\|_2 - \lambda / \mu}{\|[Q]_{:,i}\|_2} [Q]_{:,i}$
        else
             $[E]_{:,i} = 0$
        end if
    end for
     $Y_1 = Y_1 + \mu (X - AZ - E)$
     $Y_2 = Y_2 + \mu (Z - J)$
     $\mu = \min(\rho \mu, \mu_{\max})$
end while
Output: Representation matrix $Z^* = Z$ , error matrix $E^* = E$ .
Knowl 6 — Computational Reduction for LRR via Row-Space Invariance
theoretical result
For any optimal solution $(Z^*, E^*)$ to the LRR problem $\min_{Z, E} \|Z\|_* + \lambda \|E\|_{2,1} \text{ s.t. } X = AZ + E$ , the representation matrix satisfies:

$Z^* \in \text{span}(A^T)$

Let $r_A = \text{rank}(A)$ , and let $P^* \in \mathbb{R}^{m \times r_A}$ be an orthonormal basis matrix for $\text{span}(A^T)$ obtained by orthogonalizing the columns of $A^T$ . The representation can be factorized as $Z = P^* \tilde{Z}$ with $\tilde{Z} \in \mathbb{R}^{r_A \times n}$ , transforming LRR into the equivalent lower-dimensional optimization problem:

$\min_{\tilde{Z}, E} \|\tilde{Z}\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} \quad X = B \tilde{Z} + E$

where $B = A P^* \in \mathbb{R}^{d \times r_A}$ . The optimal solution to the original problem is recovered via $Z^* = P^* \tilde{Z}^*$ . This reduction decreases the computational complexity per Inexact ALM iteration from $O(n^3)$ to $O(d n r_A + n r_A^2 + r_A^3)$ . When $A = X \in \mathbb{R}^{d \times n}$ and $d \le n$ , the per-iteration complexity is at most $O(d^2 n + d^3)$ .
Knowl 7 — Subspace Segmentation Pipeline via LRR Affinity and Normalized Cuts
algorithm
Subspace segmentation groups $n$ data samples into $k$ subspace clusters by constructing a non-negative affinity matrix from the column space of the optimal representation matrix $Z^*$ and clustering via Normalized Cuts (NCut).
Input: Data matrix $X \in \mathbb{R}^{d \times n}$ , number of subspaces $k$ , parameter $\lambda > 0$ .
Solve $\min_{Z,E} \|Z\|_* + \lambda \|E\|_{2,1} \text{ s.t. } X = XZ + E$ to obtain minimizer $(Z^*, E^*)$ .
Compute skinny SVD of $Z^*$ : $Z^* = U^* \Sigma^* (V^*)^T$ .
Form column-weighted matrix $M = U^* (\Sigma^*)^{1/2}$ .
Form $\tilde{U}$ by normalizing each row of $M$ to unit Euclidean length: $[\tilde{U}]_{i,:} = [M]_{i,:} / \|[M]_{i,:}\|_2$ .
Construct affinity matrix $W \in \mathbb{R}^{n \times n}$ with entries $[W]_{ij} = ([\tilde{U} \tilde{U}^T]_{ij})^2$ .
Apply Normalized Cuts (NCut) spectral clustering on affinity matrix $W$ to segment samples into $k$ clusters.
Output: Cluster assignment for each of the $n$ samples.
Knowl 8 — Subspace Number Estimation via Laplacian Singular Value Soft Thresholding
algorithm
When the number of subspaces $k$ is unknown, it is estimated from the singular values of the normalized graph Laplacian of the affinity matrix produced by LRR.
Input: Data matrix $X \in \mathbb{R}^{d \times n}$ , threshold parameter $\tau \in (0, 1)$ (default $\tau = 0.08$ ).
Compute affinity matrix $W \in \mathbb{R}^{n \times n}$ using the LRR subspace segmentation procedure.
Compute degree matrix $D = \text{diag}(\sum_{j=1}^n [W]_{1j}, \dots, \sum_{j=1}^n [W]_{nj})$ .
Compute normalized Laplacian matrix $L = I - D^{-1/2} W D^{-1/2} \in \mathbb{R}^{n \times n}$ .
Compute singular values $\{\sigma_i\}_{i=1}^n$ of $L$ .
for $i = 1$ to $n$ do
    if $\sigma_i \ge \tau$ then
         $s_i = 1$
    else
         $s_i = \log_2(1 + \sigma_i^2 / \tau^2)$
    end if
end for
Estimate subspace count $\hat{k} = n - \text{int}(\sum_{i=1}^n s_i)$ , where $\text{int}(\cdot)$ rounds to the nearest integer.
Output: Estimated subspace number $\hat{k}$ .
Knowl 9 — Frobenius Norm Near-Recovery Bound of LRR under Arbitrary Errors
theoretical result
Let $X \in \mathbb{R}^{d \times n}$ be an arbitrary observed matrix, and let $X_0 \in \mathbb{R}^{d \times n}$ be the underlying clean data matrix with rank $r_0$ and skinny SVD $X_0 = U_0 \Sigma_0 V_0^T$ . For any minimizer $(Z^*, E^*)$ of the self-representation LRR problem:

$\min_{Z, E} \|Z\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} \quad X = XZ + E$

with $\lambda > 0$ , the representation matrix $Z^*$ satisfies the deterministic recovery error bound:

$\|Z^* - V_0 V_0^T\|_F \le \min(d, n) + r_0$

where $\|\cdot\|_F$ denotes the Frobenius norm. This bound holds universally without requiring any statistical or distributional assumptions on the underlying noise, corruptions, or outliers.

Knowl 10 — Subspace Segmentation Benchmark on Hopkins155 Dataset

data/table

The Hopkins155 motion database contains 156 video sequences (each providing tracked feature point trajectory matrices for 2 or 3 motion subspaces). The table compares subspace segmentation error rates (%) of LRR ( $\\lambda = 4$ ) with baselines (PCA, $\\text{RPCA}_1$ , $\\text{RPCA}_{2,1}$ , Sparse Representation / SR) on all 156 sequences, and against prior subspace segmentation methods on the standard 155 non-degenerate sequences.

Segmentation errors (%) over all 156 sequences
Metric	PCA	$\text{RPCA}_1$	$\text{RPCA}_{2,1}$	SR	LRR
mean	4.56	4.13	3.26	3.89	1.71
std.	10.80	10.37	9.09	7.70	4.85
max	49.78	45.83	47.15	32.57	33.33
avg. runtime (s)	0.2	0.8	0.8	4.2	1.9
Mean segmentation errors (%) over 155 sequences
Method	GPCA	RANSAC	MSL	LSA	LLMC
mean error	10.34	9.76	5.06	4.94	4.80
Method	PCA	LBF	ALC	SCC	SLBF
mean error	4.47	3.72	3.37	2.70	1.35
Method	SSC	SC	Favaro et al.	Latent LRR	LRR (this paper)
mean error	1.24	1.20	1.22	0.85	1.59

LRR achieves a mean segmentation error of 1.71% across all 156 sequences (1.59% on 155 sequences), outperforming PCA (4.56%), $\text{RPCA}_1$ (4.13%), $\text{RPCA}_{2,1}$ (3.26%), and SR (3.89%). On Hopkins155, LRR's mean error remains between 1.69% and 1.87% across $\lambda \in [3, 5]$ .

Knowl 11 — Subspace Segmentation and Outlier Detection Performance on Yale-Caltech Dataset

data/table

The Yale-Caltech dataset evaluates combined subspace clustering and outlier detection. It contains 1204 authentic face images from Extended Yale Database B across 38 subjects (each subject defining a low-rank subspace) and 609 non-face outlier images from Caltech101 (images resized to $20 \times 20$ , yielding data matrix $X \in \mathbb{R}^{400 \times 1813}$ ). Subspace segmentation accuracy (ACC, %) is evaluated on authentic face images, and outlier detection quality is evaluated via the Area Under the ROC Curve (AUC) computed by thresholding column $\ell_2$ norms $\|[E^*]_{:,i}\|_2$ .

Metric	PCA	$\text{RPCA}_1$	$\text{RPCA}_{2,1}$	SR	LRR
ACC (%)	77.15	82.97	83.72	73.17	86.13
AUC	0.9653	0.9819	0.9863	0.9239	0.9927
Execution Time (s)	0.6	60.8	59.2	383.5	152.6

LRR achieves 86.13% segmentation accuracy and 0.9927 outlier detection AUC, outperforming PCA (77.15% ACC, 0.9653 AUC), $\text{RPCA}_1$ (82.97% ACC, 0.9819 AUC), $\text{RPCA}_{2,1}$ (83.72% ACC, 0.9863 AUC), and Sparse Representation (73.17% ACC, 0.9239 AUC).

Coverage note — No substantial contributed material was omitted; minor non-convex formulations cited from concurrent work and standard lemma proofs from the appendix were omitted in accordance with the extraction rules.

References

1.W. Gear, “Multibody grouping from motion images,” Int'l J. Computer Vision, vol. 29, no. 2, pp. 133–150, 1998.
2.J. Yan and M. Pollefeys, “A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate,” in Euro. Conf. Computer Vision, vol. 4, 2006, pp. 94–106.
3.S. Rao, R. Tron, R. Vidal, and Y. Ma, “Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 32, no. 10, pp. 1832–1845, 2010.
4.G. Liu and S. Yan, “Latent low-rank representation for subspace segmentation and feature extraction,” in IEEE Int'l Conf. Computer Vision, 2011.
5.Y. Ma, H. Derksen, W. Hong, and J. Wright, “Segmentation of multivariate mixed data via lossy data coding and compression,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, no. 9, pp. 1546–1562, 2007.
6.E. Cand`es and Y. Plan, “Matrix completion with noise,” in IEEE Proceeding, vol. 98, 2010, pp. 925–936.
7.E. Cand`es, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?” J. of the ACM, 2009.
8.J. Ho, M. Yang, J. Lim, K. Lee, and D. Kriegman, “Clustering appearances of objects under varying illumination conditions,” in IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, 2003, pp. 11–18.
9.G. Liu, Z. Lin, X. Tang, and Y. Yu, “Unsupervised object segmentation with a hybrid graph model (HGM),” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 32, no. 5, pp. 910–924, 2010.
10.M. Fischler and R. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM, vol. 24, no. 6, pp. 381–395, 1981.
11.C. Zhang and R. Bitmead, “Subspace system identification for training-based mimo channel estimation,” Automatica, vol. 41, no. 9, pp. 1623–1632, 2005.
12.J. Costeira and T. Kanade, “A multibody factorization method for independently moving objects,” Int'l J. Computer Vision, vol. 29, no. 3, pp. 159–179, 1998.
13.E. Elhamifar and R. Vidal, “Sparse subspace clustering,” in IEEE Conf. Computer Vision and Pattern Recognition, vol. 2, 2009, pp. 2790–2797.
14.G. Liu, Z. Lin, and Y. Yu, “Robust subspace segmentation by low-rank representation,” in Int'l Conf. Machine Learning, 2010, pp. 663–670.
15.M. Soltanolkotabi and E. Cand`es, “A geometric analysis of subspace clustering with outliers,” arXiv:1112.4258v2, 2011.
16.H. Xu, C. Caramanis, and S. Sanghavi, “Robust pca via outlier pursuit,” in Neural Info. Processing Systems, 2010.
17.M. Fazel, “Matrix rank minimization with applications,” PhD thesis, 2002.
18.B. Chen, G. Liu, Z. Huang, and S. Yan, “Multi-task low-rank affinities pursuit for image segmentation,” in IEEE Int'l Conf. Computer Vision, 2011.
19.C. Lang, G. Liu, J. Yu, and S. Yan, “Saliency detection by multi-task sparsity pursuit,” IEEE Trans. Image Processing, 2011.
20.Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Information Theory, vol. 55, no. 11, pp. 5302–5316, 2009.
21.A. Gruber and Y. Weiss, “Multibody factorization with uncertainty and missing data using the EM algorithm,” in IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, 2004, pp. 707–714.
22.T. Zhang, A. Szlam, and G. Lerman, “Median k-flats for hybrid linear modeling with many outliers,” in Workshop on Subspace Methods, 2009.
23.A. Yang, S. Rao, and Y. Ma, “Robust statistical estimation and segmentation of multiple subspaces,” in Workshop of IEEE Conf. Computer Vision and Pattern Recognition, 2006.
24.Y. Ma, A. Yang, H. Derksen, and R. Fossum, “Estimation of subspace arrangements with applications in modeling and segmenting mixed data,” SIAM Review, vol. 50, no. 3, pp. 413–458, 2008.
25.S. Rao, A. Yang, S. Sastry, and Y. Ma, “Robust algebraic segmentation of mixed rigid-body and planar motions in two views,” Int'l J. Computer Vision, vol. 88, no. 3, pp. 425–446, 2010.
26.J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, pp. 888–905, 2000.
27.G. Chen and G. Lerman, “Spectral curvature clustering (scc),” Int'l J. Computer Vision, vol. 81, pp. 317–330, 2009.
28.——, “Foundations of a multi-way spectral clustering framework for hybrid linear modeling,” Found. Computational Mathematics, vol. 9, pp. 517–558, 2009.
29.T. Zhang, A. Szlam, Y. Wang, and G. Lerman, “Hybrid linear modeling via local best-fit flats,” arXiv:1010.3460, 2011.
30.E. Arias-Castro, G. Chen, and G. Lerman, “Spectral clustering based on local linear approximations,” ELECTRONIC JOURNAL OF STATISTICS, vol. 5, pp. 1537–1587, 2011.
31.F. Lauer and C. Schn´orr, “Spectral clustering of linear subspaces for motion segmentation,” in IEEE Int'l Conf. Computer Vision, 2009.
32.D. Donoho, “For most large underdetermined systems of linear equations the minimal ℓ1-norm solution is also the sparsest solution,” Comm. Pure and Applied Mathematics, vol. 59, pp. 797–829, 2004.
33.B. Nasihatkon and R. Hartley, “Graph connectivity in sparse subspace clustering,” in IEEE Conf. Computer Vision and Pattern Recognition, 2011, pp. 2137–2144.
34.G. Lerman and T. Zhang, “Robust recovery of multiple subspaces by geometric lp minimization,” arXiv:1104.3770, 2011.
35.Z. Zhang, X. Liang, A. Ganesh, and Y. Ma, “TILT: Transform invariant low-rank textures,” in Asian Conf. Computer Vision, 2010.
36.Z. Lin, M. Chen, L. Wu, and Y. Ma, “The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices,” UIUC Technical Report UILU-ENG-09-2215, Tech. Rep., 2009.
37.D. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods. Academic Press, 1982.
38.J. Cai, E. Cand`es, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” SIAM J. on Optimization, vol. 20, no. 4, pp. 1956–1982, 2010.
39.J. Yang, W. Yin, Y. Zhang, and Y. Wang, “A fast algorithm for edge-preserving variational multichannel image restoration,” SIAM J. Imaging Sciences, vol. 2, no. 2, pp. 569–592, 2009.
40.Y. Zhang, “Recent advances in alternating direction methods: Practice and theory,” Tutorial, 2010.
41.J. Eckstein and D. Bertsekas, “On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators,” Mathematical Programming, vol. 55, pp. 293–318, 1992.
42.S. Wei and Z. Lin, “Analysis and improvement of low rank representation for subspace segmentation,” arXiv:1107.1561, 2010.
43.G. Liu, H. Xu, and S. Yan, “Exact subspace segmentation and outlier detection by low-rank representation,” in Int'l Conf. Artificial Intelligence and Statistics, 2012.
44.R. Vidal, Y. Ma, and J. Piazzi, “A new gpca algorithm for clustering subspaces by fitting, differentiating and dividing polynomials,” in IEEE Conf. Computer Vision and Pattern Recognition, 2004, pp. 510–517.
45.K. Huang, Y. Ma, and R. Vidal, “Minimum effective dimension for mixtures of subspaces: a robust gpca algorithm and its applications,” in IEEE Conf. Computer Vision and Pattern Recognition, 2004, pp. 631–638.
46.R. Tron and R. Vidal, “A benchmark for the comparison of 3-d motion segmentation algorithms,” in IEEE Conf. Computer Vision and Pattern Recognition, 2007, pp. 1–8.
47.K. Lee, J. Ho, and D. Kriegman, “Acquiring linear subspaces for face recognition under variable lighting,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 5, pp. 684–698, 2005.
48.F.-F. Li, R. Fergus, and P. Perona, “Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories,” in Workshop of IEEE Conf. Computer Vision and Pattern Recognition, 2004, pp. 178–188.
49.Y. Sugaya and K. Kanatani, “Multi-stage unsupervised learning for multi-body motion segmentation,” IEICE Trans. Information Systems, pp. 1935–1942, 2004.
50.A. Goh and R. Vidal, “Segmenting motions of different types by unsupervised manifold clustering,” in IEEE Conf. Computer Vision and Pattern Recognition, 2007.
51.P. Favaro, R. Vidal, and A. Ravichandran, “A closed form solution to robust subspace estimation and clustering,” in IEEE Conf. Computer Vision and Pattern Recognition, 2011.

Citation

MLA

Liu, G., et al. “Robust Recovery of Subspace Structures by Low-Rank Representation”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 1, 2013, pp. 171–84, https://doi.org/10.1109/TPAMI.2012.88.

APA

Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., & Ma, Y. (2013). Robust Recovery of Subspace Structures by Low-Rank Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1), 171–184. https://doi.org/10.1109/TPAMI.2012.88

Chicago

Liu, G., Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. 2013. “Robust Recovery of Subspace Structures by Low-Rank Representation”. IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (1): 171–84. https://doi.org/10.1109/TPAMI.2012.88.

Harvard

Liu, G. et al. (2013) “Robust Recovery of Subspace Structures by Low-Rank Representation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1), pp. 171–184. Available at: https://doi.org/10.1109/TPAMI.2012.88.

Vancouver

1. Liu G, Lin Z, Yan S, Sun J, Yu Y, Ma Y (2013) Robust Recovery of Subspace Structures by Low-Rank Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 35:171–184

BibTeX

@article{Liu_2013, title={Robust Recovery of Subspace Structures by Low-Rank Representation}, volume={35}, ISSN={2160-9292}, url={http://dx.doi.org/10.1109/TPAMI.2012.88}, DOI={10.1109/tpami.2012.88}, number={1}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Liu, Guangcan and Lin, Zhouchen and Yan, Shuicheng and Sun, Ju and Yu, Yong and Ma, Yi}, year={2013}, month=Jan, pages={171–184} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Robust Recovery of Subspace Structures by Low-Rank Representation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Low-Rank Representation for Matrix Recovery and Subspace Modeling

Knowl 2 — Closed-Form Solution and Rank Equivalence for Clean Low-Rank Representation

Knowl 3 — Block-Diagonal Property of LRR over Independent Subspaces

Knowl 4 — Exact Row Space Recovery and Outlier Detection via Self-Dictionary LRR

Knowl 5 — Inexact Augmented Lagrange Multiplier Algorithm for LRR

Knowl 6 — Computational Reduction for LRR via Row-Space Invariance

Knowl 7 — Subspace Segmentation Pipeline via LRR Affinity and Normalized Cuts