Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

John WrightArvind GaneshShankar R. RaoYi-Gang PengYi Ma

article2009NeurIPS1,444 citations

Proves that a low-rank matrix corrupted by arbitrarily large, sparse errors can be efficiently and exactly recovered via convex optimization, establishing theoretical recovery guarantees alongside a scalable algorithm for high-dimensional data analysis.

Listen

Modern computational applications such as video analysis, facial recognition, web search, and bioinformatics rely on extracting low-dimensional patterns from high-dimensional datasets. Principal component analysis has long served as a standard tool for finding these patterns, but it is fragile when data contain large corruptions, occlusions, or sensor failures. Classical methods fail under gross errors, while existing robust alternatives either lack formal guarantees or are computationally prohibitive for large-scale operations.

The article demonstrates that high-dimensional data can be accurately and efficiently separated into an underlying low-rank structure and a sparse error component using convex optimization. Specifically, it establishes that a computationally tractable algorithm can achieve exact mathematical recovery of corrupted data under broad conditions.

The researchers evaluated this framework through theoretical proofs, numerical simulations, and applied experiments on computer vision datasets. The approach frames robust recovery as a convex program that simultaneously minimizes the nuclear norm (sum of singular values) of the low-rank component and the sum of absolute values of the sparse errors. To scale the solution to practical matrix dimensions, the article developed a fast first-order optimization algorithm using proximal gradient and thresholding techniques with continuation schemes.

The evaluation produced several key findings. First, the convex program achieves exact recovery with high probability even when the rank of the true data matrix grows nearly proportionally to matrix dimensions and gross errors corrupt a constant fraction of all entries. Second, numerical simulations demonstrated that recovery succeeds across an empirical boundary roughly defined where the sum of the rank fraction and error fraction is under 35 percent, such as successfully handling matrices with 10 percent corrupted entries. Third, the proposed first-order algorithm converged efficiently, typically requiring around 100 to 200 iterations and adding only a modest computational overhead compared to classical singular value decomposition. Fourth, applied demonstrations confirmed practical utility by successfully separating static backgrounds from moving foreground objects in surveillance video and removing shadows and specular reflections from facial recognition imagery. Finally, the theoretical analysis extended low-rank matrix completion results, proving exact completion is possible when rank grows proportionally with dimension.

These findings indicate that organizations processing high-dimensional visual or bioinformatic data no longer need to accept trade-offs between computational tractability and robustness to gross errors. Automated systems can remove severe measurement noise and localized occlusions in polynomial time, improving the reliability and performance of downstream machine learning models without manual data cleaning.

Stakeholders developing computer vision, surveillance, or facial recognition pipelines should consider adopting convex robust principal component analysis as a standard pre-processing stage. Before deploying at enterprise scale, teams should run pilot implementations to confirm performance under application-specific conditions, such as continuous video streams or extreme aspect ratios.

The current theoretical guarantees assume that errors are sparsely distributed and that low-rank components do not align with standard basis vectors. Additionally, while empirical results show robustness to noise, the primary proofs focus on an idealized model without dense, small-amplitude noise. Confidence in the reported results is high based on the rigorous mathematical proofs and confirming simulations, though practitioners should account for application-specific noise when implementing the algorithm.

Microsoft University of Illinois Urbana-Champaign bioinformatics computer vision image analysis Robust Principal Component Analysis low-rank matrix recovery convex optimization

arXiv: 0905.0233

Paper: Full regularization path for sparse principal component analysis, Alexandre d'Aspremont et al. (2007). Provides the foundational convex semidefinite relaxation framework for finding sparse structures in principal component analysis.
Paper: Robust Face Recognition via Sparse Representation, John Wright et al. (2009). Introduces the formulation of modeling gross corruptions and occlusions in visual data via sparse error components solved by l1-minimization.
Paper: Efficient projections onto the l1-ball for learning in high dimensions, John C. Duchi et al. (2008). Develops efficient projection and optimization subroutines for high-dimensional l1-norm regularization that underpin fast convex solvers.
Paper: Efficient sparse coding algorithms, Honglak Lee et al. (2006). Details alternating convex optimization methods for sparse representation problems that motivated scalable algorithms in low-rank and sparse matrix recovery.
Paper: Feature selection, L1 vs. L2 regularization, and rotational invariance, Andrew Y. Ng (2004). Explains why L1-regularization succeeds at recovering sparse patterns in high dimensions, providing the theoretical basis for sparse error modeling.

