pythondemos/rpca.pyDictionary of Applied Machine Learning
Updated on 2026-10-08
See also principal component analysis singular value decomposition regularization
Robust principal component analysis (robust PCA) decomposes a data matrix into the sum of a matrix of low rank and a matrix with few nonzero entries. A small number of grossly corrupted entries then lands in the second part instead of tilting the principal directions, which the squared error loss of principal component analysis (PCA) lets a single such entry do. Principal component pursuit computes the decomposition by minimizing the sum of the singular values of the first part plus a weighted sum of the absolute entries of the second. That is a convex problem whose solution is the true decomposition under conditions on the low-rank part and on the positions of the corrupted entries. The alternating direction method of multipliers (ADMM) solves it by alternating singular value thresholding and soft thresholding. Uses are the separation of a static background from moving objects in video and the detection of faulty measurements.
B-matrixThe hourly air temperature at Krems an der Donau in 2024, arranged as a matrix with one row per day and one column per hour, has $366$ rows and $24$ columns, and every row is the daily cycle on top of that day's level. Three singular values carry $99.5\%$ of its energy: the matrix is nearly of rank three. Now let $5\%$ of the entries be sensor faults, each off by $20$ to $40$ degrees. Principal component analysis (PCA) of the corrupted matrix, its best rank-three approximation by a truncated singular value decomposition (SVD), ends up $19\%$ away from the clean matrix, since the squared error loss lets the faults tilt the directions. Robust PCA decomposes the corrupted matrix into a low-rank part and a part with few nonzero entries: the first is $6\%$ away from the clean matrix, and the entries of the second at the scale of a fault are exactly the faults (Fig. 1).
Let $\mX \in \reals^{\samplesize \times \featuredim}$ be the data matrix whose rows are the feature vectors of $\samplesize$ data points. PCA finds the matrix of rank $\featuredim'$ nearest to $\mX$ in the sum of squared entries, which is the truncated SVD (Eckart and Young, 1936). A single entry of $\mX$ that is off by a large amount changes every singular vector, since the squared error grows with the square of that amount. Robust PCA assumes instead that \begin{equation} \label{equ_rpca_model_dict} \mX = \mL + \mS \text{,} \end{equation} with a matrix $\mL$ of low rank and a matrix $\mS$ with few nonzero entries of arbitrary size, and recovers both. Minimizing the rank of $\mL$ plus the number of nonzero entries of $\mS$ subject to \(\eqref{equ_rpca_model_dict}\) is intractable, and principal component pursuit replaces each count by its convex surrogate (Candès et al., 2011): \begin{equation} \label{equ_rpca_pcp_dict} \min_{\mL, \mS \in \reals^{\samplesize \times \featuredim}} \normgeneric{\mL}{*} + \regparam \normgeneric{\mS}{1} \quad \text{ subject to } \mL + \mS = \mX \text{,} \end{equation} with the nuclear norm $\normgeneric{\mL}{*}$, the sum of the singular values of $\mL$, in place of the rank, and the $\ell_{1}$ norm $\normgeneric{\mS}{1}$, the sum of the absolute entries, in place of their count, as for the least absolute shrinkage and selection operator (Lasso). Both are penalty terms, the loss-penalization route of regularization. The weight $\regparam = 1/\sqrt{\max\{\samplesize, \featuredim\}}$ needs no tuning: if the singular vectors of $\mL$ are spread over all rows and columns rather than concentrated on a few, and the nonzero entries of $\mS$ sit at positions chosen uniformly at random and are not too many, then the minimizer of \(\eqref{equ_rpca_pcp_dict}\) is the true pair $(\mL, \mS)$ with high probability (Candès et al., 2011, Thm. 1.1). On the temperature matrix the first condition fails only mildly, since the rows are not exactly of rank three, and the pursuit then assigns the small remainder of the daily curves to $\mS$ as well; the faults are still the entries of $\mS$ at their own scale.
B-pursuitThe alternating direction method of multipliers (ADMM) solves \(\eqref{equ_rpca_pcp_dict}\) by alternating two
proximal operators (Candès et al., 2011, Sect. 5): the proximal operator of
the nuclear norm, which computes an SVD and shrinks
every singular value toward zero by a threshold, and the
proximal operator of the $\ell_{1}$ norm, which shrinks every entry
toward zero by a threshold, followed by an update of the multiplier
of the constraint. Each iteration applies the same
operator to the triple of $\mL$, $\mS$ and the multiplier, so
the method is a fixed-point iteration, whose fixed points are
the saddle points of the augmented Lagrangian and therefore the
solutions of \(\eqref{equ_rpca_pcp_dict}\); the operator is
averaged, which is what guarantees convergence for a convex
problem (Boyd et al., 2011, Sect. 3.2). On the temperature
matrix the recovered $\mL$ has rank nine out of
$24$ and the pursuit takes a few thousand iterations, each an
SVD of a $366 \times 24$ matrix.
pythondemos/rpca.py
See also: principal component analysis, sparse principal component analysis, probabilistic principal component analysis, singular value decomposition, rank, alternating direction method of multipliers, proximal operator, fixed-point iteration, least absolute shrinkage and selection operator, regularization, outlier, anomaly detection, robustness, missing data.
@misc{dictml_rpca,
author = {Jung, Alexander},
editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
title = {robust principal component analysis (robust PCA)},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-10-08},
url = {https://dictionaryofml.org/terms/rpca.html}
}