Principle Components Updates via Matrix Perturbations

Authors: Aiman Elragig, Hanan Dreiwi, Dung Ly, Idriss Elmabrook

Abstract:

This paper highlights a new approach to look at online principle components analysis (OPCA). Given a data matrix X ∈ R,^m x n we characterise the online updates of its covariance as a matrix perturbation problem. Up to the principle components, it turns out that online updates of the batch PCA can be captured by symmetric matrix perturbation of the batch covariance matrix. We have shown that as n→ n0 >> 1, the batch covariance and its update become almost similar. Finally, utilize our new setup of online updates to find a bound on the angle distance of the principle components of X and its update.

Keywords: Online data updates, covariance matrix, online principle component analysis (OPCA), matrix perturbation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1132054

References:

[1] J. Weng, Y. Zhang, W.S. Hwang, Candied covariance-free incremental principle component analysis. IEEE Trans. Pattern Anal. Mach. Intel. Res 9 (2003) 2287-2320.
[2] Y. Zhang, J. Wang, Convergence Analysis of Complementary candid incremental principle analysis. Technical Report MSU-CSE-01-23, Department of Computer Science and Engineering, Michigan State University, East Lansing, MI.
[3] G. Stewart, J. Sun, Matrix Perturbation Theory. New York: Academic Press,1990
[4] R. A. Horn and C. Johnson. Matrix Analysis. Cambridge University press, 1990.
[5] Fontenla-Romero, scar, et al. Online machine learning.” Efficiency and Scalability Methods for Computational Intellect 27 (2013).
[6] Provatas, Spyridon. An online machine learning algorithm for heat load forecasting in district heating systems. (2014).
[7] H. Wang, Pi. Daoying, S. Youxian, Online SVM regression algorithm-based adaptive inverse control. Neurocomputing 70(4) (2007) 952-959.
[8] W. Barbakh, C. Fyfe, Online clustering algorithms. International Journal of Neural Systems 18(03) (2008) 185-194.
[9] H. Cardot, D. Degras, Online Principle Component Analysis in High Dimension: Which Algorithm to Choose?,Technical report arXiv:1511.03688 (2015).
[10] Z. Karnin, E. Liberty, Online PCA with Spectral Bounds, JMLR: Workshop and Conference Proceedings 40(2015)1-12.
[11] A. Balsubramani, S. Dasgupta, Y. Freund, The fast convergence of incremental pca. Advances in Neural Information Processing Systems 26(2013)3174-3182.
[12] H. Zhao, P. Chi, J.T. Kwok, A novel incremental principle components analysis and its application for face recognition. IEEE Transactions on Systems. Man. Cybernetics-Partt B: Cybernetics 36(4)(2016) 873-886.
[13] A. D. Iodice, A. Markos, Low-dimensional tracking of association structures in categorical data. Stat. Comput. 25(5)(2015)1009-1022
[14] J. Tang, W. Yu, T, Chai, L. Zhao, Online principle component analysis with applications to process modeling. Neurocomputing 82(2012)167-178.
[15] T. Budavari, V. Wild, A. Dobos, C. Yip, Reliable eigenspectra for new generation surveys. Numer. Math., 394(2009)1496-1502
[16] H. Zha, H. D. Simon, On upadating problems in latent sementing indexing, AIAM J. Sci. Comput,, 21(2)(1999)782-791.
[17] R. A. Fisher, The use of multiple measurements in taxonomic problems, Annals of Eugenics, 7 (2) (1936) 179188.
[18] J Nie, W Kotlowski, MK Warmuth, Online PCA with optimal regret, Journal of Machine Learning Research 17(173) (2016) 1-49.
[19] D Garber, E Hazan, T Ma, Online learning of eigenvectors. In International Conference on Machine Learning (2015) 560-56.
[20] A. Allahyar, HS. Yazdi, Online discriminative component analysis feature extraction from stream data with domain knowledge, Intelligent Data Analysis 18(5) (2014) 927-951.
[21] M. Herbster, S. Pasteris, M. Pontil, Predicting a switching sequence of graph labelings, Journal of Machine Learning Research 16 (2015) 2003-2022.
[22] G. H. Golub, C. F. Van Loan, Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD,2003, fourth, edition.
[23] J. B. Tenenbaum, V. De Silva, J. C. Langford, A global geometric framework for nonlinear dimensionality reduction. science, 290(5500)((2000) 2319-2323.
[24] G. E. Hinton, R. R. Salakhutdinov, Reducing the dimensionality of data with neural networks. science, 313(5786) (2006) 504-507.
[25] E. Bingham, H. Mannila, Random projection in dimensionality reduction: applications to image and text data, In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001) 245-250.
[26] S. T. Roweis, L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500) (2000) 2323-2326.
[27] O. Fontenla-Romero, B. Guijarro-Berdinas, D. Martinez-Rego, B. Perez-Sanchez, D. Peteiro-Barral, Online machine learning. Efficiency and Scalability Methods for Computational Intellect, 27 (2013).
[28] G. H. Golub, Some modified matrix eigenvalue problems. SIAM Review, 15 (1973) 318334.
[29] M. Gu, S. Eisenstat, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl 15 (1994)12661276.
[30] W. Li, H. Yue, S. Valle-Cervantes, S. Qin, Recursive PCA for adaptive process monitoring, J. Process Control, 10 (2000) 471486
[31] A. Hegde, J. Principe, D. Erdogmus, U. Ozertem, Y. Rao, H. Peddaneni, Perturbation-based eigenvector updates for on-line principal components analysis and canonical correlation analysis, J. VLSI Sign. Process., 45 (2006) 8595.
[32] J. Tang, W. Yu, T. Chai, L. Zhao, On-line principal component analysis with application to process modeling. Neurocomputing, 82 (2012) 167178.
[33] T. D. Sanger, Optimal unsupervised learning in single-layer linear feedforward neural network, Neural Netw. 2(1989) 459-473.
[34] E. Oja, J. Karhunen, On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. Journal of mathematical analysis and applications, 106(1) (1985) 69-84.