# Refined Complexity of PCA with Outliers

arXiv: https://arxiv.org/abs/1905.04124 · HTML: https://mlsanity.com/paper/1905.04124/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2019.

## Built on by (most cited first, 7 of 7)

- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [The Complexity of Envy-Free Graph Cutting](https://mlsanity.com/paper/2312.07043/) (2023)
- [Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams](https://mlsanity.com/paper/2408.06867/) (2024)
- [ProHD: Projection-Based Hausdorff Distance Approximation](https://mlsanity.com/paper/2511.18207/) (2025)

## Abstract (arXiv)

Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and neuroscience. However, it is well-documented that the applicability of PCA in many real scenarios could be constrained by an "immune deficiency" to outliers such as corrupted observations. We consider the following algorithmic question about the PCA with outliers. For a set of n points in ℝd, how to learn a subset of points, say 1% of the total number of points, such that the remaining part of the points is best fit into some unknown r-dimensional subspace? We provide a rigorous algorithmic analysis of the problem. We show that the problem is solvable in time nO(d2). In particular, for constant dimension the problem is solvable in polynomial time. We complement the algorithmic result by the lower bound, showing that unless Exponential Time Hypothesis fails, in time f(d)no(d), for any function f of d, it is impossible not only to solve the problem exactly but even to approximate it within a constant factor.