Skip to yearly menu bar Skip to main content


Fixed-Parameter and Approximation Algorithms for PCA with Outliers

Yogesh Dahiya · Fedor Fomin · Fahad Panolan · Kirill Simonov

Keywords: [ Algorithms ]


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.

Chat is not available.