On rank-one approximation of positive matrices using methods of tropical optimization

Authors

  • Nikolai K. Krivulin
  • Elizaveta Yu. Romanova

Abstract

In the paper, an approach to the problem of rank-one approximation of positive matrices in the Chebyshev metric in logarithmic scale is developed based on the application of methods of tropical optimization. The theory and methods of tropical optimization constitute one of the areas of tropical mathematics that deals with semirings and semifields with idempotent addition and their applications. For many practically important problems, methods of tropical optimization allow finding a complete solution explicitly in a closed form. In this work, the approximation problem under consideration is reduced to multidimensional tropical optimization problem, which has a known solution in the general case. A new solution to the problem in the case when the matrix has no zero columns or rows is proposed and represented in a more simple form. On the basis of this result, a new complete solution of the problem of rank-one approximation of positive matrices is developed. To illustrate the results obtained, an example of the solution of the approximation problem for an arbitrary positive matrix of the second order is given in analytical form.

Downloads

Download data is not yet available.

References

1. Yao Q., Kwok J. Greedy learning of generalized low-rank models // Proc. 25th Intern. JointConf. on Artificial Intelligence (IJCAI’16). AAAI Press, 2016. P. 2294–2300.

2. Elden L. Numerical linear algebra in data mining // Acta Numer. 2006. Vol. 15. P. 327–384.https://doi.org/10.1017/S0962492906240017

3. Ruhe A. Numerical computation ofprincipal components when several observations are missing.Research report. Umea Univ., 1974.

4. Friedland S., Mehrmann V., Miedlar A., Nkengla M. Fast low rank approximations of matricesand tensors // Electron. J. Linear Algebra. 2011. Vol. 22. P. 1031–1048. https://doi.org/10.13001/1081-3810.1489

5. Koyuturk M., Grama A., Ramakrishnan N. Compression, clustering, and pattern discovery invery high-dimensional discrete-attribute data sets // IEEE Trans. Knowledge Data Eng. 2005. Vol. 17,N 4. P. 447–461. https://doi.org/10.1109/TKDE.2005.55Вестник СПбГУ. Математика. Механика. Астрономия. 2019. Т.6(64). Вып.2 2176. Kumar N. K., Schneider J. Literature survey on low rank approximation of matrices // LinearMultilinear Algebra. 2017. Vol. 65, N 11. P. 2212–2244 https://doi.org/10.1080/03081087.2016.1267104

6. Kumar N. K., Schneider J. Literature survey on low rank approximation of matrices // Linear Multilinear Algebra. 2017. Vol. 65, N 11. P. 2212–2244 https://doi.org/10.1080/03081087.2016.1267104

7. Gillis N. Introduction to nonnegative matrix factorization//SIAG/OPTViewsandNews.2017.Vol. 25, N 1. P. 7–16.

8. Aissa-El-Bey A., Seghouane K. Sparse canonical correlation analysis based on rank-1 matrix approximation and its application for FMR Isignals//2016IEEEIntern.Conf.onAcoustics,SpeechandSignal Processing (ICASSP). IEEE, 2016. P. 4678–4682. https://doi.org/10.1109/ICASSP.2016.7472564

9. Саати Т. Принятие решений. Метод анализа иерархий / пер. с англ. Р.Г.Вачнадзе. М.:Радио и связь, 1993. 315 c.

10. Luss R., Teboulle M. Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint // SIAM Review. 2013. Vol. 55, N 1. P. 65–98. https://doi.org/10.1137/110839072

11. Shi Z., Wang L., Shi L. Approximation method to rank-one binary matrix factorization// IEEE Intern. Conf. on Automation Science and Engineering (CASE). IEEE, 2014. P. 800–805.https://doi.org/10.1109/CoASE.2014.6899417

12. Gillis N., Shitov Y. Low-rank matrix approximation in the infinity norm//Computing Research Repository. 2017. arXiv:1706.00078.

13. Кривулин Н.К. Методы и демпотентной алгебры в задачах моделирования и анализа сложных систем. СПб: Изд-во С.-Петерб. ун-та, 2009.

14. Krivulin N. Rating alternatives from pairwise comparisons by solving tropical optimizationproblems // 12th Intern. Conference on Fuzzy Systems and Knowledge Discovery (FSKD). IEEE, 2015.P. 162–167. https://doi.org/10.1109/FSKD.2015.7381933

15. Krivulin N. Using tropical optimization techniques to evaluateal ternatives viapairwise comparisons // 2016 Proc. 7th SIAM Workshop on Combinatorial Scientific Computing. Philadelphia: SIAM,2016. P. 62–72. https://doi.org/10.1137/1.9781611974690.ch7

16. Krivulin N.K., Romanova E.Yu. Rank-one approximation ofpositivematrices based onmeth-ods of tropical mathematics // Vestnik St. Petersburg Univ. Math. 2018. Vol. 51, N 2. P. 133–143.https://doi.org/10.3103/S106345411802005X

17. Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144 с.

18. Butkoviˇc P. Max-linear systems. In Ser.: Springer Monographs in Mathematics. London:Springer, 2010. https://doi.org/10.1007/978-1-84996-299-5

19. McEneaney W.M. Max-Plus Methods for Nonlinear Control and Estimation. In Ser.: Systemsand Control: Foundations and Applications. Boston: Birkh¨auser, 2006. https://doi.org/10.1007/0-8176-4453-9

20. Krivulin N. Tropical optimization problems // In: Advances in Economics and Optimization(Economic Issues, Problems and Perspectives). New York: Nova Sci. Publ., 2014. P. 195–214.

21. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimizationproblems // Linear Algebra Appl. 2015. Vol. 468. P. 211–232. https://doi.org/10.1016/j.laa.2014.06.044

22. Krivulin N. Tropical optimization problems in time-constrained project scheduling // Optimization. 2017. Vol. 66, N 2. P. 205–224. https://doi.org/10.1080/02331934.2016.1264946

23. Krivulin N.K. An extremal property of the eigenvalue of irreducible matrices in idempotentalgebra andsolutionofthe Rawlslocation problem//VestnikSt. Petersburg Univ.Math. 2011. Vol.44,N 4. P. 272–281. https://doi.org/10.3103/S1063454111040078

Downloads

Published

2020-08-17

How to Cite

Krivulin, N. K., & Romanova, E. Y. (2020). On rank-one approximation of positive matrices using methods of tropical optimization. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 6(2), 208–220. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/8412

Issue

Vol. 6 No. 2 (2019)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.