PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery

Namrata Vaswani, Thierry Bouwmans, Sajid Javed, Praneeth Narayanamurthy

arXiv:1711.09492v4cs.ITcs.CVstat.MEstat.ML

TL;DR

The paper surveys robust subspace learning when outliers corrupt PCA data or when the underlying subspace changes over time. It organizes solutions around S+LR-based RPCA and RST, alongside RSR for whole-vector outliers, and compares their guarantees, assumptions, and practical performance. The survey highlights ReProCS as especially strong among provable methods in video applications, while identifying missing correctness and evaluation results for dynamic undersampled robust PCA.

  • Problem

    Robust subspace learning must estimate low-dimensional structure despite outliers, while long sequences may require tracking a gradually changing subspace and whole-vector corruption motivates robust subspace recovery.

  • Method

    The article provides a magazine-style overview of RPCA and RST through sparse+low-rank decomposition, plus RSR for data vectors that are either inliers or outliers.

  • Results

    ReProCS has the best practical performance among provable video foreground-background methods and is among the fastest, while its guarantees provide strong outlier tolerance under additional assumptions.

  • Takeaways & Limitations

    Choosing between static RPCA and dynamic tracking depends on the temporal setting: dynamic models better fit long static-camera videos, whereas sudden scene changes favor static RPCA.

  • Takeaways & Limitations

    Dynamic extensions of undersampled robust PCA have received little attention: complete correctness results and careful real-dataset evaluations for dynamic MRI are still missing.

Abstract

from arXiv · show

PCA is one of the most widely used dimension reduction techniques. A related easier problem is "subspace learning" or "subspace estimation". Given relatively clean data, both are easily solved via singular value decomposition (SVD). The problem of subspace learning or PCA in the presence of outliers is called robust subspace learning or robust PCA (RPCA). For long data sequences, if one tries to use a single lower dimensional subspace to represent the data, the required subspace dimension may end up being quite large. For such data, a better model is to assume that it lies in a low-dimensional subspace that can change over time, albeit gradually. The problem of tracking such data (and the subspaces) while being robust to outliers is called robust subspace tracking (RST). This article provides a magazine-style overview of the entire field of robust subspace learning and tracking. In particular solutions for three problems are discussed in detail: RPCA via sparse+low-rank matrix decomposition (S+LR), RST via S+LR, and "robust subspace recovery (RSR)". RSR assumes that an entire data vector is either an outlier or an inlier. The S+LR formulation instead assumes that outliers occur on only a few data vector indices and hence are well modeled as sparse corruptions.

I. INTRODUCTION

The article frames robust subspace learning around recovering principal subspaces when data contain outliers, and distinguishes static RPCA, dynamic tracking, and robust subspace recovery by their corruption models.

  • PCA finds orthogonal basis vectors spanning the directions of most dataset variability, with the principal subspace often being the main object of interest.
  • Outlier-corrupted PCA is called robust PCA or robust subspace learning, with failures arising from sensor faults, foreground occlusions, or anomalous network behavior.
  • The S+LR formulation decomposes M into low-rank true data L and sparse outliers S, whose column subspace gives the principal components.
  • For long sequences, subspace tracking models data in a low-dimensional subspace that changes gradually over time, rather than forcing one fixed subspace.
  • Robust subspace recovery treats each entire data vector as either an inlier or an outlier, unlike S+LR's sparse corruptions within data vectors.
  • Applications include video layering, dynamic MRI, network anomaly detection, and survey analysis by representing slowly varying structure as low rank and localized changes as sparse.

B. Desirable algorithm properties

