Subspace Estimation from Incomplete Observations: A High-Dimensional
  Analysis
  We present a high-dimensional analysis of three popular algorithms, namely,
Oja's method, GROUSE and PETRELS, for subspace estimation from streaming and
highly incomplete observations. We show that, with proper time scaling, the
time-varying principal angles between the true subspace and its estimates given
by the algorithms converge weakly to deterministic processes when the ambient
dimension $n$ tends to infinity. Moreover, the limiting processes can be
exactly characterized as the unique solutions of certain ordinary differential
equations (ODEs). A finite sample bound is also given, showing that the rate of
convergence towards such limits is $\mathcal{O}(1/\sqrt{n})$. In addition to
providing asymptotically exact predictions of the dynamic performance of the
algorithms, our high-dimensional analysis yields several insights, including an
asymptotic equivalence between Oja's method and GROUSE, and a precise scaling
relationship linking the amount of missing data to the signal-to-noise ratio.
By analyzing the solutions of the limiting ODEs, we also establish phase
transition phenomena associated with the steady-state performance of these
techniques.
