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 $\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.

Introduction

Subspace estimation is a cornerstone of signal processing, essential for tasks ranging from array processing to video surveillance. In the modern era of "Big Data," researchers face two primary challenges: high dimensionality coupled with streaming data, and the prevalence of missing observations due to sensor failures or power constraints. While algorithms like GROUSE and PETRELS are widely deployed, a precise theoretical understanding of their dynamic performance—especially how missing data interacts with the Signal-to-Noise Ratio (SNR)—has remained elusive. This paper provides a rigorous high-dimensional analysis of Oja’s method, GROUSE, and PETRELS, revealing that their error trajectories converge to deterministic Ordinary Differential Equations (ODEs) as the dimension $n \to \infty$.

The Scaling Limit Framework

The core innovation of this work is the use of scaling limits. By scaling time by the ambient dimension ($k = tn$) and letting $n \to \infty$, the authors demonstrate that the stochastic evolution of the "cosine similarity matrix" (measuring the angle between the true subspace and the estimate) converges to a deterministic path. This transformation allows a complex, high-dimensional stochastic process to be analyzed as a predictable, low-dimensional dynamical system.

Figure 1: Convergence of stochastic trajectories to the deterministic limit (solid line) as the dimension $n$ increases.

As shown in Figure 1, as the dimension $n$ grows, the variance of the stochastic trajectories decreases, and the empirical performance aligns perfectly with the theoretical $n \to \infty$ limit. The authors prove a finite-sample bound, showing that the actual performance stays within $\mathcal{O}(1/\sqrt{n})$ of the ODE prediction.

Algorithmic Insights and Equivalences

The high-dimensional analysis yields several surprising insights into the nature of these streaming algorithms:

  • Asymptotic Equivalence: Despite their different mathematical foundations (Euclidean vs. Grassmannian manifolds), Oja’s method and GROUSE are asymptotically equivalent. In high dimensions, they converge to the exact same deterministic process.
  • PETRELS as Adaptive Oja: PETRELS follows a similar ODE structure but effectively utilizes an adaptive step-size matrix. This explains its faster initial convergence: it "boosts" its learning rate early on and tapers it off as it approaches the target subspace.
  • The SNR-Subsampling Link: The ODEs reveal that missing data is mathematically equivalent to lowering the SNR. Specifically, the subsampling ratio $\alpha$ and the signal covariance $\Lambda$ appear together in the governing equations as $\alpha \Lambda^2$.

Performance and Phase Transitions

By analyzing the steady-state solutions of the limiting ODEs, the paper identifies "hard" thresholds or phase transitions. If the step size is too large or the SNR is too low relative to the missing data, the algorithms fail to learn an informative estimate, remaining at a state no better than a random guess.

Figure 5: Dynamic performance of GROUSE, Oja, and PETRELS. The markers represent empirical averages, while the solid lines represent the theoretical ODE predictions.

For Oja and GROUSE with a constant step size $\tau$, an informative solution is only possible if the following stability condition is met: $$\tau < \frac{2\alpha}{\sigma^4} \min_{\ell} \lambda_\ell^2$$ This provides engineers with a concrete "speed limit" for setting learning rates in practical applications.

Conclusion

This high-dimensional framework provides a powerful tool for predicting the performance of subspace tracking algorithms. While the current analysis requires a "warm start" (a non-zero initial correlation with the target), it successfully characterizes the dynamic and steady-state behavior of these methods. Future work may explore the "escape" phase from purely random initializations and non-stationary tracking scenarios.

Summary updated

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 $\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.
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},
}
Figure