The article evaluates robust subspace algorithms through correctness, practical accuracy, computational cost, memory use, and online operation, while distinguishing complete from partial guarantees.

  • A complete correctness guarantee assumes only inputs and algorithm parameters, then proves the output is within small error of the true quantity.
  • Partial guarantees may rely on intermediate estimates or establish only convergence to a stationary point or local minimum, so they are usually less useful alone.
  • Practical accuracy is assessed using normalized recovery error, column-span error, or outlier-support recovery error, depending on the quantity of interest.
  • Time complexity should include both order-wise analysis and measured runtime because asymptotic complexity can hide large practical constants.
  • Memory complexity and number of passes matter for large datasets, with memory-optimal RPCA requiring O(nr) memory.
  • Online algorithms process arriving data sequentially, make decisions with small delays, and improve output quality as more data arrives.

1) Static RPCA [4]:

Static RPCA and robust subspace tracking model observations as low-rank data plus sparse outliers and noise, but identifiability requires assumptions separating these structures.

  • The static S+LR model represents observations using low-rank L, sparse outliers S, and small unstructured noise W, estimating L and its column space.
  • RST observes m_t = ℓ_t + s_t + w_t, where ℓ_t lies in a fixed or slowly changing low-dimensional subspace and sparse outliers are tracked over time.
  • Dynamic RPCA is the offline counterpart of tracking, seeking recovery of the matrix L and its column space with bounded error.
  • Identifiability fails when L is also sufficiently sparse or S is also sufficiently low rank, so the two components cannot be uniquely separated.
  • RST can use piecewise-constant subspaces lasting more than r samples to reduce the number of unknown parameters and make tracking identifiable.
  • Correctness analyses require incoherence or equivalent dense-factor assumptions together with bounds on row and column outlier fractions.

B. Static Robust PCA (RPCA): a summary

Static RPCA separates data into low-rank and sparse components, with provable methods including PCP, AltProj, and faster gradient-based approaches. ReProCS-NORST extends the framework online to track changing subspaces while detecting changes and tolerating outliers under explicit assumptions.

  • Static RPCA methods: PCP introduced a provably correct polynomial-time convex solution for static RPCA, while AltProj achieved lower time complexity under the same assumptions.AltProj uses alternating minimization rather than a convex-program solver.
  • Static RPCA methods: AltProj returns low-rank and sparse estimates with bounded recovery errors when incoherence, outlier-fraction, noise, and parameter conditions hold.The guarantee bounds the Frobenius error of the low-rank estimate and the maximum error of the sparse estimate.
  • Static RPCA methods: RPCA-GD has complexity O(ndrL log(1/ϵ)), comparable to vanilla r-SVD, but requires outlier-fraction bounds √rL times tighter.ReProCS-NORST has the same stated time complexity as RPCA-GD.
  • Robust subspace tracking: ReProCS-NORST is an online RST method that outputs subspace, low-rank, and sparse estimates while detecting subspace-change times.It is designed as a nearly optimal tracking-delay solution.
  • Robust subspace tracking: ReProCS-NORST detects changes with delay only slightly above r and tolerates a constant maximum outlier fraction per row after initialization under slow-change and minimum-magnitude assumptions.The method is also described as nearly memory-optimal and able to handle slowly moving or occasionally static objects better than approaches with tighter row-fraction requirements.

D. Dynamic versus Static RPCA

Dynamic and static RPCA model different subspace behavior, but both can be useful when data arrive in natural sequences. Robust subspace recovery instead treats whole vectors as either inliers or outliers and has guarantees that depend strongly on the outlier fraction.

  • Dynamic versus static RPCA: Dynamic RPCA assumes a time-varying subspace with slow changes, whereas static RPCA uses a single subspace.For long static-camera videos, the dynamic model is generally described as better suited.
  • Dynamic versus static RPCA: For growing recommendation or survey datasets, static RPCA can initialize the solution and RST can update it as users arrive and detect subspace changes.A subspace change may correspond to a newly represented demographic.
  • Robust subspace recovery: Robust subspace recovery asks for the low-dimensional subspace of inliers when each entire data vector is either an inlier or an outlier.The setting assumes the outlier fraction is below 50%.
  • Robust subspace recovery: Outlier pursuit correctly recovers the inlier column space and outlier support when the outlier fraction γ is in O(1/r) and the low-rank matrix is column-incoherent.This provides a simple correctness guarantee for RSR.
  • Robust subspace recovery: The outlier-pursuit guarantee requires a tight outlier-fraction bound, while many other RSR guarantees establish only asymptotic convergence or lower-bound a performance metric.The passage explicitly compares this limitation with the S+LR literature.

