• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Refined Complexity of PCA with Outliers

Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill
Conference object, Peer reviewed, Journal article
Published version
Thumbnail
View/Open
PDF (321.2Kb)
URI
https://hdl.handle.net/1956/22122
Date
2019
Metadata
Show full item record
Collections
  • Department of Informatics [536]
Original version
Fomin V, Golovach P, Panolan F, Simonov K. Refined Complexity of PCA with Outliers. Proceedings of Machine Learning Research (PMLR). 2019;97:5818-5826  
Abstract
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.
Publisher
PMLR
Journal
Proceedings of Machine Learning Research (PMLR)
Copyright
Copyright 2019 The Author(s)

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit