Static and Dynamic Robust PCA and Matrix Completion: A Review

Abstract

Principal Components Analysis (PCA) is one of the most widely used dimension reduction techniques. Robust PCA (RPCA) refers to the problem of PCA when the data may be corrupted by outliers. Recent work by Cand{è}s, Wright, Li, and Ma defined RPCA as a problem of decomposing a given data matrix into the sum of a low-rank matrix (true data) and a sparse matrix (outliers). The column space of the low-rank matrix then gives the PCA solution. This simple definition has lead to a large amount of interesting new work on provably correct, fast, and practical solutions to RPCA. More recently, the dynamic (time-varying) version of the RPCA problem has been studied and a series of provably correct, fast, and memory efficient tracking solutions have been proposed. Dynamic RPCA (or robust subspace tracking) is the problem of tracking data lying in a (slowly) changing subspace while being robust to sparse outliers. This article provides an exhaustive review of the last decade of literature on RPCA and its dynamic counterpart (robust subspace tracking), along with describing their theoretical guarantees, discussing the pros and cons of various approaches, and providing empirical comparisons of performance and speed. A brief overview of the (low-rank) matrix completion literature is also provided (the focus is on works not discussed in other recent reviews). This refers to the problem of completing a low-rank matrix when only a subset of its entries are observed. It can be interpreted as a simpler special case of RPCA in which the indices of the outlier corrupted entries are known.

arXiv commentTo appear in Proceedings of the IEEE, Special Issue on Rethinking PCA for Modern Datasets. arXiv admin note: text overlap with arXiv:1711.09492

References in corpus (14)

• Rank-Sparsity Incoherence for Matrix Decomposition
• Recovering low-rank matrices from few coefficients in any basis
• Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support
• An overview of low-rank matrix recovery from incomplete observations
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Guaranteed Matrix Completion via Non-convex Factorization
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• An Overview of Robust Subspace Recovery
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• Low Rank Phase Retrieval
• Robust PCA with Partial Subspace Knowledge
• Video Denoising and Enhancement via Dynamic Video Layering

Cited by in corpus (6)

• An Overview of Robust Subspace Recovery
• Provable Dynamic Robust PCA or Robust Subspace Tracking
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Provable Subspace Tracking from Missing Data and Matrix Completion
• A robust principal component analysis for outlier identification in messy microcalorimeter data