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 1 y D 2 con elementos diagonales estrictamente positivos tales que D 1 AD 2 es doblemente estocástica . Las matrices D 1 y D 2 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,
Esto es preservar el rastro,
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
es doblemente estocástica. En otras palabras, es tal que tanto,
así como para el adjunto,
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
- ^ 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
- ^ 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
- ^ Sinkhorn, Richard y Knopp, Paul (1967). "Sobre matrices no negativas y matrices doblemente estocásticas". Pacific J. Math. 21 , 343–348.
- ^ 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.
- ^ 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.
- ^ 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 .
- ^ 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.
- ^ Mensch, Arthur; Blondel, Mathieu; Peyre, Gabriel (2019). "Pérdidas geométricas para el aprendizaje distributivo". Proc ICML 2019 . arXiv : 1905.06005 .
- ^ 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 .
- ^ Kogkalidis, Konstantinos; Moortgat, Michael; Moot, Richard (2020). "Redes de prueba neuronales". Actas de la 24.ª Conferencia sobre aprendizaje computacional del lenguaje natural .