Paper: Robust Recovery of Subspace Structures by Low-Rank Representation, Guangcan Liu et al. (2010). Generalizes robust recovery from a single low-rank subspace to a union of multiple linear subspaces via Low-Rank Representation.
Paper: Robust Subspace Segmentation by Low-Rank Representation, Guangcan Liu et al. (2010). Applies low-rank and sparse matrix decomposition concepts to robust subspace segmentation and clustering using augmented Lagrange multipliers.
Paper: Spectral Regularization Algorithms for Learning Large Incomplete Matrices, Rahul Mazumder et al. (2010). Extends nuclear-norm convex regularizations with specialized thresholding algorithms to scale matrix completion on large, noisy datasets.
Paper: A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers, Sahand N. Negahban et al. (2009). Establishes a unified statistical framework for high-dimensional regularized M-estimators, encompassing combined nuclear and L1 norm decomposable penalties.
Paper: Sparse Subspace Clustering: Algorithm, Theory, and Applications, Ehsan Elhamifar et al. (2012). Builds on convex optimization principles to solve subspace clustering under sparse corruptions and missing entries.
Paper: Tensor Completion for Estimating Missing Values in Visual Data, Ji Liu et al. (2009). Extends low-rank completion and convex trace-norm optimization from 2D matrices to higher-order visual tensors.
Paper: Online Learning for Matrix Factorization and Sparse Coding, Julien Mairal et al. (2010). Develops online optimization algorithms that extend matrix factorization and sparse coding methods to massive, streaming datasets.

Cover for Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

Abstract

Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision.

Topics

bioinformatics computer vision image analysis optimization principal component analysis (pca)ranging theoretical result web searches optimization problems robust performance

Keywords

Robust Principal Component Analysis low-rank matrix recovery convex optimization matrix completion nuclear norm minimization singular value decomposition convex relaxation classical PCA dimensionality reduction

1 Introduction
2 Problem Setting and Main Results
3 Scalable Optimization for Robust PCA
4 Simulations and Experiments
5 Discussion and Future Work
References

Knowls

Knowl 1 — Exact Robust PCA Recovery Under Non-Vanishing Error Fractions
theoretical result
Let $A_0 \in \mathbb{R}^{m \times m}$ be a low-rank matrix whose singular spaces are distributed according to the random orthogonal model of rank $r$ , and let $E_0 \in \mathbb{R}^{m \times m}$ be an error matrix whose signs and support are distributed according to the Bernoulli sign-and-support model with error probability $\rho_s$ .

For any constant $p > 0$ , there exist positive constants $C_0^* > 0$ , $\rho_s^* > 0$ , and dimension threshold $m_0$ such that for all $m > m_0$ , if
$r \le C_0^* \frac{m}{\log(m)} \quad \text{and} \quad \rho_s \le \rho_s^*,$
then with probability at least $1 - C m^{-p}$ (for some constant $C > 0$ ), the pair $(A_0, E_0)$ is the uniquely defined minimizer of the convex program:
$(A_0, E_0) = \arg\min_{A, E} \|A\|_* + \frac{1}{\sqrt{m}} \|E\|_1 \quad \text{subject to} \quad A + E = A_0 + E_0,$
where $\|A\|_* = \sum_i \sigma_i(A)$ denotes the nuclear norm and $\|E\|_1 = \sum_{i,j} |E_{i,j}|$ is the entrywise $\ell_1$ -norm.

This guarantees exact recovery of both the low-rank component and the sparse corruptions even when the rank grows proportionally up to a logarithmic factor, $O(m / \log m)$ , and the number of arbitrary gross errors grows proportionally to the total number of entries $m^2$ .
Knowl 2 — Convex Formulation of Robust Principal Component Analysis
model/method
Given an observed data matrix $D \in \mathbb{R}^{m \times n}$ generated by corrupting a low-rank matrix $A_0 \in \mathbb{R}^{m \times n}$ with an unknown sparse error matrix $E_0 \in \mathbb{R}^{m \times n}$ such that $D = A_0 + E_0$ , the idealized robust PCA problem seeks the lowest-rank representation subject to sparse errors:
$\min_{A, E} \operatorname{rank}(A) + \gamma \|E\|_0 \quad \text{subject to} \quad A + E = D,$
where $\|E\|_0$ is the number of non-zero entries in $E$ .

