Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSimonov, Kirill
dc.date.accessioned2020-05-07T10:57:24Z
dc.date.available2020-05-07T10:57:24Z
dc.date.issued2019
dc.PublishedFomin V, Golovach P, Panolan F, Simonov K. Refined Complexity of PCA with Outliers. Proceedings of Machine Learning Research (PMLR). 2019;97:5818-5826eng
dc.identifier.issn2640-3498en_US
dc.identifier.urihttps://hdl.handle.net/1956/22122
dc.description.abstractPrincipal 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.en_US
dc.language.isoengeng
dc.publisherPMLRen_US
dc.titleRefined Complexity of PCA with Outliersen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2020-01-17T14:49:02Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2019 The Author(s)en_US
dc.identifier.cristin1774904
dc.source.journalProceedings of Machine Learning Research (PMLR)
dc.relation.projectNorges forskningsråd: 249994
dc.relation.projectNorges forskningsråd: 263317


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel