Principle Components Updates via Matrix Perturbations
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:76274", author = "Aiman Elragig and Hanan Dreiwi and Dung Ly and Idriss Elmabrook", title = "Principle Components Updates via Matrix Perturbations", 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.", volume = "11", number = "8", pages = "968-9", }
