Teorema de Sinkhorn

Toda 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 puede escribirse 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 únicas módulo 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 que sumen 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

El siguiente análogo para matrices unitarias también es cierto: 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 los mapas entre matrices también es verdadera (ver Teorema 5 ^[5] y también Teorema 4.7 ^[6] ): dado un operador de Kraus que representa la operación cuántica Φ que mapea una matriz de densidad en otra,

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

Esto es preservar el rastro,

${\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 de 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ástica. En otras palabras, es tal que tanto,

${\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 identidad.

Aplicaciones

En la década de 2010, el teorema de Sinkhorn comenzó 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 de datos y permutaciones. ^{[8] [9] [10]} Esto mejora el entrenamiento de algoritmos de aprendizaje automático, en situaciones en las que el entrenamiento de máxima verosimilitud puede no ser el mejor método.

Referencias

1. Sinkhorn, Richard. (1964). "Una relación entre matrices positivas arbitrarias y matrices doblemente estocásticas". Ann. Math. Statist. 35 , 876–879. doi :10.1214/aoms/1177703591
2. Marshall, AW y Olkin, I. (1967). "Escalamiento de matrices para lograr sumas de filas y columnas específicas". Numerische Mathematik . 12(1) , 83–90. doi :10.1007/BF02170999
3. Sinkhorn, Richard y Knopp, Paul (1967). "Sobre matrices no negativas y matrices doblemente estocásticas". Pacific J. Math. 21 , 343–348.
4. Idel, Martin; Wolf, 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, Tryphon; Pavon, Michele (2015). "Asignaciones de contracción positiva para sistemas de Schrödinger clásicos y cuánticos". Journal of Mathematical Physics . 56 (3): 033301–1–24. arXiv : 1405.6650 . Código Bibliográfico :2015JMP....56c3301G. doi :10.1063/1.4915289. S2CID  119707158.
6. Gurvits, Leonid (2004). "Complejidad clásica y entrelazamiento cuántico". Revista de Ciencias Computacionales . 69 (3): 448–484. doi : 10.1016/j.jcss.2004.06.003 .
7. Cuturi, Marco (2013). "Distancias de Sinkhorn: cálculo a la velocidad de la luz del transporte óptimo". Avances en sistemas de procesamiento de información neuronal . págs. 2292–2300.
8. Mensch, Arthur; Blondel, Mathieu; Peyre, Gabriel (2019). "Pérdidas geométricas para el aprendizaje distributivo". Proc ICML 2019 . arXiv : 1905.06005 .
9. Mena, Gonzalo; Belanger, David; Munoz, Gonzalo; Snoek, Jasper (2017). "Redes Sinkhorn: Uso de técnicas de transporte óptimo para aprender permutaciones". Taller NIPS sobre transporte óptimo y aprendizaje automático .
10. Kogkalidis, Konstantinos; Moortgat, Michael; Moot, Richard (2020). "Redes de prueba neuronales". Actas de la 24.ª Conferencia sobre aprendizaje computacional del lenguaje natural .