Subspace Estimation From Incomplete Observations: A High-Dimensional Analysis

Chuang Wang, Yonina C. Eldar, Yue M. Lu

Abstract

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 O(1/√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 signalto-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.
BibTeX
@article{wang2019subspace,
  author = {Chuang Wang and Yonina C. Eldar and Yue M. Lu},
  title = {{Subspace Estimation From Incomplete Observations: A High-Dimensional Analysis}},
  journal = {IEEE Journal of Selected Topics in Signal Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=3EASe16L1E},
}

Loading related content...

Figure