Teorema de Sinkhorn

Cada matriz cuadrada con entradas positivas se puede escribir en una determinada forma estándar.

El teorema de Sinkhorn establece que toda matriz cuadrada con entradas positivas se puede escribir en una determinada forma estándar.

Teorema

Si A es una matriz n × n con elementos estrictamente positivos, entonces existen matrices diagonales D ₁ y D ₂ con elementos diagonales estrictamente positivos tales que D ₁ AD ₂ es doblemente estocástica . Las matrices D ₁ y D ₂ son módulo único multiplicando la primera matriz por un número positivo y dividiendo la segunda por el mismo número. ^{[1] [2]}

Algoritmo de Sinkhorn-Knopp

Un método iterativo simple para abordar la matriz estocástica doble es reescalar alternativamente todas las filas y todas las columnas de A para sumar 1. Sinkhorn y Knopp presentaron este algoritmo y analizaron su convergencia. ^[3] Esto es esencialmente lo mismo que el algoritmo de ajuste proporcional iterativo , bien conocido en las estadísticas de encuestas.

Análogos y extensiones.

La siguiente analogía para las matrices unitarias también es cierta: para cada matriz unitaria U existen dos matrices unitarias diagonales L y R tales que LUR tiene cada una de sus columnas y filas sumando 1. ^[4]

La siguiente extensión a aplicaciones entre matrices también es cierta (ver Teorema 5 ^[5] y también Teorema 4.7 ^[6] ): dado un operador de Kraus que representa la operación cuántica Φ mapeando una matriz de densidad en otra,

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

eso es preservar rastros,

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

y, además, cuyo rango está en el interior del cono definido positivo (positividad estricta), existen escalamientos x _j , para j en {0,1}, que son definidos positivos de modo que el operador Kraus reescalado

${\displaystyle 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})^{*}}$

es doblemente estocástico. En otras palabras, es tal que ambos,

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

así como para el adjunto,

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

donde I denota el operador de identidad.

Aplicaciones

En la década de 2010, el teorema de Sinkhorn empezó a utilizarse para encontrar soluciones a problemas de transporte óptimo regularizados por entropía . ^[7] Esto ha sido de interés en el aprendizaje automático porque estas "distancias de Sinkhorn" se pueden utilizar para evaluar la diferencia entre distribuciones y permutaciones de datos. ^{[8] [9] [10]} Esto mejora el entrenamiento de algoritmos de aprendizaje automático, en situaciones en las que el entrenamiento de máxima probabilidad puede no ser el mejor método.

Referencias

1. Cuerno de fregadero, Richard. (1964). "Una relación entre matrices positivas arbitrarias y matrices doblemente estocásticas". Ana. Matemáticas. Estadístico. 35 , 876–879. doi :10.1214/aoms/1177703591
2. Marshall, AW y Olkin, I. (1967). "Escalado de matrices para lograr sumas de filas y columnas específicas". Matemática numérica . 12(1) , 83–90. doi :10.1007/BF02170999
3. Sinkhorn, Richard y Knopp, Paul. (1967). "Sobre matrices no negativas y matrices doblemente estocásticas". Pacífico J. Matemáticas. 21 , 343–348.
4. Idel, Martín; Lobo, Michael M. (2015). "Forma normal de Sinkhorn para matrices unitarias". Álgebra lineal y sus aplicaciones . 471 : 76–84. arXiv : 1408.5728 . doi :10.1016/j.laa.2014.12.031. S2CID  119175915.
5. Georgiou, Trifón; Pavón, Michele (2015). "Mapeos de contracción positiva para sistemas de Schrödinger clásicos y cuánticos". Revista de Física Matemática . 56 (3): 033301–1–24. arXiv : 1405.6650 . Código Bib : 2015JMP....56c3301G. doi : 10.1063/1.4915289. S2CID  119707158.
6. Gurvits, Leonid (2004). "Complejidad clásica y entrelazamiento cuántico". Revista de ciencia computacional . 69 (3): 448–484. doi : 10.1016/j.jcss.2004.06.003 .
7. Cuturi, Marco (2013). "Distancias de Sinkhorn: cálculo de la velocidad de la luz del transporte óptimo". Avances en los sistemas de procesamiento de información neuronal . págs. 2292-2300.
8. Mensch, Arturo; Blondel, Mathieu; Peyre, Gabriel (2019). "Pérdidas geométricas para el aprendizaje distributivo". Proceso ICML 2019 . arXiv : 1905.06005 .
9. Mena, Gonzalo; Belanger, David; Muñoz, Gonzalo; Snoek, Jasper (2017). "Redes Sinkhorn: uso de técnicas de transporte óptimas para aprender permutaciones". Taller NIPS en Transporte Óptimo y Aprendizaje Automático .
10. Kogkalidis, Konstantinos; Moortgat, Michael; Discutible, Richard (2020). "Redes a prueba de neuronas". Actas de la 24ª Conferencia sobre aprendizaje computacional de lenguajes naturales .