2026/07/27 by Apratim Dey
Engineering · Mathematics · #eess.SP #math.PR #math.ST #stat.ML #stat.TH
arxiv created 2026/07/30 · arxiv updated 2026/07/31
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 Σ=θ2 v0v0^\top+I∈ℝd× d, and run Oja's algorithm with step size δ/d on n iid samples Xk\simN(0,Σ), with output vn. Then, as n,d→∞ with n/dlog d→γ∈(0,∞), we establish a phase transition: |⟨ vn,v0⟩|→ 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: |⟨ vn,v0⟩|\stackrelw→ρ_*|G|exp(η/2γ_*)/√(ρ_*4+G2exp(η/γ_*)) where G\simN(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.