Using tropical optimization in rank-one approximation of positive matrices

Результат исследований: Материалы конференцийтезисы

1 Загрузки (Pure)

Аннотация

We apply methods of tropical optimization to approximate matrices with positive entries by matrices of rank one. We consider the approximating matrices as factored into column and row vectors, and formulate the problem to find the pair of vectors, which provide the best approximation of a given matrix in the Chebyshev (minimax) sense in logarithmic scale. Both problems of unconstrained approximation, and problems with constraints imposed on the vectors, are under consideration. We represent the approximation problems in the tropical mathematics setting as optimization problems to find the minimum of a non-linear function defined on vectors over the max-algebra idempotent semifield. To solve the problems obtained, we apply recent results in tropical optimization, which offer direct complete solutions. These results serve as the basis to derive solutions to the approximation problems in question in a compact closed vector form. We discuss the computational complexity of the solutions, and the extension of the approach to solve approximation problems for non-negative matrices.

This work was supported by the Russian Foundation for Basic Research, grant No. 18-010-00723.
Язык оригиналаанглийский
Страницы30-30
СостояниеОпубликовано - июн 2018
СобытиеThe 6th IMA Conference on Numerical Linear Algebra and Optimization - University of Birmingham, Birmingham, Великобритания
Продолжительность: 27 июн 201829 июн 2018
https://ima.org.uk/7149/6thimanlao/

Конференция

КонференцияThe 6th IMA Conference on Numerical Linear Algebra and Optimization
СтранаВеликобритания
ГородBirmingham
Период27/06/1829/06/18
Адрес в сети Интернет

    Fingerprint

Предметные области Scopus

  • Алгебра и теория чисел
  • Теория оптимизации

Цитировать

Кривулин, Н. К. (2018). Using tropical optimization in rank-one approximation of positive matrices. 30-30. Выдержка из The 6th IMA Conference on Numerical Linear Algebra and Optimization, Birmingham, Великобритания.