Fixed-Parameter and Approximation Algorithms for PCA with Outliers
Authors: Yogesh Dahiya, Fedor Fomin, Fahad Panolan, Kirill Simonov
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study this problem from the perspective of parameterized complexity by investigating how parameters like the dimension of the data, the subspace dimension, the number of outliers and their structure, and approximation error, influence the computational complexity of the problem. Our algorithmic methods are based on techniques of randomized linear algebra and algebraic geometry. Our results. We provide several algorithms for PCA WITH OUTLIERS that work in polynomial time for small values of r. The proofs of both theorems are based on the following strategy: apply randomized dimensionality reduction (sketching), and then use the methods of algebraic geometry to compute the exact solution. |
| Researcher Affiliation | Academia | Yogesh Dahiya * 1 The Institute of Mathematical Sciences (HBNI), Chennai, India 2 Fedor Fomin * Department of Informatics, University of Bergen, Norway 3 Fahad Panolan * Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, Telangana, India. Kirill Simonov * 2 Department of Informatics, University of Bergen, Norway |
| Pseudocode | No | The paper describes algorithms using numbered steps in prose (e.g., in Section 4.1 'Subspace-sampling Algorithm' steps 1-6), but does not contain a dedicated pseudocode block or algorithm figure. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This paper is theoretical and focuses on algorithm design and complexity analysis; it does not report on empirical experiments using datasets, thus no training data information is provided. |
| Dataset Splits | No | This is a theoretical paper outlining algorithms and proofs; it does not include empirical experiments or discuss data partitioning into training, validation, or test sets. |
| Hardware Specification | No | This paper is theoretical, focusing on algorithm design and complexity analysis rather than empirical experimentation. Therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | This paper is purely theoretical, focusing on mathematical models and algorithmic complexity. It does not describe any empirical experiments, and thus no specific software dependencies with version numbers are mentioned for replication. |
| Experiment Setup | No | As a theoretical paper, this work focuses on the design and analysis of algorithms rather than practical experimentation. Consequently, it does not include details such as hyperparameters or system-level training settings for an experimental setup. |