III. ROBUST PCA AND SUBSPACE TRACKING VIA SPARSE + LOW-RANK MATRIX DECOMPOSITION (S+LR)

S+LR methods rely on separating a low-rank component from sparse corruptions, but this separation is not identifiable without assumptions that keep the two components sufficiently distinct. Incoherence and outlier-support restrictions provide such conditions, while fixed sparse foregrounds illustrate failure cases.

  • Identifiability: S+LR does not ensure identifiability when the low-rank component is also sufficiently sparse or the sparse component is also sufficiently low rank.Separation can fail when the sparse component has rank no larger than the low-rank component or the low-rank support is no larger than the sparse support.
  • Identifiability: A foreground object with unchanging support and intensities can produce a rank-one sparse corruption, making its separation from the low-rank background impossible without extra assumptions.This is a concrete video example of non-identifiability.
  • Identifiability: Sparse singular vectors can make the low-rank matrix row-sparse, column-sparse, or generally sparse, potentially making it sparser than the corruption and therefore unidentifiable.The issue may arise from sparse left singular vectors, right singular vectors, or both.
  • Identifiability: Outlier fractions bounded by c/rL per row and column, or uniformly generated support with a size bound, can prevent the sparse component from becoming lower rank than the low-rank component.These are alternative assumptions for controlling the corruption structure.
  • Incoherence: Dense or incoherent left and right singular vectors help ensure that the low-rank component is sufficiently different from the sparse component.Incoherence is described as limiting the normalized inner product between the two matrices.
  • Incoherence: RPCA guarantees require both left and right incoherence, while strong incoherence additionally bounds inner products between rows of the left and right singular-vector matrices.The stronger condition is described as tighter than what separate left and right incoherence imply.

B. Older RPCA solutions: Robust Subspace Learning (RSL)

Older RPCA solutions progressed from practical heuristics toward provably correct convex and non-convex methods that separate sparse corruptions from low-rank structure. Later approaches sought faster computation, online operation, or reduced stages, but some speedups impose restrictive data-shape or sampling assumptions.

  • Robust Subspace Learning (RSL) remains a strong practical heuristic, whereas online heuristics failed across the reported simulated and real-data experiments.The cited comparison distinguishes RSL from incremental online heuristics.
  • Principal Component Pursuit (PCP) minimizes nuclear and l1 norms to obtain the first known polynomial-time RPCA solution that is also provably correct.The nuclear norm surrogates matrix rank, while the l1 norm surrogates sparse support size.
  • AltProj alternates projections onto sparse and progressively higher-rank matrix spaces, improving sparse and low-rank estimates through staged residual updates.It begins with hard thresholding, then alternates sparse thresholding and low-rank projection across r stages.
  • AltProj has time complexity O(ndr^2 log(1/ϵ)) and memory complexity O(nd), while PCP typically requires O(nd^2/ϵ) time.These complexities reflect full-matrix processing and iterative convex optimization.
  • RPCA-GD targets near-single-r-SVD complexity, while NO-RMC reduces stages and deliberately undersamples the matrix but requires d to be of the same order as n.NO-RMC exploits observed-entry structure for speed, creating a stringent requirement for high-dimensional video data.

F. Non-convex online solution for RST and RPCA: Recursive Projected Compressive Sensing (ReProCS)

