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

Research output

Abstract

Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for approximate solution of some equations in mechanics, and in other fields. In the paper, a method for approximating positive matrices by matrices of unit rank is proposed on the basis of minimization of log-Chebyshev distance. The approximation problem is reduced to an optimization problem that has a compact representation in terms of an idempotent semifield that uses the operation of taking maximum in the role of addition, and is often called the 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 derived. Using methods and results of tropical optimization, all the positive matrices which provide the minimum of approximation error are obtained in explicit form. A numerical example that illustrates the application of the proposed rank-one approximation method is considered.
Original languageRussian
Pages (from-to)256-269
Number of pages14
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Volume5 (63)
Issue number2
Publication statusPublished - 2018

Fingerprint

Positive Matrices
mathematics
Max-algebra
Matrix Approximation
Low-rank Approximation
Low-rank Matrices
Semifield
Recommendation System
Approximation Problem
Approximation Error
Approximation
matrices
Chebyshev
approximation
Approximation Methods
Idempotent
optimization
Mechanics
Approximate Solution
Optimization Problem

Scopus subject areas

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

Cite this

@article{23af32c255d14bf99b2364159afc87f5,
title = "Одноранговая аппроксимация положительных матриц на основе методов тропической математики",
abstract = "Малоранговая аппроксимация матриц находит широкое применение при анализе больших данных, в рекомендательных системах в сети Интернет, для приближенного решения некоторых уравнений механики и в других областях. В статье предлагается метод аппроксимации положительных матриц матрицами единичного ранга на основе минимизации log-чебышёвского расстояния. Задача аппроксимации сводится к задаче оптимизации, имеющей компактное представление в терминах идемпотентного полуполя с операцией вычисления максимума в роли сложения, которое часто называют max-алгеброй. Приводятся необходимые определения и предварительные результаты из области тропической математики, на основе которых строится решение исходной задачи. С помощью применения методов и результатов тропической оптимизации находятся в явном виде все положительные матрицы, на которых достигается минимум погрешности аппроксимации. Рассматривается численный пример, иллюстрирующий применение предложенного метода одноранговой аппроксимации.",
keywords = "tropical mathematics, idempotent semifield, rank-one matrix approximation, log-Chebyshev distance, тропическая математика, идемпотентное полуполе, одноранговая аппроксимация матриц, log-чебышёвская функция расстояния",
author = "Кривулин, {Николай Кимович} and Романова, {Елизавета Юрьевна}",
year = "2018",
language = "русский",
volume = "5 (63)",
pages = "256--269",
journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",
issn = "1025-3106",
publisher = "Издательство Санкт-Петербургского университета",
number = "2",

}

TY - JOUR

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

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

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

PY - 2018

Y1 - 2018

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

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

KW - tropical mathematics

KW - idempotent semifield

KW - rank-one matrix approximation

KW - log-Chebyshev distance

KW - тропическая математика

KW - идемпотентное полуполе

KW - одноранговая аппроксимация матриц

KW - log-чебышёвская функция расстояния

M3 - статья

VL - 5 (63)

SP - 256

EP - 269

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 2

ER -