# Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 13 Aug 2024.

## Builds on (most cited first, 6 of 6)

- [Deep Unfolded Robust PCA with Application to Clutter Suppression in Ultrasound](https://mlsanity.com/paper/1811.08252/) (2018)
- [Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset](https://mlsanity.com/paper/1511.01245/) (2015)
- [Bandit Principal Component Analysis](https://mlsanity.com/paper/1902.03035/) (2019)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Anomaly Detection on Financial Time Series by Principal Component Analysis and Neural Networks](https://mlsanity.com/paper/2209.11686/) (2022)
- [A Finite Algorithm for the Realizabilty of a Delaunay Triangulation](https://mlsanity.com/paper/2210.03932/) (2022)

## Abstract (arXiv)

In this paper, we introduce new algorithms for Principal Component Analysis (PCA) with outliers. Utilizing techniques from computational geometry, specifically higher-degree Voronoi diagrams, we navigate to the optimal subspace for PCA even in the presence of outliers. This approach achieves an optimal solution with a time complexity of nd+O(1)poly(n,d). Additionally, we present a randomized algorithm with a complexity of 2O(r(d-r)) × poly(n, d). This algorithm samples subspaces characterized in terms of a Grassmannian manifold. By employing such sampling method, we ensure a high likelihood of capturing the optimal subspace, with the success probability (1 - δ)T. Where δ represents the probability that a sampled subspace does not contain the optimal solution, and T is the number of subspaces sampled, proportional to 2r(d-r). Our use of higher-degree Voronoi diagrams and Grassmannian based sampling offers a clearer conceptual pathway and practical advantages, particularly in handling large datasets or higher-dimensional settings.