ReProCS solves robust subspace tracking by estimating sparse outliers through projected compressed sensing and updating the subspace from recovered low-rank estimates. Its repeated SVD updates progressively reduce error, yielding a fast, memory-efficient, highly robust online framework under slow-change and related assumptions.

  • ReProCS-NORST: ReProCS-NORST initializes the subspace with AltProj, then estimates sparse outliers by projected compressed sensing before recovering the low-rank component.Projection onto the previous subspace’s orthogonal complement largely removes the low-rank signal, leaving a noisy sparse-recovery problem.
  • Subspace Update: Subspace updates detect changes and use K successive r-SVD steps on new α-frame blocks to obtain progressively improved estimates.The algorithm updates every α frames and computes the top r left singular vectors of the recovered low-rank data block.
  • Why it works: The projected-CS noise is proportional to current subspace error, and sparse-support recovery enables accurate low-rank estimates for the subsequent PCA step.The recovered outlier error satisfies ∥e_t∥ ≤ C∥b_t∥, linking subspace accuracy to the quality of sparse recovery.
  • Why it works: (√c2)^K times (∆ + ϵ) is the K-th changed-subspace error, becoming ϵ-accurate when K = C log(1/ϵ).Each update contracts the preceding error by √c2 under the stated bound on c2.
  • Guarantees and complexity: ReProCS-NORST uses O(nr log n) online memory and O(ndr log(1/ϵ)) computation, while tolerating larger outlier fractions under extra slow-change and magnitude assumptions.Its computation matches the time needed for an r-SVD of an n × d matrix with a good eigen-gap.

1) Looser bound on max-outlier-frac-row and outlier magnitudes’ lower bound:

ReProCS’s stronger outlier tolerance depends on extra assumptions, including dense low-rank data and sufficiently large outliers, although the magnitude requirement can be relaxed for most outliers. The analysis also notes an exploitable low-rank structure in projected noise.

  • ReProCS tolerates a constant maximum outlier fraction per row by recovering sparse outliers first and using dense low-rank subspace estimates.The approach also exploits accurate knowledge of the low-rank subspace.
  • Most outlier magnitudes need not satisfy the original lower bound if small and large components obey the stated interval-specific norm and entrywise conditions.The sufficient split is s_t = (s_t)_small + (s_t)_large, with the small component shrinking across update intervals.
  • The projected-noise vectors form an approximately rank-r matrix, suggesting modified-PCP methods could exploit structure that the basic analysis does not use.If element-wise CS error bounds were available, the required conditions could be relaxed further.

2) Relating Projected CS and Robust Regression:

Projected compressive sensing is equivalent to robust regression with sparse outliers, and approximate robust regression is appropriate when the previous subspace estimate is imperfect. The section compares modified-PCP and ReProCS in assumptions, complexity, and empirical performance.

  • Relating Projected CS and Robust Regression: Projected CS solves robust regression by modeling outliers as sparse corruptions after projection onto the estimated subspace complement.The approximate formulation accounts for error in the previous subspace estimate.
  • Relating Projected CS and Robust Regression: Modified-PCP exploits partial subspace knowledge by penalizing the residual low-rank component and sparse corruption subject to exact or approximate reconstruction.For tracking, the previous α frames provide the current partial subspace estimate, initialized using PCP.
  • Assumptions and Guarantees: Modified-PCP requires uniformly random outlier supports but does not require a lower bound on outlier magnitudes.Its guarantee uses a weaker strong-incoherence condition when the newly varying rank is much smaller than the total rank.
  • Assumptions and Guarantees: ReProCS has the best outlier-fraction tolerance among the compared methods under fixed or slow subspace change and additional outlier-magnitude assumptions.After the first Cr frames, its row tolerance is O(1) and column tolerance is O(1/r), while its online memory and delay are near-optimal.
  • Complexity: NO-RMC reaches time complexity O(nrL^2) up to logarithmic factors, but requires nearly square data and incurs additional undersampling cost.Generating Bernoulli support alone can cost O(nd).
  • Practical Performance: ReProCS has the best practical performance among provable methods for video foreground-background separation and is among the fastest.Modified-PCP and ReProCS are the fastest in MATLAB experiments; the other methods are at least three times slower.

