Online principal components analysis

We consider the online version of the well known Prin-cipal Component Analysis (PCA) problem. In stan-dard PCA, the input to the problem is a set of d-dimensional vectors X = [x1,...,xn] and a target di-mension k < d; the output is a set of k-dimensional vectors Y = [y1,...,yn] that minimize the reconstruc-tion error: minΦ i ‖xi − Φyi‖22. Here, Φ ∈ Rd×k 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 ex-cept 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 ` dimensional with ` ≥ k to compensate for the handicap of operating on-line. To the best of our knowledge, this paper is the first to consider this setting of OPCA. Our algorithm produces yt ∈ R ` with ` = O(k · poly(1/ε)) such that ALG ≤ OPTk +ε‖X‖2F.