Because this rank-and-sparsity minimization is NP-hard, it is relaxed into a tractable convex surrogate by substituting the nuclear norm $\|A\|_* = \sum_i \sigma_i(A)$ for $\operatorname{rank}(A)$ and the entrywise $\ell_1$ -norm $\|E\|_1 = \sum_{i,j} |E_{i,j}|$ for $\|E\|_0$ :
$\min_{A, E} \|A\|_* + \lambda \|E\|_1 \quad \text{subject to} \quad A + E = D.$
The objective $\|A\|_* + \lambda \|E\|_1$ is the convex envelope of $\operatorname{rank}(A) + \lambda \|E\|_0$ over the set of matrices satisfying $\max(\|A\|_{2,2}, \|E\|_{1,\infty}) \le 1$ . For square matrices $D \in \mathbb{R}^{m \times m}$ , the regularizing parameter is set to $\lambda = m^{-1/2}$ .
Knowl 3 — Robust PCA via Accelerated Proximal Gradient with Continuation
algorithm
The equality-constrained convex problem is solved via a relaxed Lagrangian formulation parameterized by $\mu > 0$ :
$\min_{A, E} \mu \|A\|_* + \lambda \mu \|E\|_1 + \frac{1}{2} \|D - A - E\|_F^2.$
As $\mu \searrow 0$ , the solution to this penalized objective approaches the solution of the equality-constrained problem. The proximal updates decouple into singular value thresholding for $A$ (using singular value thresholding operator $\mathcal{D}_\tau(Y) = U (S - \tau I)_+ V^*$ ) and entrywise soft-thresholding for $E$ (using operator $\mathcal{S}_\tau(Y) = \operatorname{sign}(Y) \circ (|Y| - \tau)_+$ ). Acceleration via Nesterov-style predictor-corrector points $(\tilde{A}_k, \tilde{E}_k)$ yields an $O(k^{-2})$ convergence rate. A continuation scheme geometrically decays $\mu$ by a factor of $0.9$ from $\mu_0 = 0.99 \|D\|_{2,2}$ down to a floor $\bar{\mu} = 10^{-5} \mu_0$ .
Input: Observation matrix $D \in \mathbb{R}^{m \times n}$ , weight $\lambda > 0$
Initialize $A_0 \leftarrow 0, A_{-1} \leftarrow 0, E_0 \leftarrow 0, E_{-1} \leftarrow 0$
Initialize $t_0 \leftarrow 1, t_{-1} \leftarrow 1, \mu_0 \leftarrow 0.99 \|D\|_{2,2}, \bar{\mu} \leftarrow 10^{-5} \mu_0, k \leftarrow 0$
while not converged do
     $\tilde{A}_k \leftarrow A_k + \frac{t_{k-1}-1}{t_k} (A_k - A_{k-1})$
     $\tilde{E}_k \leftarrow E_k + \frac{t_{k-1}-1}{t_k} (E_k - E_{k-1})$
     $Y_k^A \leftarrow \tilde{A}_k - \frac{1}{2} (\tilde{A}_k + \tilde{E}_k - D)$
     $(U, S, V) \leftarrow \operatorname{svd}(Y_k^A)$
     $A_{k+1} \leftarrow U (S - \frac{\mu_k}{2} I)_+ V^*$
     $Y_k^E \leftarrow \tilde{E}_k - \frac{1}{2} (\tilde{A}_k + \tilde{E}_k - D)$
     $E_{k+1} \leftarrow \operatorname{sign}(Y_k^E) \circ (|Y_k^E| - \frac{\lambda \mu_k}{2} \mathbf{1}\mathbf{1}^*)_+$
     $t_{k+1} \leftarrow \frac{1 + \sqrt{1 + 4 t_k^2}}{2}$
     $\mu_{k+1} \leftarrow \max(0.9 \mu_k, \bar{\mu})$
     $k \leftarrow k + 1$