I. Other online heuristics for RPCA and dynamic RPCA (robust subspace tracking)

The review surveys online and dynamic RPCA heuristics that extend, approximate, or reinterpret robust regression and subspace-update frameworks. It also emphasizes that application-specific constraints can substantially improve performance when valid.

  • Other online heuristics: After ReProCS, many online RPCA algorithms were proposed, but none came with complete guarantees.The review distinguishes these methods from provably correct approaches.
  • Other online heuristics: ORPCA uses stochastic optimization to solve a factorized PCP formulation but has only a partial guarantee requiring each output subspace estimate to be full rank.The factorization represents the nuclear norm through Frobenius-norm penalties on two factors.
  • Other online heuristics: APSM identifies outlier-containing time instants and uses CoSAMP to estimate the sparse outlier vector.At each time, it seeks a point in the intersection of solution sets associated with incoming data.
  • Other online heuristics: GRASTA alternates robust regression and subspace updates using approximate versions of the ReProCS framework.It solves exact l1 robust regression and can interpret subspace-tracking error as an outlier during significant subspace changes.
  • Other online heuristics: pROST and ROSETA modify GRASTA’s framework by replacing l1 recovery or changing the coefficient, outlier, and subspace-update procedures.pROST uses nonconvex lp surrogates, while ROSETA uses ADMM and proximal-point updates.
  • Application-specific approaches: Application-specific constraints can significantly improve RPCA performance when they are valid, motivating methods such as incPCP and modified-ReProCS.Modified-ReProCS exploits slowly changing foreground support through modified-CS.

A. History

Robust PCA developed from robust covariance and neural-network approaches toward formulations that model sparse corruptions, outlier points, and robust subspace objectives. The review organizes these methods alongside comparisons of assumptions, guarantees, and complexity.

  • History: Early statistical approaches replaced the covariance matrix with a robust covariance estimator before computing eigenvalues and eigenvectors.These methods were more robust but limited to relatively low-dimensional data.
  • History: Table I compares RPCA assumptions, time complexity, and memory complexity while omitting incoherence because every listed algorithm requires it.The comparison ignores dependence on condition numbers.
  • History: Table II compares RPCA and RST methods with and without guarantees in chronological order.The review separately notes that some algorithms have partial or no guarantees.
  • History: Early neural-network work incorporated outliers through binary decision fields that marked samples as outliers.The approach generalized PCA’s energy function using self-organizing rules.
  • Robust subspace recovery: Robust subspace recovery treats whole data vectors as inliers or outliers and can be reformulated using a column-sparse corruption matrix.Outlier pursuit applies an extension of PCP, with the l2,1 norm promoting column group sparsity.
  • Robust PCA methods: MDR approximates the robust first principal component by maximizing the l1 norm of projected data, while HR-PCA alternates PCA with random removal.HR-PCA’s guarantee gives positive expressed variance below 50% outliers and asymptotically approaches one as the outlier fraction vanishes with n.

E. Solutions for “Robust Subspace Recovery”

Robust subspace recovery estimates an underlying subspace from inlier and outlier points using robust M-estimation and convex relaxations. The reviewed methods include batch and stochastic algorithms, with practical evaluations conducted on RPCA and RST approaches.

  • Robust subspace recovery: Robust subspace recovery seeks the underlying subspace P from data containing inlier and outlier points using a robust M-estimator.The optimization is non-convex because it minimizes over matrices with orthonormal columns.
  • REAPER: REAPER uses a tighter convex relaxation and estimates P as the top r eigenvectors of the resulting matrix.Its constraint set is described as the convex hull of basis matrices.
  • Scalability: Batch GMS and REAPER do not scale to big data because their algorithms operate in the batch setting.Three stochastic approximation algorithms combine these methods with SGD to reduce running-time and space requirements.
  • Online robust PCA: Feng et al.’s online PCA algorithm uses probabilistic admission or rejection and tolerates anything less than 50% corruption under an asymptotic guarantee.The guarantee depends on an initialization assumption that is not specified.
  • Evaluation: The evaluation uses authors’ final parameter settings on the CDnet 2012 dataset without extra tuning.Reported metrics include recovery accuracy and support-recovery error, alongside memory and time complexity.

