SDS Seminar Series – Dr. Purna Sarkar

Our first work looks at data streams generated from a Markov chain. While streaming PCA is typically analyzed under the IID data model, in many applications like distributed optimization, data points are sampled from a Markov chain and, therefore, are dependent. The naive approach of dropping data leads to a suboptimal rate. We use a novel linearization argument to remove the logarithmic dependence on the number of samples n. 

Typically, the analysis of Oja's algorithm assumes that the effective rank of the covariance matrix is much smaller than n. Our second work examines online sparse PCA, where the effective rank is comparable to n.  This differs from previously studied settings because the Oja vector does not concentrate on the true population eigenvector. Here, we show that a simple thresholding yields a consistent estimate of the population eigenvector. Both are joint works with Syamantak Kumar.