end while
return $A_k, E_k$
The algorithm terminates when the Frobenius norm of the subgradient $(\tilde{A}_k - A_{k+1} + E_{k+1} - \tilde{E}_k, \tilde{E}_k - E_{k+1} + A_{k+1} - \tilde{A}_k)$ drops below $2 \max(1, \|(A_{k+1}, E_{k+1})\|_F) \times \tau$ with $\tau = 10^{-7}$ .
Knowl 4 — Matrix Completion Under Proportional Rank Growth
theoretical result
Let $A_0 \in \mathbb{R}^{m \times m}$ be a rank- $r$ matrix distributed according to the random orthogonal model. Let $\Upsilon \subset [m] \times [m]$ be an independently chosen subset of observed entries where each coordinate pair $(i, j)$ is included independently with probability $1 - \rho_s$ .

There exist positive numerical constants $m_0$ , $\rho_r^*$ , $\rho_s^*$ , and $C$ such that if $m > m_0$ ,
$r \le \rho_r^* m \quad \text{and} \quad \rho_s \le \rho_s^*,$
then with probability at least $1 - \exp(-C m)$ , $A_0$ is the uniquely defined minimizer of the convex matrix completion problem:
$A_0 = \arg\min_A \|A\|_* \quad \text{subject to} \quad A(i, j) = A_0(i, j) \quad \forall (i, j) \in \Upsilon.$
This guarantees exact matrix completion in the linear proportional growth regime where rank $r$ scales as a constant fraction $\rho_r^* m$ of the dimension from a fraction $(1 - \rho_s) m^2$ of observed entries.
Knowl 5 — Random Orthogonal Model and Bernoulli Error Sign and Support Model
definition
The theoretical recovery guarantees for Robust Principal Component Analysis rely on two distributional models:
1. Random Orthogonal Model: A matrix $A_0 \in \mathbb{R}^{m \times m}$ of rank $r$ satisfies the random orthogonal model if its singular value decomposition has left and right singular vector matrices $U, V \in \mathbb{R}^{m \times r}$ that are drawn independently and uniformly at random from the Stiefel manifold $\mathcal{W}_r^m$ (according to the Haar measure). Its non-zero singular values may take arbitrary positive values.
2. Bernoulli Sign-and-Support Model: An error matrix $E_0 \in \mathbb{R}^{m \times m}$ satisfies the Bernoulli sign-and-support model with parameter $\rho_s \in [0, 1]$ if the entries of $\operatorname{sign}(E_0)$ are independent and identically distributed random variables taking the value $0$ with probability $1 - \rho_s$ , and taking values $+1$ and $-1$ each with probability $\rho_s / 2$ . The magnitudes of the non-zero entries of $E_0$ may take arbitrary values.

Knowl 6 — Exact Recovery Performance of Robust PCA Under Proportional Dimension Scaling

data/table

The performance of the accelerated proximal gradient algorithm for Robust PCA was tested on synthetic square matrices of dimension $m \in \{100, 200, 400, 800\}$ with regularization parameter $\lambda = m^{-1/2}$ . The low-rank component $A_0 = L R^T$ was formed from two independent $m \times r$ matrices with i.i.d. $\mathcal{N}(0, 1)$ entries, fixing $r = 0.05 m$ . The corruption matrix $E_0$ had support chosen uniformly at random (affecting either $5\%$ or $10\%$ of entries) with non-zero magnitudes uniformly distributed in $[-500, 500]$ .

$m$	$\operatorname{rank}(A_0)$	$\\|E_0\\|_0$	$\frac{\\|\hat{A}-A_0\\|_F}{\\|A_0\\|_F}$	$\operatorname{rank}(\hat{A})$	$\\|\hat{E}\\|_0$	# iterations	time (s)
100	5	500	$3.0 \times 10^{-4}$	5	506	104	1.6
200	10	2,000	$2.1 \times 10^{-4}$	10	2,012	104	7.9
400	20	8,000	$1.4 \times 10^{-4}$	20	8,030	104	64.8
800	40	32,000	$9.9 \times 10^{-5}$	40	32,062	104	531.6
100	5	1,000	$3.1 \times 10^{-4}$	5	1,033	108	1.6
200	10	4,000	$2.3 \times 10^{-4}$	10	4,042	107	8.0
400	20	16,000	$1.6 \times 10^{-4}$	20	16,110	107	66.7
800	40	64,000	$1.2 \times 10^{-4}$	40	64,241	106	542.8

