Abstract
We consider the problem of streaming principal component analysis (PCA) whenthe observations are noisy and generated in a non-stationary environment. Given$T$, $p$-dimensional noisy observations sampled from a non-stationary variantof the spiked covariance model, our goal is to construct the best linear$k$-dimensional subspace of the terminal observations. We study the effect ofnon-stationarity by establishing a lower bound on the number of samples and thecorresponding recovery error obtained by any algorithm. We establish theconvergence behaviour of the noisy power method using a novel proof techniquewhich maybe of independent interest. We conclude that the recovery guarantee ofthe noisy power method matches the fundamental limit, thereby generalizingexisting results on streaming PCA to a non-stationary setting.