Online Power Iteration For Subspace Estimation Under Incomplete Observations: Limiting Dynamics And Phase Transitions

摘要

We analyze the dynamics of an imputation-based online power iteration method for estimating a low-dimensional subspace from a stream of sample vectors with random missing entries. In the asymptotic regime, we show that the dynamic performance of the algorithm can be fully characterized by a finite-dimensional deterministic matrix recursion process. This limiting process provides an exact characterization of the relationship between estimation accuracy, sample complexity, and subsampling ratios. Further analysis of the limiting dynamics also reveals a sharp phase transition phenomenon, showing that there exist critical batch sizes below which the algorithm can perform no better than guessing. Although our analysis is asymptotic in nature, the theoretical results provide accurate predictions for the actual performance of the algorithm, even in moderate signal dimensions.