The algorithm recovers the exact true rank ( $\operatorname{rank}(\hat{A}) = \operatorname{rank}(A_0)$ ) and produces relative errors $\|\hat{A} - A_0\|_F / \|A_0\|_F$ on the order of $10^{-4}$ to $10^{-5}$ . Across all problem sizes, convergence is achieved in approximately 104 to 108 iterations, showing that total computation scales predominantly with the per-iteration singular value decomposition cost.

Knowl 7 — Empirical Phase Transition in Rank Ratio and Error Sparsity for Robust PCA
empirical result
For matrices of fixed size $m = 200$ , the empirical success rate of Robust PCA was evaluated across rank fractions $\rho_r = \operatorname{rank}(A_0)/m \in [0, 1]$ and error probabilities $\rho_s = \|E_0\|_0 / m^2 \in [0, 1]$ , using 10 random trials per pair and defining success by relative error $\|\hat{A} - A_0\|_F / \|A_0\|_F < 0.01$ .

The recovery boundary exhibits a sharp phase transition approximately along the linear threshold:
$\rho_r + \rho_s \approx 0.35.$
Below this boundary, convex optimization achieves exact recovery across all random trials (100% success rate), while above it, recovery uniformly fails (0% success rate). This sharp boundary confirms that exact separation holds empirically even when rank and corruption levels are both constant fractions of the dimension.
Knowl 8 — Video Background and Foreground Activity Separation via Robust PCA
empirical result
When video frames are flattened and stacked as columns of a matrix $D$ , the video decomposes into $D = A + E$ , where $A$ captures the stationary or slowly varying low-rank background and $E$ captures the spatially sparse foreground activity.

Evaluation on video sequences demonstrates that Robust PCA decomposes the content without prior training:
1. In an airport sequence (200 frames of $72 \times 88$ pixels) with heavy pedestrian movement under constant illumination, the low-rank component $\hat{A}$ reconstructs the static background while the sparse component $\hat{E}$ isolates moving people.
2. In a lobby sequence (550 frames of $64 \times 80$ pixels) with drastic lighting changes toward the end, $\hat{A}$ adapts to the illumination changes across the scene without ghosting artifacts, while $\hat{E}$ isolates foreground movements.
Knowl 9 — Illumination Invariant Face Reconstruction and Specularity Removal via Robust PCA
empirical result
Images of a Lambertian object under varying illumination span an approximately 9-dimensional linear subspace (harmonic plane). Real face images deviate from this model due to non-Lambertian effects, such as specularities in the eyes, saturations, and cast shadows around facial features.

When 31 face images ( $96 \times 84$ pixels) of an individual from subsets 1–3 of the Extended Yale B database are aligned and stacked as columns of a matrix $D$ , Robust PCA decomposes $D = A + E$ . The low-rank estimate $\hat{A}$ recovers the artifact-free Lambertian face appearance across illuminations, while the sparse error component $\hat{E}$ captures specular reflections and localized shadows.

Coverage note — The detailed mathematical proofs of Theorem 2.4 and Theorem 2.5 were omitted because they were deferred to external companion literature (Wright et al., 2009 [22]) and not detailed within the paper text.

References

