Abstract
We develop two methods for the following fundamental statistical task: given an $\epsilon$-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(\epsilon\log\epsilon^{-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 + \epsilon)$-approximate solution in $O(p\log(\tfrac{nd}{\epsilon})\epsilon^{-1})$ input-sparsity time iterations.
Introduction
Principal Component Analysis (PCA) is a cornerstone of modern data science, essential for dimensionality reduction and identifying dominant patterns in high-dimensional datasets. However, standard PCA is notoriously sensitive to outliers; even a small fraction of adversarially corrupted data can significantly bias the resulting eigenvectors.
While the field of robust statistics has developed efficient algorithms for PCA, most existing methods rely on restrictive assumptions. They typically require the data to be exactly Gaussian or to possess "certifiably bounded moments"—a technical condition necessary for Sum-of-Squares (SoS) optimization. This paper addresses the gap for sub-Gaussian distributions. These distributions are ubiquitous in nature, characterized by tails that decay at least as fast as a normal distribution, yet they lack the rigid algebraic structure (such as Isserlis’ Theorem) that previous robust algorithms exploited.
Algorithmic Frameworks
This research introduces two distinct algorithmic approaches to achieve robust PCA under sub-Gaussian assumptions without requiring additional algebraic moment structures.
1. Iterative Filtering (Algorithm 6)
The first method utilizes a "top-down" iterative filtering strategy. The algorithm computes the empirical covariance matrix and identifies the top eigenvector. It then employs a specialized 1D Robust Variance estimator to evaluate whether the variance in that specific direction is suspiciously high. If an anomaly is detected, the algorithm filters or downweights the points contributing excessively to that variance. This process repeats until the variance stabilizes, yielding a $1 - O(\epsilon \log \epsilon^{-1})$-approximate top eigenvector in polynomial time.
2. Nearly-Linear Time via Schatten-$p$ Packing (Algorithm 4)
To address the computational demands of massive datasets, the authors developed a second method that reframes the problem as a Semidefinite Program (SDP). Specifically, they focus on Schatten-$p$ norm packing. While traditional packing SDPs often utilize the spectral norm ($p=\infty$), this approach uses a smaller $p$ to "smooth" the optimization landscape, encouraging a more uniform distribution of spectral mass.
To facilitate this, the authors engineered a novel technical tool: the first width-independent solver for Schatten-$p$ packing. In optimization, "width" refers to the scale of the constraints. A width-independent solver is highly efficient because its runtime depends only logarithmically on the problem's scale, allowing for nearly-linear time complexity relative to the input size.
Key Insights
- Sufficiency of Sub-Gaussianity: The paper proves that simple sub-Gaussian concentration is sufficient for robust PCA. This demonstrates that the complex algebraic identities of Gaussian distributions are not a prerequisite for effective outlier handling.
- Schatten-$p$ Norm Smoothing: Generalizing packing SDPs to Schatten-$p$ norms allows for faster convergence and nearly-linear runtimes, providing a bridge between statistical robustness and computational efficiency.
- Extension of Positivity Structure: The research shows that the positivity structures used to accelerate Linear Program (LP) solvers can be extended to matrix-based SDPs, representing a significant advancement in continuous optimization.
Results and Performance
The proposed algorithms were evaluated under the standard $\epsilon$-corruption model, where an adversary can modify an $\epsilon$ fraction of the samples.
- Statistical Accuracy: The filtering algorithm achieves the near-optimal accuracy of $1 - O(\epsilon \log \epsilon^{-1})$.
- Computational Complexity: The iterative filtering method runs in $O(\frac{nd^2}{\epsilon})$ time. The Schatten-$p$ packing method achieves nearly-linear time—$O(\frac{nd}{\epsilon^{4.5}} + \frac{ndt}{\epsilon^{1.5}})$—assuming a mild spectral gap exists between the top eigenvalues.
- Sample Efficiency: Both methods are near-sample optimal, requiring approximately $O(d)$ samples, which is the theoretical minimum even for non-robust PCA.
Limitations and Future Directions
While these algorithms represent a significant step forward, certain constraints remain. The nearly-linear time algorithm requires a "mild spectral gap" (where the top eigenvalue is sufficiently larger than the others); its performance may degrade if eigenvalues are closely clustered. Additionally, the current Schatten-$p$ solver is optimized for odd integers $p$, suggesting that extending the solver to even or non-integer values is a viable path for future research. Finally, the authors suggest that Schatten-$p$ packing could have broader applications in "spectrally fair" resource allocation within complex systems.
Summary updated