Timezone: »
Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and neuroscience. However, it is well-documented that the applicability of PCA in many real scenarios could be constrained by an “immune deficiency” to outliers such as corrupted observations. We consider the following algorithmic question about the PCA with outliers. For a set of n points in R^d, how to learn a subset of points, say 1% of the total number of points, such that the remaining part of the points is best fit into some unknown r-dimensional subspace? We provide a rigorous algorithmic analysis of the problem. We show that the problem is solvable in time n^O(d^2) . 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) n^o(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.
Author Information
Kirill Simonov (University of Bergen)
Fedor Fomin (University of Bergen)
Petr Golovach (University of Bergen)
Fahad Panolan (University of Bergen)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Refined Complexity of PCA with Outliers »
Wed. Jun 12th 01:30 -- 04:00 AM Room Pacific Ballroom #180
More from the Same Authors
-
2022 Poster: The Complexity of k-Means Clustering when Little is Known »
Robert Ganian · Thekla Hamm · Viktoriia Korchemna · Karolina Okrasa · Kirill Simonov -
2022 Spotlight: The Complexity of k-Means Clustering when Little is Known »
Robert Ganian · Thekla Hamm · Viktoriia Korchemna · Karolina Okrasa · Kirill Simonov -
2021 Poster: Fixed-Parameter and Approximation Algorithms for PCA with Outliers »
Yogesh Dahiya · Fedor Fomin · Fahad Panolan · Kirill Simonov -
2021 Spotlight: Fixed-Parameter and Approximation Algorithms for PCA with Outliers »
Yogesh Dahiya · Fedor Fomin · Fahad Panolan · Kirill Simonov