Одноранговая аппроксимация положительных матриц на основе методов тропической математики

Nikolai K. Krivulin; Elizaveta Yu. Romanova

Authors

Nikolai K. Krivulin
Elizaveta Yu. Romanova

Abstract

Малоранговая аппроксимация матриц находит широкое применение при анализе больших данных, в рекомендательных системах в сети Интернет, для приближенного решения некоторых уравнений механики и в других областях. В статье предлагается метод аппроксимации положительных матриц матрицами единичного ранга на основе минимизации log-чебышёвского расстояния. Задача аппроксимации сводится к задаче оптимизации, имеющей компактное представление в терминах идемпотентного полуполя с операцией вычисления максимума в роли сложения, которое часто называют max-алгеброй. Приводятся необходимые определения и предварительные результаты из области тропической математики, на основе которых строится решение исходной задачи. С помощью применения методов и результатов тропической оптимизации находятся в явном виде все положительные матрицы, на которых достигается минимум погрешности аппроксимации. Рассматривается численный пример, иллюстрирующий применение предложенного метода одноранговой аппроксимации.

Downloads

Download data is not yet available.

References

1. Соловьев С.А. Решение разреженных систем линейных уравнений методом Гаусса с использованием техники аппроксимации матрицами малого ранга // Выч. мет. программирование. 2014. Т. 15, №3. С. 441-460.

2. Воронин К.В., Соловьев С.А. Решение уравнения Гельмгольца с использованием метода малоранговой аппроксимации в качестве предобуславливателя // Выч. мет. программирование. 2015. Т. 16, №2. С. 268-280.

3. Lee J., Kim S., Lebanon G., Singer Y. Local low-rank matrix approximation // Proc. 30th Intern. Conf. on Machine Learning, Atlanta, Georgia, USA. 2013. P. 82-90.

4. Lee J., Bengio S., Kim S. et al. Local collaborative ranking // Proc. 23rd Intern. Conf. on World Wide Web (WWW'14), April 7-11, 2014, Seoul, Korea. ACM. 2014. P. 85-96. DOI: 10.1145/2566486.2567970

5. Savas B. Algorithms in data mining using matrix and tensor methods // Link¨oping Studies in Science and Technology: Dissertations, Vol. 1178. Link¨oping Univ. Tech. 2008. 138 p.

6. Ispany M., Michaletzky G., Reiczigel J. et al. Approximation of non-negative integer-valued matrices with application to Hungarian mortality data // Proc. 19th Intern. Symp. on Mathematical Theory of Networks and Systems (MTNS 2010), 5-9 July, 2010, Budapest, Hungary. P. 831-838.

7. Тыртышников Е.Е. Матрицы, тензоры, вычисления. Учебный курс. М.: МГУ им. М. В.Ломоносова, 2013.

8. Wang H., Ahuja N. A tensor approximation approach to dimensionality reduction // Int. J. Comput. Vis. 2008. Vol. 76, N 3. P. 217-229. DOI: 10.1007/s11263-007-0053-0

9. Yao Q., Kwok J. Greedy learning of generalized low-rank models // Proc. 25th Intern. Joint Conf. on Artificial Intelligence (IJCAI'16), New York, 2016. AAAI Press. 2016. P. 2294-2300.

10. Шлянников А.В. Алгоритм восстановления трехмерной модели лица по фотографии // Научно-технический вестник ИТМО. 2010. Т. 69, №5. С. 86-90.

11. Aissa-El-Bey A., Seghouane K. Sparse canonical correlation analysis based on rank-1 matrix approximation and its application for FMRI signals // 2016 IEEE Intern. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Shanghai, China. IEEE. 2016. P. 4678-4682. DOI: 10.1109/ICASSP.2016.7472564

12. 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. DOI: 10.1137/110839072

13. Friedland S., Mehrmann V., Pajarola R., Suter S.K. On best rank one approximation of tensors // Numer. Linear Algebra Appl. 2013. Vol. 20, N 6. P. 942-955. DOI: 10.1002/nla.1878

14. da Silva A. P., Comon P., de Almeida A. L.F. Rank-1 tensor approximation methods and application to deflation. Research report. GIPSA-lab, 2015.

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

16. Shen H., Huang J. Sparse principal component analysis via regularized low rank matrix approximation // J. Multivariate Anal. 2008. Vol. 99, N 6. P. 1015-1034. DOI: 10.1016/j.jmva.2007.06.007

17. Zi¸etak K. The Chebyshev approximation of a rectangular matrix by matrices of smaller rank as the limit of lp-approximation // J. Comput. Appl. Math. 1984. Vol. 11. P. 297-305. (84)90004-9 DOI: 10.1016/0377-0427

18. Boyd S., Vandenberghe L. Convex optimization. Cambridge: Cambridge Univ. Press, 2004.

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

20. Lobo M. S., Vandenberghe L., Boyd S., Lebret H. Applications of second-order cone programming // Linear Algebra Appl. 1998. Vol. 284. P. 193-228. (98)10032-0 DOI: 10.1016/S0024-3795

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

22. Krivulin N. Using tropical optimization techniques to evaluate alternatives via pairwise comparisons // 2016 Proc. 7th SIAM Workshop on Combinatorial Scientific Computing. Philadelphia: SIAM, 2016. P. 62-72. DOI: 10.1137/1.9781611974690.ch7

23. Кривулин Н.К., Агеев В.А., Гладких И.В. Применение методов тропической оптимизации для оценки альтернатив на основе парных сравнений // Вестник С-Петерб. ун-та. Прикладная математика. Информатика. Процессы управления. 2017. Т. 13. Вып. 1. С. 27-41. DOI: 10.21638/11701/spbu10.2017.103

24. Krivulin N.K. Eigenvalues and eigenvectors of matrices in idempotent algebra // Vestnik St. Petersburg Univ. Math. 2006. Vol. 39, N 2. P. 72-83.

25. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems // Linear Algebra Appl. 2015. Vol. 468. P. 211-232. DOI: 10.1016/j.laa.2014.06.044

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

27. Pin J.-E. Tropical semirings // Idempotency / ed. by J. Gunawardena. Cambridge: Cambridge Univ. Press, 1998. P. 50-69.

28. Литвинов Г.Л., Маслов В.П., Соболевский А.Н. Идемпотентная математика и интервальный анализ // Вычислительные технологии. 2001. Т. 6, №6. С. 47-70.

29. Butkovic P. Max-linear systems. In: Springer Monographs in Mathematics. London: Springer, 2010. 272 p. DOI: 10.1007/978-1-84996-299-5