Manfred Warmuth, UCSC

Online Algorithms for Principal Component Analysis

We design an online algorithm for Principal Component Analysis. In
each trial the current instance is centered and projected into a
probabilistically chosen low dimensional subspace.  The regret of our
online algorithm, i.e. total expected quadratic approximation error of
the online algorithm minus the total quadratic approximation error of
the batch algorithm, is bounded by a term whose dependence on the
dimension of the instances is only logarithmic.

We first develop our methodology in the expert setting of online
learning by giving an algorithm for learning as well as the best
subset of experts of a certain size. This algorithm is then lifted to
the matrix setting where the subsets of experts correspond to
subspaces.  The algorithm represents the uncertainty over the best
subspace as a density matrix whose eigenvalues are bounded.  The
running time is O(n^2) per trial, where n is dimension of the
instances.

Joint work with Dima Kuzmin.