Systems and Means of Informatics
2023, Volume 33, Issue 1, pp 78-89
EFFICIENT COMPUTATIONS IN MATRIX FACTORIZATION WITH MISSING COMPONENTS
Abstract
The paper is devoted to the effective implementation of matrix factorization in the presence of missing components into a product of two lower rank matrices. The problem of estimating the parameters of the adopted data model is solved by multidimensional optimization. In practice, the large sizes of the matrices and vectors included in iterative algorithms give rise to the curse of dimensionality. It is proposed to drastically reduce the complexity of matrix operations by presenting them in block-diagonal form. The article substantiates the possibility of casting individual matrices to a block-diagonal form and describes the rules for block-by-block singular value decomposition of matrices. The results of block-by-block processing are illustrated by the example of data matrix factorization of different sizes and with different probabilities of missing components. The time for estimating parameters can be reduced by several orders of magnitude compared to the processing of matrices in the usual representation.
[+] References (6)
- Chen, P. 2008. Optimization algorithms on subspaces: Revisiting missing data problem in low-rank matrix. Int. J. Comput. Vision 80(1): 125-142. doi: 10.1007/s11263-008- 0135-7.
- Krivenko, M. P. Vybor modeli pri faktorizatsii matritsy dannykh s propuskami [Model selection for matrix factorization with missing components]. Informatika i ee Prime- neniya - Inform. Appl. 16(3):52-58. doi: 10.14357/19922264220307.
- Abadir, K.M., and J. R. Magnus. 2005. Matrix algebra. Cambridge: Cambridge University Press. 466 p.
- Hung, C.-H., and T.L. Markham. 1975. The Moore-Penrose inverse of a partitioned matrix M = C^ . Linear Algebra Appl. 11 (1):73-86. doi: 10.1016/0024- 3795(75)90118-4.
- Graybill, F. A. 1983. Matrices with applications in statistics. Belmont, CA: Wadsworth Publishing Co. 461 p.
- Seber, G. A. F. 2008. A matrix handbook for statisticians. Hoboken, NJ: Wiley. 569 p.
[+] About this article
Title
EFFICIENT COMPUTATIONS IN MATRIX FACTORIZATION WITH MISSING COMPONENTS
Journal
Systems and Means of Informatics
Volume 33, Issue 1, pp 78-89
Cover Date
2023-05-11
DOI
10.14357/08696527230108
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
lower rank matrix approximation; singular decomposition; missing data; ALS algorithm; block-diagonal representation of a matrix
Authors
M. P. Krivenko 
Author Affiliations
Federal Research Center "Computer Science and Control", Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|