Apratim Dey

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

It is shown that for online / streaming algorithms the story is very different, and constant aspect ratio is insufficient for nonzero overlap, in stark contrast to ordinary high dimensional PCA, where nonzero overlap is possible at constant $n/d and improves as $n/d$ increases.