1 Citation (Scopus)

Abstract

Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for the approximate solution of some equations of mechanics, and in other fields. In this paper, a method for approximating positive matrices by rank-one matrices on the basis of minimization of log-Chebyshev distance is proposed. The problem of approximation reduces to an optimization problem having a compact representation in terms of an idempotent semifield in which the operation of taking the maximum plays the role of addition and which is often referred to as max-algebra. The necessary definitions and preliminary results of tropical mathematics are given, on the basis of which the solution of the original problem is constructed. Using the methods and results of tropical optimization, all positive matrices at which the minimum of approximation error is reached are found in explicit form. A numerical example illustrating the application of the rank-one approximation is considered.
Original languageEnglish
Pages (from-to)133-143
Number of pages11
JournalVestnik St. Petersburg University: Mathematics
Volume51
Issue number2
Early online date16 Jun 2018
DOIs
Publication statusPublished - 2018

Fingerprint

Positive Matrices
Max-algebra
Matrix Approximation
Low-rank Approximation
Low-rank Matrices
Semifield
Recommendation System
Approximation Error
Approximation
Chebyshev
Idempotent
Mechanics
Approximate Solution
Optimization Problem
Numerical Examples
Necessary
Optimization
Mathematics
Form

Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Algebra and Number Theory

Cite this

@article{22d1cfd644dc43b196a5b443552061f7,
title = "Rank-one approximation of positive matrices based on methods of tropical mathematics",
abstract = "Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for the approximate solution of some equations of mechanics, and in other fields. In this paper, a method for approximating positive matrices by rank-one matrices on the basis of minimization of log-Chebyshev distance is proposed. The problem of approximation reduces to an optimization problem having a compact representation in terms of an idempotent semifield in which the operation of taking the maximum plays the role of addition and which is often referred to as max-algebra. The necessary definitions and preliminary results of tropical mathematics are given, on the basis of which the solution of the original problem is constructed. Using the methods and results of tropical optimization, all positive matrices at which the minimum of approximation error is reached are found in explicit form. A numerical example illustrating the application of the rank-one approximation is considered.",
keywords = "tropical mathematics, idempotent semifield, rank-one matrix approximation, log-Chebyshev distance function",
author = "Кривулин, {Николай Кимович} and Романова, {Елизавета Юрьевна}",
year = "2018",
doi = "10.3103/S106345411802005X",
language = "English",
volume = "51",
pages = "133--143",
journal = "Vestnik St. Petersburg University: Mathematics",
issn = "1063-4541",
publisher = "Pleiades Publishing",
number = "2",

}

TY - JOUR

T1 - Rank-one approximation of positive matrices based on methods of tropical mathematics

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

AU - Романова, Елизавета Юрьевна

PY - 2018

Y1 - 2018

N2 - Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for the approximate solution of some equations of mechanics, and in other fields. In this paper, a method for approximating positive matrices by rank-one matrices on the basis of minimization of log-Chebyshev distance is proposed. The problem of approximation reduces to an optimization problem having a compact representation in terms of an idempotent semifield in which the operation of taking the maximum plays the role of addition and which is often referred to as max-algebra. The necessary definitions and preliminary results of tropical mathematics are given, on the basis of which the solution of the original problem is constructed. Using the methods and results of tropical optimization, all positive matrices at which the minimum of approximation error is reached are found in explicit form. A numerical example illustrating the application of the rank-one approximation is considered.

AB - Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for the approximate solution of some equations of mechanics, and in other fields. In this paper, a method for approximating positive matrices by rank-one matrices on the basis of minimization of log-Chebyshev distance is proposed. The problem of approximation reduces to an optimization problem having a compact representation in terms of an idempotent semifield in which the operation of taking the maximum plays the role of addition and which is often referred to as max-algebra. The necessary definitions and preliminary results of tropical mathematics are given, on the basis of which the solution of the original problem is constructed. Using the methods and results of tropical optimization, all positive matrices at which the minimum of approximation error is reached are found in explicit form. A numerical example illustrating the application of the rank-one approximation is considered.

KW - tropical mathematics

KW - idempotent semifield

KW - rank-one matrix approximation

KW - log-Chebyshev distance function

U2 - 10.3103/S106345411802005X

DO - 10.3103/S106345411802005X

M3 - Article

VL - 51

SP - 133

EP - 143

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -