Name
Abstract | ||
|---|---|---|
We consider the online version of the well known Principal Component Analysis (PCA) problem. In standard PCA, the input to the problem is a set of d-dimensional vectors X = [x1, . . ., xn] and a target dimension k < d; the output is a set of k-dimensional vectors Y = [y1, . . ., yn] that minimize the reconstruction error: [EQUATION]. Here, Φ ∈ Rdxk is restricted to being isometric. The global minimum of this quantity, OPTk, is obtainable by offline PCA. In online PCA (OPCA) the setting is identical except for two differences: i) the vectors xt are presented to the algorithm one by one and for every presented xt the algorithm must output a vector yt before receiving xt+1; ii) the output vectors yt are l dimensional with l ≥ k to compensate for the handicap of operating online. To the best of our knowledge, this paper is the first to consider this setting of OPCA. Our algorithm produces yt ∈ Rl with l = O(k · poly(1/ε)) such that ALG ≤ OPTk + ε||X||[EQUATION]. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.5555/2722129.2722190 | SODA |
DocType | ISBN | Citations |
Conference | 978-1-61197-433-1 | 1 |
PageRank | References | Authors |
0.35 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| Dan Garber | 2 | 1 | 1.36 |
| Zohar S. Karnin | 3 | 266 | 20.98 |
| Edo Liberty | 4 | 397 | 24.83 |