Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

T. Krasulina, “Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices,” Automatation and Remote Control , pp. 50–56, 1970

1970

Earlier work this paper cites.

P.-Å. Wedin, “Perturbation bounds in connection with singular value decomposition,” BIT Numerical Mathematics , vol. 12, no. 1, pp. 99–111, 1972

1972

Earlier work this paper cites.

E. Oja, “Simplified neuron model as a principal component analyzer,” Journal of mathematical biology , vol. 15, no. 3, pp. 267–273, 1982

1982

Earlier work this paper cites.

P. M. Hall, A. D. Marshall, and R. R. Martin, “Incremental eigenanalysis for classification.” in BMVC , vol. 98. Citeseer, 1998, pp. 286–295

1998

Earlier work this paper cites.

I. M. Johnstone, “On the distribution of the largest eigenvalue in principal components analysis,” Annals of statistics , pp. 295–327, 2001

2001

Earlier work this paper cites.

I. Jolliffe, Principal component analysis . Wiley Online Library, 2002

2002

Earlier work this paper cites.

J. Weng, Y. Zhang, and W.-S. Hwang, “Candid covariance-free incremental principal component analysis,” Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol. 25, no. 8, pp. 1034–1040, 2003

2003

Earlier work this paper cites.

M. K. Warmuth and D. Kuzmin, “Randomized PCA algorithms with regret bounds that are logarithmic in the dimension,” in Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006 , 2006, pp. 1481–1488

2006

Earlier work this paper cites.

D. A. Ross, J. Lim, R.-S. Lin, and M.-H. Yang, “Incremental learning for robust visual tracking,” International Journal of Computer Vision , vol. 77, no. 1-3, pp. 125–141, 2008

2008

Earlier work this paper cites.

K. L. Clarkson and D. P. Woodruff, “Numerical linear algebra in the streaming model,” in Proceedings of the forty-first annual ACM symposium on Theory of computing . ACM, 2009, pp. 205–214

2009

Cited alongside, same era.

R. Vershynin, “Introduction to the non-asymptotic analysis of random matrices,” arXiv preprint arXiv:1011.3027 , 2010

Original

2010

Cited alongside, same era.

M. Cohen, Y. T. Lee, G. Miller, J. Pachocki, and A. Sidford, “Geometric median in nearly linear time,” To Appear in 48th Annual Symposium on the Theory of Computing (STOC) 2016 , 2010

2010

Cited alongside, same era.

J. A. Tropp, “User-friendly tail bounds for sums of random matrices,” Foundations of Computational Mathematics , vol. 12, no. 4, pp. 389–434, 2012

2012

Cited alongside, same era.

G. H. Golub and C. F. Van Loan, Matrix computations . JHU Press, 2012, vol. 3

M. Hardt and E. Price, “The noisy power method: A meta algorithm with applications,” in Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada , 2014, pp. 2861–2869

2014

Later among the works it cites.

C. D. Sa, C. Re, and K. Olukotun, “Global convergence of stochastic gradient descent for some non-convex matrix problems,” in Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015 , 2015, pp. 2332–2341

2015

Later among the works it cites.

C. Jin, S. M. Kakade, C. Musco, P. Netrapalli, and A. Sidford, “Robust shift-and-invert preconditioning: Faster and more sample efficient algorithms for eigenvector computation,” arXiv preprint arXiv:1510.08896 , 2015

Original

2015

Later among the works it cites.

M. B. Cohen, J. Nelson, and D. P. Woodruff, “Optimal approximate matrix product in terms of stable rank,” arXiv preprint arXiv:1507.02268 , 2015

Original