Timezone: »
Poster
Fixed-Parameter and Approximation Algorithms for PCA with Outliers
Yogesh Dahiya · Fedor Fomin · Fahad Panolan · Kirill Simonov
PCA with Outliers is the fundamental problem of identifying an underlying low-dimensional subspace in a data set corrupted with outliers. A large body of work is devoted to the information-theoretic aspects of this problem. However, from the computational perspective, its complexity is still not well-understood. 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.
Author Information
Yogesh Dahiya (The Institute of Mathematical Sciences (HBNI), Chennai, India)
Fedor Fomin (University of Bergen)
Fahad Panolan (Indian Institute of Technology Hyderabad)
Kirill Simonov (University of Bergen)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Fixed-Parameter and Approximation Algorithms for PCA with Outliers »
Fri. Jul 23rd 01:45 -- 01:50 AM Room
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 -
2019 Poster: Refined Complexity of PCA with Outliers »
Kirill Simonov · Fedor Fomin · Petr Golovach · Fahad Panolan -
2019 Oral: Refined Complexity of PCA with Outliers »
Kirill Simonov · Fedor Fomin · Petr Golovach · Fahad Panolan