Теорема Синкхорна

Теорема Синкхорна утверждает, что каждую квадратную матрицу с положительными элементами можно записать в определенной стандартной форме.

Теорема

Если A — размера n × n матрица со строго положительными элементами, то существуют диагональные матрицы D ₁ и D ₂ со строго положительными диагональными элементами такие, что D ₁ AD ₂ является дважды стохастической . Матрицы D ₁ и D ₂ уникальны по модулю умножения первой матрицы на положительное число и деления второй на то же число.

Алгоритм Синкхорна – Кноппа

Простой итерационный метод приближения к двойной стохастической матрице состоит в поочередном масштабировании всех строк и всех столбцов A до суммы, равной 1. Синкхорн и Кнопп представили этот алгоритм и проанализировали его сходимость. По сути, это то же самое, что итеративный алгоритм пропорциональной аппроксимации , хорошо известный в статистике опросов.

Аналоги и расширения

Верен также следующий аналог для унитарных матриц: для каждой унитарной матрицы U существуют две диагональные унитарные матрицы L и R такие, что LUR равна 1. сумма всех столбцов и строк

Верно также следующее расширение на отображения между матрицами (см. теорему 5 а также теорема 4.7 ): с учетом оператора Крауса которая представляет собой квантовую операцию Φ, отображающую одну матрицу плотности в другую,

$S\mapsto \Phi (S)=\sum _{i}B_{i}SB_{i}^{*},$

это сохранение следов,

$\sum _{i}B_{i}^{*}B_{i}=I,$

и, кроме того, чей диапазон находится внутри положительно определенного конуса (строгая положительность), существуют масштабирования x _j для j в {0,1}, которые являются положительно определенными, так что перемасштабированный оператор Крауса

$S\mapsto x_{1}\Phi (x_{0}^{-1}Sx_{0}^{-1})x_{1}=\sum _{i}(x_{1}B_{i}x_{0}^{-1})S(x_{1}B_{i}x_{0}^{-1})^{*}$

является вдвойне стохастическим. Другими словами, ситуация такова, что оба,

$x_{1}\Phi (x_{0}^{-1}Ix_{0}^{-1})x_{1}=I,$

а также для сопряженного,

$x_{0}^{-1}\Phi ^{*}(x_{1}Ix_{1})x_{0}^{-1}=I,$

где I обозначает тождественный оператор.

Приложения

В 2010-х годах теорема Синкхорна стала использоваться для поиска решений энтропийно-регуляризованных задач оптимального транспорта . Это представляет интерес для машинного обучения , поскольку такие «расстояния Синхорна» можно использовать для оценки разницы между распределениями данных и перестановками. Это улучшает обучение алгоритмов машинного обучения в ситуациях, когда обучение методом максимального правдоподобия может быть не лучшим методом.