Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.06867 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915534098923520 |
|---|---|
| author | Hashemian, Sajjad Arvenaghi, Mohammad Saeed Ardeshir-Larijani, Ebrahim |
| author_facet | Hashemian, Sajjad Arvenaghi, Mohammad Saeed Ardeshir-Larijani, Ebrahim |
| contents | 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 - δ)^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 $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06867 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams Hashemian, Sajjad Arvenaghi, Mohammad Saeed Ardeshir-Larijani, Ebrahim Machine Learning 68W01 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 - δ)^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 $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. |
| title | Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams |
| topic | Machine Learning 68W01 |
| url | https://arxiv.org/abs/2408.06867 |