Одноранговая аппроксимация положительных матриц на основе методов тропической математики
Аннотация
Малоранговая аппроксимация матриц находит широкое применение при анализе больших данных, в рекомендательных системах в сети Интернет, для приближенного решения некоторых уравнений механики и в других областях. В статье предлагается метод аппроксимации положительных матриц матрицами единичного ранга на основе минимизации log-чебышёвского расстояния. Задача аппроксимации сводится к задаче оптимизации, имеющей компактное представление в терминах идемпотентного полуполя с операцией вычисления максимума в роли сложения, которое часто называют max-алгеброй. Приводятся необходимые определения и предварительные результаты из области тропической математики, на основе которых строится решение исходной задачи. С помощью применения методов и результатов тропической оптимизации находятся в явном виде все положительные матрицы, на которых достигается минимум погрешности аппроксимации. Рассматривается численный пример, иллюстрирующий применение предложенного метода одноранговой аппроксимации.
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
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
Загрузки
Опубликован
19.08.2020
Как цитировать
Кривулин, Н. К., & Романова, Е. Ю. (2020). Одноранговая аппроксимация положительных матриц на основе методов тропической математики. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 5(2), 256–269. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8520
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
