  This paper introduces Memory-limited Online Subspace Estimation Scheme
(MOSES) for both estimating the principal components of streaming data and
reducing its dimension. More specifically, in various applications such as
sensor networks, the data vectors are presented sequentially to a user who has
limited storage and processing time available. Applied to such problems, MOSES
can provide a running estimate of leading principal components of the data that
has arrived so far and also reduce its dimension.
  MOSES generalises the popular incremental Singular Vale Decomposition (iSVD)
to handle thin blocks of data, rather than just vectors. This minor
generalisation in part allows us to complement MOSES with a comprehensive
statistical analysis, thus providing the first theoretically-sound variant of
iSVD, which has been lacking despite the empirical success of this method. This
generalisation also enables us to concretely interpret MOSES as an approximate
solver for the underlying non-convex optimisation program. We find that MOSES
consistently surpasses the state of the art in our numerical experiments with
both synthetic and real-world datasets, while being computationally
inexpensive.
