Refined Complexity of PCA with Outliers
Authors: Kirill Simonov, Fedor Fomin, Petr Golovach, Fahad Panolan
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a rigorous algorithmic analysis of the problem. We show that the problem is solvable in time n O(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. Our algorithm is, foremost, of theoretical interest, especially in the presense of the nearly-matching lower bound showing that doing something essentially better is next to impossible. |
| Researcher Affiliation | Academia | 1Department of Informatics, University of Bergen, Norway. Correspondence to: Fedor Fomin <fomin@ii.uib.no>, Petr Golovach <pgo041@uib.no>, Fahad Panolan <Fahad.Panolan@uib.no>, Kirill Simonov <Kirill.Simonov@uib.no>. |
| Pseudocode | No | The paper describes the algorithm in numbered prose (e.g., 'Our algorithm proceeds as follows. 1. Using the algorithm from Proposition 1, obtain a point VC from each cell C of W over P. 2. For each VC, compute the optimal SVC:...'), but does not use structured pseudocode or an algorithm block. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of its own open-source code. It mentions 'On the practical side, we note that a number of routines from (Basu et al., 2006) is implemented in the SARAG library (Caruso, 2006).' but this refers to a third-party library, not their implementation. |
| Open Datasets | No | The paper is theoretical and does not use or specify any publicly available datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not report on experiments or dataset usage, thus no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments, therefore no specific ancillary software details with version numbers are provided as dependencies for experimental replication. It mentions 'the SARAG library' but not as a dependency for their own work's experimental setup. |
| Experiment Setup | No | The paper is theoretical and does not describe any experiments, therefore no experimental setup details like hyperparameters or training settings are provided. |