Robust principal component analysis
Robust principal component analysis (RPCA) is a family of methods for separating a data matrix into a structured low-rank component and an unstructured component containing sparse but potentially large deviations. Its canonical formulation, known as principal component pursuit, represents an observed matrix (M\in\mathbb{R}^{m\times n}) as
[ M=L_0+S_0, ]
where (L_0) has low matrix rank and (S_0) has relatively few nonzero entries. The decomposition generalizes principal component analysis, which models data through a low-dimensional linear subspace but can be strongly altered by observations whose magnitudes are inconsistent with the assumed noise distribution.
The adjective “robust” refers to resistance against sparse gross errors rather than to uniform resistance against every departure from a statistical model. RPCA can recover a low-rank matrix when individual corrupted entries have arbitrarily large magnitude, provided that the low-rank and sparse components satisfy appropriate identifiability conditions. The same mathematical framework has influenced matrix completion, background separation in image sequences, latent-variable estimation, and the analysis of high-dimensional measurements containing localized failures.
Mathematical formulation
Directly minimizing rank and support size gives the optimization problem
[ \min_{L,S}\ \operatorname{rank}(L)+\lambda|S|_0 \quad\text{subject to}\quad M=L+S, ]
where (|S|_0) denotes the number of nonzero entries and (\lambda>0) balances the two structural assumptions. Both terms are nonconvex, and the resulting problem is computationally intractable in general.
Principal component pursuit replaces rank with the nuclear norm, defined as the sum of a matrix’s singular values, and replaces support size with the entrywise (\ell_1) norm. The resulting convex optimization problem is
[ \min_{L,S}\ |L|_*+\lambda|S|_1 \quad\text{subject to}\quad M=L+S. ]
The nuclear norm is the convex envelope of rank on the spectral-norm unit ball, while the (\ell_1) norm is the corresponding convex surrogate for sparsity under an entrywise magnitude constraint. This pairing makes the decomposition accessible to convex duality and permits exact-recovery statements under probabilistic or deterministic structural assumptions.
For an (m\times n) matrix, the conventional theoretical choice is
[ \lambda=\frac{1}{\sqrt{\max(m,n)}}. ]
This scaling places the dual norms associated with the low-rank and sparse terms on comparable asymptotic scales. It does not encode the expected magnitudes of the entries, because the exact noiseless theory permits the nonzero entries of (S_0) to have unrestricted amplitude.
Identifiability
A decomposition into low-rank and sparse matrices is not automatically unique. A matrix supported in a single row may be sparse while also having rank one. Conversely, a low-rank matrix whose singular vectors align with coordinate axes may itself be concentrated on a small collection of entries. In either case, the same observed matrix admits multiple decompositions with the required structural properties.
RPCA theory controls this ambiguity through incoherence conditions on the singular vectors of (L_0). If
[ L_0=U\Sigma V^\mathsf{T} ]
is a compact singular value decomposition of rank (r), standard incoherence assumptions bound the concentration of the columns of (U) and (V) in the coordinate basis. A representative form is
[ \max_i |U^\mathsf{T}e_i|_2^2 \leq \frac{\mu r}{m}, \qquad \max_j |V^\mathsf{T}e_j|_2^2 \leq \frac{\mu r}{n}, ]
together with a bound on the maximum entry of (UV^\mathsf{T}). The parameter (\mu) quantifies the degree to which the low-rank subspaces avoid coordinate concentration.
The sparse component requires a complementary restriction on its support. In the standard probabilistic model, the locations of its nonzero entries are sampled approximately uniformly, while their signs satisfy an independence condition in several versions of the theorem. These assumptions prevent the sparse component from reproducing a substantial low-rank pattern. Deterministic variants instead express recovery in terms of the interaction between the support subspace and the tangent space of the low-rank matrix variety.
Let
[ T={UX^\mathsf{T}+YV^\mathsf{T}:X\in\mathbb{R}^{n\times r}, Y\in\mathbb{R}^{m\times r}} ]
denote the tangent space at (L_0), and let (\Omega) denote the linear space of matrices supported on the nonzero pattern of (S_0). A basic identifiability requirement is
[ T\cap\Omega={0}. ]
Quantitative recovery arguments strengthen this condition by bounding the operator norm of compositions of the corresponding orthogonal projections. This geometric interpretation places RPCA within the broader theory of low-rank matrix recovery and compressed sensing.
Exact and stable recovery
Under suitable incoherence and sparsity assumptions, principal component pursuit has ((L_0,S_0)) as its unique optimum with probability approaching one as the matrix dimensions increase. Representative theorems permit the rank to grow nearly linearly with the smaller matrix dimension, subject to logarithmic factors and dependence on the incoherence parameter. They also permit a nonvanishing fraction of matrix entries to be corrupted when the support follows the required random model.
The proof strategy constructs a dual certificate satisfying the optimality conditions for both norm terms. The certificate must agree with (UV^\mathsf{T}) on the low-rank tangent space while matching the sign pattern of (S_0) on the corruption support. Its remaining components must lie strictly inside the dual-norm unit balls. Random projection estimates and matrix concentration inequalities control the interactions among these spaces.
The modern convex formulation and its recovery theory were developed by Emmanuel Candès, Xiaodong Li, Yi Ma, John Wright, and You Watanabe during the late 2000s and early 2010s. Their analysis connected sparse error correction with nuclear-norm minimization and established conditions under which both components are recovered without prior knowledge of their rank or support. The resulting framework distinguished entrywise corruption from the smaller dense perturbations treated by classical statistical noise models.
When observations contain an additional dense error term,
[ M=L_0+S_0+N, \qquad |N|_F\leq\delta, ]
the equality constraint is replaced by a fidelity constraint:
[ \min_{L,S}\ |L|_*+\lambda|S|_1 \quad\text{subject to}\quad |M-L-S|_F\leq\delta. ]
This formulation is commonly called stable principal component pursuit. Under assumptions related to those of the exact theory, the estimation error is bounded in proportion to the dense-noise level. Exact entrywise recovery is generally unavailable in this setting because the dense perturbation cannot be uniquely assigned to either component.
Computation
Principal component pursuit has a separable objective coupled by a linear equality constraint. This structure supports methods based on the augmented Lagrangian, operator splitting, and proximal algorithms. The proximal map of the entrywise (\ell_1) norm is soft thresholding, while the proximal map of the nuclear norm applies the same scalar operation to singular values.
For a threshold (\tau), entrywise soft thresholding is defined by
[ \mathcal{S}_{\tau}(x)
\operatorname{sgn}(x)\max(|x|-\tau,0). ]
If (X=U\Sigma V^\mathsf{T}), singular-value thresholding takes the form
[ \mathcal{D}_{\tau}(X)
U\mathcal{S}_{\tau}(\Sigma)V^\mathsf{T}. ]
Alternating applications of these maps arise naturally from the optimality conditions of the penalized or augmented problem. The principal computational expense is normally the repeated evaluation of a full or partial singular value decomposition. Implementations therefore exploit truncated decompositions when the current low-rank estimate has substantially smaller rank than the ambient matrix dimensions.
Zhouchen Lin, Minming Chen, and Yi Ma developed an inexact augmented-Lagrange multiplier method that became a standard computational realization of principal component pursuit. Related analyses by Zihan Zhou, Xiaodong Li, John Wright, Emmanuel Candès, and Yi Ma treated stable recovery and constrained variants. These algorithmic developments linked the statistical decomposition to established convergence results for the alternating direction method of multipliers.
Statistical interpretation
Classical PCA may be derived from a model in which residual entries follow an isotropic Gaussian distribution. Under that model, minimizing squared reconstruction error produces the leading singular subspace of the data matrix. Sparse gross errors do not follow this residual structure, because a small number of entries can dominate the squared loss and rotate the estimated subspace.
RPCA instead separates two distinct forms of variation. The low-rank term represents dependence shared across many rows or columns, whereas the sparse term represents deviations concentrated at particular coordinates. This distinction concerns the geometry of the matrix rather than the marginal distribution of each observation. Consequently, RPCA is not equivalent to replacing squared loss with an entrywise robust loss, although certain penalized formulations yield related estimators after one variable is eliminated.
The sparse component is also distinct from a general collection of anomalous samples. Principal component pursuit assumes sparsity at the level of individual entries. When corruption affects entire columns, the appropriate model uses a column-sparsity penalty such as
[ |C|{2,1}=\sum_j|C{:j}|_2, ]
leading to the formulation commonly called Outlier Pursuit. Its identifiability conditions differ because a corrupted column may occupy every coordinate within that sample.
Scope and limitations
The basic model assumes that the principal structure is well approximated by a single linear subspace. Data concentrated near a curved manifold may not produce a globally low-rank matrix, even when their intrinsic dimension is small. Local subspace models and nonlinear dimensionality-reduction methods address a different geometric assumption.
Recovery guarantees also depend on separation between low rank and sparsity. A sparse component organized into a low-rank pattern remains intrinsically ambiguous, while a low-rank component concentrated on a few entries is indistinguishable from sparse corruption. No optimization method can resolve such cases without adding information beyond the observed matrix.
The convex formulation reduces model selection but does not remove it entirely. Stable variants require a scale for dense noise, and applications with structured corruption require a norm matching that structure. Missing observations introduce an additional sampling operator, producing a problem that combines RPCA with matrix completion rather than the fully observed decomposition considered by principal component pursuit.