1.C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.
2.S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129–159, 2001.
3.J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
4.M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.
5.I. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, New York, 1986.
6.P. Huber. Robust Statistics. Wiley, New York, New York, 1981.
7.F. De La Torre and M. Black. A framework for robust subspace learning. IJCV, 54(1-3):117–142, 2003.
8.R. Gnanadesikan and J. Kettenring. Robust estimates, residuals, and outlier detection with multiresponse data. Biometrics, 28(1):81–124, 1972.
9.Q. Ke and T. Kanade. Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming. In CVPR, 2005.
10.M. Fischler and R. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–385, 1981.
11.E. Cand`es and T. Tao. Decoding by linear programming. IEEE Trans. Info. Thy., 51(12):4203–4215, 2005.
12.B. Recht, M. Fazel, and P. Parillo. Guaranteed minimum rank solution of matrix equations via nuclear norm minimization. SIAM Review, submitted for publication.
13.E. Candes and B. Recht. Exact matrix completion via convex optimzation. Foundations of Computational Mathematics, to appear.
14.A. Montanari R. Keshavan and S. Oh. Matrix completion from a few entries. preprint, 2009.
15.E. Candes and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, submitted for publication.
16.E. Candes and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, to appear.
17.D. Donoho. High-dimensional data analysis: The curses and blessings of dimensionality. AMS Math Challenges Lecture, 2000.
18.A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Science, (1):183–202, 2009.
19.Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
20.J. Cai, E. Candes, and Z. Shen. A singular value thresholding algorithm for matrix completion. preprint, http://arxiv.org/abs/0810.3286, 2008.
21.K.-C. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. preprint, http://math.nus.edu.sg/~matys/apg.pdf, 2009.
22.J. Wright, A. Ganesh, S. Rao, and Y. Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Journal of the ACM, submitted for publication.
23.E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(2):237–260, 1998.
24.D. Donoho. For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6):797–829, 2006.
25.V. Chandrasekaran, S. Sanghavi, P. Parrilo, and A. Willsky. Sparse and low-rank matrix decompositions. In IFAC Symposium on System Identification, 2009.
26.J. Wright and Y. Ma. Dense error correction via $\ell^1$ -minimization. IEEE Transactions on Information Theory, to appear.
27.Z. Lin, A. Ganesh, J. Wright, M. Chen, L. Wu, and Y. Ma. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. SIAM Journal on Optimization, submitted for publication.
28.V. Cevher, , M. F. Duarte, C. Hegde, and R. G. Baraniuk. Sparse signal recovery using markov random fields. In NIPS, 2008.
29.L. Li, W. Huang, I. Gu, and Q. Tian. Statistical modeling of complex backgrounds for foreground object detection. IEEE Transactions on Image Processing, 13(11), 2004.
30.R. Basri and D. Jacobs. Lambertian reflection and linear subspaces. IEEE Trans. PAMI, 25(3):218–233, 2003.
31.A. Georghiades, P. Belhumeur, and D. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. PAMI, 23(6):643–660, 2001.

Citation

MLA

Wright, J., et al. “Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization”. Advances in Neural Information Processing Systems, vol. 22, 2009, https://proceedings.neurips.cc/paper_files/paper/2009/file/c45147dee729311ef5b5c3003946c48f-Paper.pdf.

APA

Wright, J., Ganesh, A., Rao, S., Peng, Y., & Ma, Y. (2009). Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization. Advances in Neural Information Processing Systems, 22. https://proceedings.neurips.cc/paper_files/paper/2009/file/c45147dee729311ef5b5c3003946c48f-Paper.pdf

Chicago

Wright, J., A. Ganesh, S. Rao, Y. Peng, and Y. Ma. 2009. “Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization”. Advances in Neural Information Processing Systems 22. https://proceedings.neurips.cc/paper_files/paper/2009/file/c45147dee729311ef5b5c3003946c48f-Paper.pdf.

Harvard

Wright, J. et al. (2009) “Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2009/file/c45147dee729311ef5b5c3003946c48f-Paper.pdf.

Vancouver

1. Wright J, Ganesh A, Rao S, Peng Y, Ma Y (2009) Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization. Advances in Neural Information Processing Systems 22:

BibTeX

@inproceedings{wright2009robust,
  title = {Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization},
  author = {Wright, John and Ganesh, Arvind and Rao, Shankar and Peng, Yigang and Ma, Yi},
  year = {2009},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {22},
  url = {https://proceedings.neurips.cc/paper_files/paper/2009/file/c45147dee729311ef5b5c3003946c48f-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

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

Open PDF

License: Published with permission

Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Exact Robust PCA Recovery Under Non-Vanishing Error Fractions

Knowl 2 — Convex Formulation of Robust Principal Component Analysis

Knowl 3 — Robust PCA via Accelerated Proximal Gradient with Continuation

Knowl 4 — Matrix Completion Under Proportional Rank Growth

Knowl 5 — Random Orthogonal Model and Bernoulli Error Sign and Support Model

Knowl 6 — Exact Recovery Performance of Robust PCA Under Proportional Dimension Scaling

Knowl 7 — Empirical Phase Transition in Rank Ratio and Error Sparsity for Robust PCA

Knowl 8 — Video Background and Foreground Activity Separation via Robust PCA

Knowl 9 — Illumination Invariant Face Reconstruction and Specularity Removal via Robust PCA

References

Citation

BibTeX

Access the Paper