The Phase Transition in Online PCA Depends on n/d (d), not n/d

High dimensional statistical theory has established the importance of constant aspect ratio, when the number of dimensions (d) and samples (n) satisfy n,d to infinity with n/d to gamma in(0, infinity), in understanding the limits of canonical estimation problems. In particular, for estimating the top eigenvector of a d times d population covariance matrix from n iid samples, the BBP phase transition gives a precise threshold -- a simple functional of the aspect ratio -- such that the top sample principal component attains nonzero asymptotic correlation with the truth only when the leading population eigenvalue exceeds it. In this paper, we show that for online / streaming algorithms the story is very different, and constant aspect ratio is insufficient for nonzero overlap. We study Oja's algorithm, the most popular method for online PCA. Let = theta squared v 0v 0+I in R d times d, and run Oja's algorithm with step size delta/d on n iid samples X k about N(0,), with output v n. Then, as n,d to infinity with n/d d to gamma in(0, infinity), we establish a phase transition: v n,v 0 to 0 when gamma< gamma*, and to rho* when gamma> gamma*. Here rho*= rho*(theta, delta)= sqrt (theta 2-delta/2)+/theta 2(1+ delta/2) and gamma*= gamma*(theta, delta)=1/2 delta(theta 2-delta/2)+. Further, at criticality, when n=[gamma*d d+ eta d] and d to infinity, eta in R, the correlation is random: v n,v 0 to rho*G (eta/2 gamma*)/sqrt rho* 4+G 2 (eta/gamma*) where G about N(0,1). This is in stark contrast to ordinary high dimensional PCA, where nonzero overlap is possible at constant n/d and improves as n/d increases.