The Phase Transition in Online PCA Depends on n/dlog(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→∞ with n/d→ γ∈(0,∞), in understanding the limits of canonical estimation problems. In particular, for estimating the top eigenvector of a d× 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 Sigma=θ2 v0v0^top+I∈ℝd× d, and run Oja's algorithm with step size δ/d on n iid samples Xk~N(0,Sigma), with output hat vn. Then, as n,d→∞ with n/dlog d→γ∈(0,∞), we establish a phase transition: |langlehat vn,v0rangle|→ 0 when γ<γ_*, and →ρ_* when γ>γ_*. Here ρ_*=ρ_*(θ,δ)=√(θ2-δ/2)_+/θ2(1+δ/2) and γ_*=γ_*(θ,δ)=1/2δ(θ2-δ/2)_+. Further, at criticality, when n=[γ_*dlog d+η d] and d→∞, η∈ℝ, the correlation is random: |langlehat vn,v0rangle|stackrelw→ρ_*|G|exp(η/2γ_*)/√ρ_*4+G2exp(η/γ_*) where G~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.