Approximate factorization of positive matrices by using methods of tropical optimization

N. K. Krivulin ; E. Yu. Romanova

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 16 (2020) no. 4, pp. 357-374

Résumé

The problem of rank-one factorization of positive matrices with missing (unspecified) entries is considered where a matrix is approximated by a product of column and row vectors that are subject to box constraints. The problem is reduced to the constrained approximation of the matrix, using the Chebyshev metric in logarithmic scale, by a matrix of unit rank. Furthermore, the approximation problem is formulated in terms of tropical mathematics that deals with the theory and applications of algebraic systems with idempotent addition. By using methods of tropical optimization, direct analytical solutions to the problem are derived for the case of an arbitrary positive matrix and for the case when the matrix does not contain columns (rows) with all entries missing. The results obtained allow one to find the vectors of the factor decomposition by using expressions in a parametric form which is ready for further analysis and immediate calculation. In conclusion, an example of approximate rank-one factorization of a matrix with missing entries is provided.

Détail

Keywords: positive matrix factorization, rank-one matrix approximation, log-Chebyshev distance function, tropical optimization, max-algebra.

Bibliographie

[1] A. Aissa-El-Bey, K. Seghouane, “Sparse canonical correlation analysis based on rank-1 matrix approximation and its application for FMRI signals”, 2016 IEEE Intern. Conference on Acoustics, Speech and Signal Processing, ICASSP, IEEE, 2016, 4678–4682 | DOI

[2] R. Kannan, M. Ishteva, H. Park, “Bounded matrix factorization for recommender system”, Knowledge and Information Systems, 39:3 (2014), 491–511 | DOI

[3] X. Xiu, L. Kong, “Rank-one and sparse matrix decomposition for dynamic MRI”, Numerical Algebra, Control and Optimization, 5:2 (2015), 127–134 | DOI | MR | Zbl

[4] M. T. Belachew, N. Gillis, “Solving the maximum clique problem with symmetric rank-one nonnegative matrix approximation”, Journal of Optimization Theory and Applications, 173:1 (2017), 279–296 | DOI | MR | Zbl

[5] N. Krivulin, “Rating alternatives from pairwise comparisons by solving tropical optimization problems”, 2015 12th Intern. Conference on Fuzzy Systems and Knowledge Discovery, FSKD, IEEE, 2015, 162–167 | DOI

[6] N. Krivulin, “Using tropical optimization techniques to evaluate alternatives via pairwise comparisons”, 2016 Proceedings of the 7th SIAM Workshop on Combinatorial Scientific Computing, SIAM, 2016, 62–72 | DOI

[7] N. Gillis, “Introduction to nonnegative matrix factorization”, SIAG/OPT Views and News, 25:1 (2017), 7–16 | MR

[8] N. K. Kumar, J. Schneider, “Literature survey on low rank approximation of matrices”, Linear and Multilinear Algebra, 65:11 (2017), 2212–2244 | DOI | MR | Zbl

[9] D. Feldman, T. Tassa, “More constraints, smaller coresets: constrained matrix approximation of sparse big data”, Proceedings of the 21st ACM SIGKDD Intern. Conference on Knowledge Discovery and Data Mining, ACM, New York, 2015, 249–258 | DOI

[10] A. Kyrillidis, “Simple and practical algorithms for p-norm low-rank approximation”, 34th Conference on Uncertainty in Artificial Intelligence, AUAI Press, Corvallis, 2018, 414–424

[11] N. Gillis, Y. Shitov, “Low-rank matrix approximation in the infinity norm”, Linear Algebra and its Applications, 581:15 (2019), 367–382 | DOI | MR | Zbl

[12] A. Panyukov, K. Chaloob, Y. Mezal, “Approximation of a matrix with positive elements by a matrix of a unit rank”, 2018 IEEE Symposium on Computer Applications and Industrial Electronics, ISCAIE, IEEE, 2018, 234–237 | DOI

[13] N. K. Krivulin, E. Yu. Romanova, “Rank-one approximation of positive matrices based on methods of tropical mathematics”, Vestnik Saint Petersburg University. Mathematics, 51:2 (2018), 133–143 | DOI | MR | Zbl

[14] N. K. Krivulin, E. Yu. Romanova, “On the rank-one approximation of positive matrices using tropical optimization methods”, Vestnik Saint Petersburg University. Mathematics, 52:2 (2019), 145–153 | DOI | MR | Zbl

[15] Maslov V. P., Kolokol'tsov V. N., Idempotent analysis and its applications in optimal control, Fizmatlit Publ., M., 1994, 144 pp. (In Russian) | MR

[16] B. Heidergott, G. J. Olsder, J. van der Woude, Max Plus at work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 2006, 226 pp. | MR | Zbl

[17] W. M. McEneaney, Max-plus methods for nonlinear control and estimation, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 2006, 241 pp. | DOI | MR | Zbl

[18] Krivulin N. K., Methods of idempotent algebra for problems in modeling and analysis of complex systems, Saint Petersburg University Press, Saint Petersburg, 2009, 256 pp. (In Russian)

[19] P. Butkovič, Max-linear systems, Springer Monographs in Mathematics, Springer, London, 2010, 272 pp. | DOI | MR | Zbl

[20] N. Krivulin, “A constrained tropical optimization problem: Complete solution and application example”, Tropical and Idempotent Mathematics and Applications, Contemporary Mathematics, 616, AMS, Providence, 2014, 163–177 | DOI | MR | Zbl

[21] N. Krivulin, “Tropical optimization problems”, Advances in Economics and Optimization, Economic Issues, Problems and Perspectives, Nova Science Publ., New York, 2014, 195–214 | MR

[22] N. Krivulin, “Extremal properties of tropical eigenvalues and solutions to tropical optimization problems”, Linear Algebra and its Applications, 468 (2015), 211–232 | DOI | MR | Zbl

[23] N. Krivulin, “A multidimensional tropical optimization problem with nonlinear objective function and linear constraints”, Optimization, 64:5 (2015), 1107–1129 | DOI | MR | Zbl