Timezone: »

Fixed-Parameter and Approximation Algorithms for PCA with Outliers
Yogesh Dahiya · Fedor Fomin · Fahad Panolan · Kirill Simonov

Thu Jul 22 06:45 PM -- 06:50 PM (PDT) @

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)

More from the Same Authors