B. Experimental Comparisons for Video Layering (foreground-background separation)

The study compares RPCA-based foreground-background separation methods on CDnet sequences spanning six video categories, using qualitative visual results and ground-truth-based F1 evaluation. Performance varies with scene dynamics, outlier fractions, and application-specific constraints.

  • Dataset and methods: The evaluation compares 26 existing RPCA-based methods on CDnet 2012, including batch and online approaches across six video categories.The reported categories are Baseline, Dynamic Backgrounds, Intermittent Object Motion, Thermal, Camera Jitter, and Shadows.
  • Evaluation measures: The quantitative validation uses true positives, true negatives, false positives, and false negatives to compute recall, precision, and F1 measure.The study also reports computational time for the compared methods.
  • Overall performance: 74–78% F1 scores were achieved on average by PRMF, 2PRPCA, and simple-ReProCS among methods without extra constraints.MSCL and GOSUS achieved 83% and 81%, respectively, among methods using extra constraints.
  • Category-specific findings: Dynamic Backgrounds challenged mounted-camera detection because rippling water and swaying bushes produced dynamic background motion.ReProCS, 3TD, 2PRPCA, PRMF, and several constrained methods produced better foreground quality than the other compared methods in this category.
  • Qualitative comparison: Figure 5 presents qualitative comparisons for 15 CDnet sequences, with input images, ground truth, and outputs from the compared RPCA-based methods.The sequences cover Baseline, Dynamic Backgrounds, Camera Jitter, Intermittent Object Motion, Shadows, and Thermal categories.
  • Category-specific findings: ReProCS achieved a 70% F1 score in Intermittent Object Motion, where motionless foreground objects create large outlier fractions per row.Only SRPCA and MSCL performed better among methods without the same limitations, using motion detection heuristics and spatiotemporal regularization.

C. Comparison with non-RPCA methods

The article compares RPCA methods with selected top-performing unsupervised non-RPCA methods and identifies unresolved extensions of robust and dynamic robust PCA. These include moving-camera compensation, sudden subspace changes, streaming multidimensional RPCA, and broader problem settings.

  • Comparison scope: The comparison excludes supervised deep-learning methods and re-tests three top-performing unsupervised methods: SuBSENSE, PAWCS, and LOBSTER.The methods were selected using publicly available source code for a fair comparison.
  • Method differences: SuBSENSE, PAWCS, and LOBSTER use more color and texture features and additional cues for shadows or sudden illumination changes.These design choices are identified as reasons for both their accuracy and slower speed relative to RPCA methods.
  • Open theoretical and empirical questions: Dynamic extensions of robust matrix completion and undersampled robust PCA remain important open questions, with no complete correctness result for the undersampled case.Careful evaluations on real dynamic MRI datasets are also missing.
  • Practical challenges: For moving-camera video, motion compensation is needed before the data can be modeled accurately as sparse plus low-rank, but no simple provably correct useful approach exists.Sudden subspace changes can cause complete loss of track and misclassification of the low-rank component as outlier.
  • Practical challenges: A streaming multidimensional RPCA solution requiring one pass and memory for only the output subspace remains an open question.The cited streaming RPCA preprint handles only one-dimensional RPCA, whereas ReProCS requires more than one pass.
  • Review scope: The review does not cover deep-learning RPCA, robust or dynamic robust PCA for tensor data, or several other active research areas.It also identifies adaptation to more general problems such as subspace clustering and phaseless robust PCA as open questions.
Loading 1711.09492v4…