Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing

Arun Jambulapati, Jerry Li, Kevin Tian

Introduction

Principal Component Analysis (PCA) is a foundational tool in data science, widely used to identify the primary directions of variation within high-dimensional datasets. However, standard PCA is notoriously fragile: a single adversarial outlier can completely skew the resulting principal components. The field of robust statistics aims to design algorithms capable of recovering true data distributions even when an $\epsilon$ fraction of the data is controlled by a malicious adversary.

While robust PCA algorithms for Gaussian data are well-established, real-world data often follows broader "sub-Gaussian" distributions—where tails decay at least as fast as a Gaussian, but lack strict Gaussian structure. Until now, robustly estimating the top eigenvector of sub-Gaussian data in polynomial time required assuming the data possessed "certifiable higher moments." This is a restrictive technical condition that many practical distributions fail to satisfy.

This paper eliminates that requirement, presenting the first polynomial-time algorithms for robust PCA on sub-Gaussian distributions that rely solely on basic concentration of measure. To achieve this, the authors also develop a powerful new optimization tool: the first "width-independent" solver for Schatten-$p$ norm packing semidefinite programs (SDPs).

Algorithmic Innovations

The authors tackle the robust PCA problem through two distinct algorithmic approaches, balancing statistical optimality with computational efficiency.

1. Iterative Filtering (PCAFilter)

The first approach is a polynomial-time algorithm based on iterative filtering. The algorithm maintains a weighted covariance matrix and repeatedly calculates its top eigenvector. It then employs a specialized 1D robust variance estimator to evaluate whether the variance in that specific direction exceeds what a true sub-Gaussian distribution should allow. If the variance is suspiciously high, the algorithm identifies the responsible outlier samples, downweights or prunes them, and repeats the process.

2. Robust PCA via Schatten Packing

The second approach achieves nearly-linear runtime by leveraging a novel optimization framework. Standard robust PCA methods often rely on the spectral norm ($L_\infty$ norm) to detect outliers. However, an adversary can easily "fool" this metric by concentrating their corruption into a single, massive fake top eigenvector.

To counter this, the authors shift to the Schatten-$p$ norm, which evaluates the $p$-th power of all eigenvalues. This creates a "smoother" objective function that forces the adversary to spread their corruption across many dimensions to remain effective, making the outliers significantly easier to detect and mitigate. The algorithm optimizes this using a mirror descent framework equipped with a specialized potential function tailored to the geometry of Schatten norms.

The Optimization Breakthrough: Width-Independence

A core technical contribution of this work is the Width-Independent Schatten-$p$ Packing Solver. In optimization literature, "width" refers to the maximum scale or range of values in the input data. Traditional solvers for packing SDPs have runtimes that scale linearly with this width, causing performance to degrade unacceptably on large-scale, high-dimensional datasets.

The authors' new solver breaks this barrier, achieving a runtime that scales only logarithmically with the width. This makes the solver highly practical for massive datasets and serves as the engine for their nearly-linear time robust PCA algorithm.

Key Theoretical Results

As a purely theoretical paper, the contributions are grounded in mathematical proofs of correctness, sample complexity, and runtime bounds:

  • Sample-Optimal Filtering: The PCAFilter algorithm achieves an approximation error of $O(\epsilon \log \epsilon^{-1})$ in polynomial time. This is theoretically "sample-optimal," meaning it requires the minimum possible amount of data to reach this level of accuracy.
  • Nearly-Linear Time PCA: The Schatten packing-based algorithm achieves a slightly higher error bound of $O(\sqrt{\epsilon \log \epsilon^{-1} \log d})$, but operates in nearly-linear time (e.g., $O(nd^{1.5})$ or better) under a mild assumption about the "spectral gap" (the distance between the top eigenvalues).
  • Solver Efficiency: The Schatten-$p$ packing solver delivers a $(1+\epsilon)$-approximate solution in just $O(p \log(nd/\epsilon) \epsilon^{-1})$ iterations, with each iteration running in input-sparsity time.

Limitations and Future Directions

While these results represent a significant leap forward in robust statistics, the authors note a few theoretical limitations. The nearly-linear time algorithm relies on a spectral gap dependency; if the top eigenvalues of the true covariance matrix are extremely close together, the problem becomes computationally harder. Additionally, for mathematical simplicity, the current proofs for the Schatten solver assume $p$ is an odd integer, though the authors suspect the framework generalizes.

Looking forward, the authors suggest that their width-independent Schatten packing tools have applications far beyond robust PCA. The techniques developed here could be adapted for other complex optimization domains, such as fair resource allocation in operations research, opening new avenues for high-dimensional algorithmic design.

Summary updated

Abstract

We develop two methods for the following fundamental statistical task: given an $\eps$-corrupted set of $n$ samples from a $d$-dimensional sub-Gaussian distribution, return an approximate top eigenvector of the covariance matrix. Our first robust PCA algorithm runs in polynomial time, returns a $1 - O(\eps\log\eps^{-1})$-approximate top eigenvector, and is based on a simple iterative filtering approach. Our second, which attains a slightly worse approximation factor, runs in nearly-linear time and sample complexity under a mild spectral gap assumption. These are the first polynomial-time algorithms yielding non-trivial information about the covariance of a corrupted sub-Gaussian distribution without requiring additional algebraic structure of moments. As a key technical tool, we develop the first width-independent solvers for Schatten-$p$ norm packing semidefinite programs, giving a $(1 + \eps)$-approximate solution in $O(p\log(\tfrac{nd}{\eps})\eps^{-1})$ input-sparsity time iterations (where $n$, $d$ are problem dimensions).
BibTeX
@inproceedings{jambulapati2020robust,
  author = {Arun Jambulapati and Jerry Li and Kevin Tian},
  title = {{Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=ecLSzRyY17h},
}
Figure