Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams
<|reference_start|>Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams: 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 $n^{d+\mathcal{O}(1)}\text{poly}(n,d)$. Additionally, we present a randomized algorithm with a complexity of $2^{\mathcal{O}(r(d-r))} \times \text{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 - \delta)^T$. Where $\delta$ represents the probability that a sampled subspace does not contain the optimal solution, and $T$ is the number of subspaces sampled, proportional to $2^{r(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.<|reference_end|>
@article{hashemian2024optimal,
    title={Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams},
    author={Sajjad Hashemian, Mohammad Saeed Arvenaghi, Ebrahim Ardeshir-Larijani},
    journal={arXiv preprint arXiv:2408.06867},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06867},
    primaryClass={cs.LG}
}