Principal Component Analysis with Contaminated Data: The High Dimensional Case

Huan Xu, Constantine Caramanis, Shie Mannor

Abstract

Standard Principal Component Analysis (PCA) is highly susceptible to outliers, particularly in high-dimensional regimes where the number of features $m$ is comparable to or exceeds the number of observations $n$. This paper introduces High-dimensional Robust PCA (HR-PCA), a computationally tractable algorithm designed to maintain robustness in these challenging environments. HR-PCA achieves a breakdown point of 50%, the theoretical maximum, by employing a stochastic iterative removal process. This work demonstrates that while high dimensionality typically degrades the performance of robust estimators, HR-PCA remains stable and asymptotically optimal.

Introduction

Principal Component Analysis (PCA) serves as a foundational tool for dimensionality reduction and signal processing. By identifying the subspace that captures the maximum variance of a dataset, it allows researchers to simplify complex data while preserving essential information. However, PCA relies on a quadratic error criterion, which renders it notoriously fragile; a single outlier, if sufficiently distant from the main data cluster, can rotate the principal components away from the true signal.

In classical statistics, where $n \gg m$, various robust PCA variants have been developed. However, modern datasets—such as DNA microarrays, high-resolution video, and sensor network logs—often exist in the high-dimensional regime where $m \approx n$ or $m > n$. In these settings, traditional robust methods often fail. This paper addresses the "breakdown point collapse," where the fraction of outliers an algorithm can handle shrinks toward zero as dimensionality increases.

The High-Dimensional Challenge

High-dimensional data introduces two primary difficulties for robust estimation:

  1. Noise Accumulation: The cumulative effect of noise across thousands of dimensions can easily overwhelm the signal, making it difficult to distinguish between legitimate variance and stochastic fluctuations.
  2. Breakdown Point Sensitivity: Most robust algorithms rely on estimators that become increasingly unstable as the ratio of dimensions to samples grows.

The authors propose a solution that remains robust even when the data is contaminated by a constant fraction of arbitrarily (or even maliciously) corrupted points, regardless of the dimensionality.

The HR-PCA Framework

Instead of attempting to compute a robust covariance matrix directly—a task that is often computationally prohibitive in high dimensions—the authors propose High-dimensional Robust PCA (HR-PCA). The algorithm utilizes an iterative "PCA plus random removal" strategy:

  1. Iterative Projection: The algorithm performs standard PCA on the current dataset to identify candidate directions of high variance.
  2. Robust Variance Estimation (RVE): The data is projected onto these directions, and the variance of the "cleanest" subset of points is calculated. This helps identify which directions are likely driven by outliers.
  3. Stochastic Removal: Rather than using a deterministic threshold to delete outliers, HR-PCA employs a randomized approach. It removes data points with a probability proportional to their squared projection on the current principal components. This "secret sauce" prevents malicious outliers from being designed to evade deterministic detection.
  4. Convergence: The process repeats until the outliers are purged, and the true low-dimensional subspace is recovered.

Furthermore, the algorithm is kernelizable, allowing it to be extended to non-linear subspaces via the "kernel trick," expanding its utility to non-linear manifold learning.

Theoretical Guarantees and Insights

The paper provides several rigorous proofs regarding the performance of HR-PCA:

  • The 50% Breakdown Point: The authors prove that HR-PCA can withstand up to 50% data contamination. This is the absolute theoretical limit for any robust estimator; beyond 50%, it becomes impossible to distinguish the "true" data from the "corrupted" data.
  • The Blessing of Dimensionality: Interestingly, the authors argue that high dimensionality can be an advantage. In very high-dimensional spaces, noise and signal tend to become orthogonal. HR-PCA leverages this property to help the RVE distinguish between the underlying signal and the contamination.
  • Asymptotic Optimality: The authors demonstrate that as both the number of samples and dimensions tend toward infinity, HR-PCA recovers the exact low-dimensional subspace, provided the fraction of outliers vanishes asymptotically.

Empirical Evaluation

The algorithm was evaluated primarily using synthetic datasets designed to simulate high-dimensional stress ($n = m = 1000$). The "authentic" data consisted of a low-dimensional signal embedded in high-dimensional Gaussian noise, while "contaminated" data included outliers placed strategically to pull PCA directions away from the signal.

HR-PCA was compared against standard PCA and several robust benchmarks, including Multi-Variate iterative Trimming (MVT), ROBPCA, and Project-Pursuit (PP). The results indicated:

  • Superior Robustness: HR-PCA maintained high accuracy (expressed variance) even at 40% contamination. In contrast, the performance of ROBPCA and Project-Pursuit collapsed once contamination exceeded 10-15%.
  • Dimensionality Scaling: While the performance of existing robust methods dropped significantly as dimensions increased, HR-PCA remained stable, confirming its suitability for high-dimensional applications.

Discussion and Limitations

While HR-PCA represents a significant advancement, it is not without trade-offs. The iterative nature of the algorithm—requiring multiple passes of PCA and point removal—makes it more computationally expensive than a single-pass standard PCA. Additionally, the algorithm requires users to estimate the fraction of corrupted points ($\lambda$) and the number of iterations ($T$). While the authors provide heuristics for these parameters, real-world performance may vary based on these selections.

Future work involves validating the algorithm on real-world "dirty" data, such as sensor networks with intermittent failures or video streams with occlusions, where the outlier structure may be more complex than the synthetic models used in this study.

Summary updated

BibTeX
@inproceedings{xu2010principal,
  author = {Huan Xu and Constantine Caramanis and Shie Mannor},
  title = {{Principal Component Analysis with Contaminated Data: The High Dimensional Case}},
  booktitle = {Conference on Learning Theory},
  year = {2010},
  url = {https://openreview.net/forum?id=pzIrOt9BQ0},
}
Figure