Using tropical optimization in rank-one approximation of positive matrices

Research output

1 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages30-30
Publication statusPublished - Jun 2018
EventThe 6th IMA Conference on Numerical Linear Algebra and Optimization - University of Birmingham, Birmingham
Duration: 27 Jun 201829 Jun 2018
https://ima.org.uk/7149/6thimanlao/

Conference

ConferenceThe 6th IMA Conference on Numerical Linear Algebra and Optimization
CountryUnited Kingdom
CityBirmingham
Period27/06/1829/06/18
Internet address

Fingerprint

Positive Matrices
Approximation Problem
Optimization
Approximation
Max-algebra
Row vector
Column vector
Semifield
Nonnegative Matrices
Chebyshev
Best Approximation
Minimax
Nonlinear Function
Idempotent
Logarithmic
Computational Complexity
Optimization Problem
Closed

Scopus subject areas

  • Algebra and Number Theory
  • Control and Optimization

Cite this

Кривулин, Н. К. (2018). Using tropical optimization in rank-one approximation of positive matrices. 30-30. Abstract from The 6th IMA Conference on Numerical Linear Algebra and Optimization, Birmingham, .
Кривулин, Николай Кимович. / Using tropical optimization in rank-one approximation of positive matrices. Abstract from The 6th IMA Conference on Numerical Linear Algebra and Optimization, Birmingham, .
@conference{1994fe012caa4c268ec1b52f5d4cd060,
title = "Using tropical optimization in rank-one approximation of positive matrices",
abstract = "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.",
author = "Кривулин, {Николай Кимович}",
note = "The 6th IMA Conference on Numerical Linear Algebra and Optimization. Wednesday 27 - Friday 29 June 2018, University of Birmingham, UK. Abstracts Book. Institute of Mathematics and its Applications. P. 30.; The 6th IMA Conference on Numerical Linear Algebra and Optimization ; Conference date: 27-06-2018 Through 29-06-2018",
year = "2018",
month = "6",
language = "English",
pages = "30--30",
url = "https://ima.org.uk/7149/6thimanlao/",

}

Using tropical optimization in rank-one approximation of positive matrices. / Кривулин, Николай Кимович.

2018. 30-30 Abstract from The 6th IMA Conference on Numerical Linear Algebra and Optimization, Birmingham, .

Research output

TY - CONF

T1 - Using tropical optimization in rank-one approximation of positive matrices

AU - Кривулин, Николай Кимович

N1 - The 6th IMA Conference on Numerical Linear Algebra and Optimization. Wednesday 27 - Friday 29 June 2018, University of Birmingham, UK. Abstracts Book. Institute of Mathematics and its Applications. P. 30.

PY - 2018/6

Y1 - 2018/6

N2 - 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.

AB - 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.

M3 - Abstract

SP - 30

EP - 30

ER -

Кривулин НК. Using tropical optimization in rank-one approximation of positive matrices. 2018. Abstract from The 6th IMA Conference on Numerical Linear Algebra and Optimization, Birmingham, .