• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Faculty of Science and Technology
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
  •   Hjem
  • Faculty of Science and Technology
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
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
Peer reviewed, Journal article
Published version
Thumbnail
Åpne
PDF (321.2Kb)
Permanent lenke
https://hdl.handle.net/1956/22122
Utgivelsesdato
2019
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [1077]
Originalversjon
Proceedings of Machine Learning Research (PMLR). 2019;97:5818-5826  
Sammendrag
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.
Utgiver
PMLR
Tidsskrift
Proceedings of Machine Learning Research (PMLR)
Opphavsrett
Copyright 2019 The Author(s)

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit