Robust principal component analysis

Robust Principal Component Analysis (RPCA) is a modification of the widely used statistical procedure of principal component analysis (PCA) which works well with respect to "grossly" corrupted observations. A number of different approaches exist for Robust PCA, including an idealized version of Robust PCA, which aims to recover a low-rank matrix L0 from highly corrupted measurements M = L0 +S0. This decomposition in low-rank and sparse matrices can be achieved by techniques such as Principal Component Pursuit method (PCP), Stable PCP, Quantized PCP, Block based PCP, and Local PCP. Then, optimization methods are used such as the Augmented Lagrange Multiplier Method (ALM), Alternating Direction Method (ADM), Fast Alternating Minimization (FAM), Iteratively Reweighted Least Squares (IRLS ) 
or alternating projections (AP).
Algorithms.
Non-convex method.
The state-of-the-art guaranteed algorithm for the robust PCA problem (with the input matrix being formula_1) is an alternating minimization type algorithm. The computational complexity is formula_2 where the input is the superposition of a low-rank (of rank formula_3) and a sparse matrix of dimension formula_4 and formula_5 is the desired accuracy of the recovered solution, i.e., formula_6 where formula_7 is the true low-rank component and formula_8 is the estimated or recovered low-rank component. Intuitively, this algorithm performs projections of the residual on to the set of low-rank matrices (via the SVD operation) and sparse matrices (via entry-wise hard thresholding) in an alternating manner - that is, low-rank projection of the difference the input matrix and the sparse matrix obtained at a given iteration followed by sparse projection of the difference of the input matrix and the low-rank matrix obtained in the previous step, and iterating the two steps until convergence.
This alternating projections algorithm is later improved by an accelerated version, coined AccAltProj. The acceleration is achieved by applying a tangent space projection before project the residue onto the set of low-rank matrices. This trick improves the computational complexity to formula_9 with a much smaller constant in front while it maintains the theoretically guaranteed linear convergence.
Another fast version of accelerated alternating projections algorithm is IRCUR. It uses the structure of CUR decomposition in alternating projections framework to dramatically reduces the compuational complexity of RPCA to formula_10
Convex relaxation.
This method consists of relaxing the rank constraint formula_11 in the optimization problem to the nuclear norm formula_12 and the sparsity constraint formula_13 to formula_14-norm formula_15. The resulting program can be solved using methods such as the method of Augmented Lagrange Multipliers.
Applications.
RPCA has many real life important applications particularly when the data under study can naturally be modeled as a low-rank plus a sparse contribution. Following examples are inspired by contemporary challenges in computer science, and depending on the applications, either the low-rank component or the sparse component could be the object of interest:
Video surveillance.
Given a sequence of surveillance video frames, it is often required to identify the activities that stand out from the background. If we stack the video frames as columns of a matrix M, then the low-rank component L0 naturally corresponds to the stationary background and the sparse component S0 captures the moving objects in the foreground.
Face recognition.
Images of a convex, Lambertian surface under varying illuminations span a low-dimensional subspace. This is one of the reasons for effectiveness of low-dimensional models for imagery data. In particular, it is easy to approximate images of a human's face by a low-dimensional subspace. To be able to correctly retrieve this subspace is crucial in many applications such as face recognition and alignment. It turns out that RPCA can be applied successfully to this problem to exactly recover the face.
Resources and libraries.
Libraries.
The LRS Library (developed by Andrews Sobral) provides a collection of low-rank and sparse decomposition algorithms in MATLAB. The library was designed for moving object detection in videos, but it can be also used for other computer vision / machine learning tasks. Currently the LRSLibrary offers more than 100 algorithms based on "matrix" and "tensor" methods.