Satz von Sinkhorn

Der Satz von Sinkhorn Der Satz von Sinkhorn besagt, dass jede quadratische Matrix mit positiven Einträgen in einer bestimmten Standardform geschrieben werden kann.

Inhalt 1 Satz 2 Sinkhorn-Knopp-Algorithmus 3 Analoga und Erweiterungen 4 Anwendungen 5 Referenzen Theorem Wenn A eine n × n-Matrix mit strikt positiven Elementen ist, dann gibt es Diagonalmatrizen D1 und D2 mit streng positiven Diagonalelementen, so dass D1AD2 doppelt stochastisch ist. Die Matrizen D1 und D2 sind eindeutig Modulo, indem die erste Matrix mit einer positiven Zahl multipliziert und die zweite durch dieselbe Zahl dividiert wird.[1] [2] Sinkhorn–Knopp algorithm A simple iterative method to approach the double stochastic matrix is to alternately rescale all rows and all columns of A to sum to 1. Sinkhorn und Knopp stellten diesen Algorithmus vor und analysierten seine Konvergenz.[3] Dies ist im Wesentlichen dasselbe wie der iterative proportionale Anpassungsalgorithmus, in Umfragestatistiken bekannt.

Analogues and extensions The following analogue for unitary matrices is also true: Für jede Einheitsmatrix U gibt es zwei diagonale Einheitsmatrizen L und R, so dass LUR jede seiner Spalten und Zeilen summiert 1.[4] Die folgende Erweiterung auf Abbildungen zwischen Matrizen ist ebenfalls wahr (siehe Satz 5[5] und auch Satz 4.7[6]): Bei gegebenem Kraus-Operator, der die Quantenoperation Φ darstellt, die eine Dichtematrix in eine andere abbildet, {displaystyle Smapsto Phi (S)= Summe _{ich}B_{ich}SB_{ich}^{*},} das ist spurenerhaltend, {Anzeigestil Summe _{ich}B_{ich}^{*}B_{ich}= Ich,} und, zusätzlich, dessen Reichweite im Inneren des positiv bestimmten Kegels liegt (strikte Positivität), es existieren Skalierungen xj, für j ein {0,1}, die positiv definit sind, so dass der umskalierte Kraus-Operator {Anzeigestil Smapsto x_{1}Phi (x_{0}^{-1}Sx_{0}^{-1})x_{1}= Summe _{ich}(x_{1}B_{ich}x_{0}^{-1})S(x_{1}B_{ich}x_{0}^{-1})^{*}} ist doppelt stochastisch. Mit anderen Worten, es ist so, dass beides, {Anzeigestil x_{1}Phi (x_{0}^{-1}Ix_{0}^{-1})x_{1}= Ich,} sowie für den Adjunkten, {Anzeigestil x_{0}^{-1}Phi^{*}(x_{1}Ix_{1})x_{0}^{-1}= Ich,} wobei I den Identitätsoperator bezeichnet.

Applications In the 2010s Sinkhorn's theorem came to be used to find solutions of entropy-regularised optimal transport problems.[7] Dies war für das maschinelle Lernen von Interesse, da z "Sinkhorn-Entfernungen" kann verwendet werden, um den Unterschied zwischen Datenverteilungen und Permutationen auszuwerten.[8][9][10] Dies verbessert das Training von maschinellen Lernalgorithmen, in Situationen, in denen Maximum-Likelihood-Training möglicherweise nicht die beste Methode ist.

Referenzen ^ Sinkhorn, Richard. (1964). "Eine Beziehung zwischen beliebigen positiven Matrizen und doppelt stochastischen Matrizen." Ann. Mathematik. Statist. 35, 876–879. doi:10.1214/aoms/1177703591 ^ Marshall, AW, & Olkin, ich. (1967). "Skalierung von Matrizen, um bestimmte Zeilen- und Spaltensummen zu erreichen." Numerische Mathematik. 12(1), 83–90. doi:10.1007/BF02170999 ^ Sinkhorn, Richard, & Knopp, Paul. (1967). "Über nichtnegative Matrizen und doppelt stochastische Matrizen". Pazifik J. Mathematik. 21, 343–348. ^ Optimal, Martin; Wolf, Michael M. (2015). "Sinkhorn-Normalform für unitäre Matrizen". Lineare Algebra und ihre Anwendungen. 471: 76–84. arXiv:1408.5728. doi:10.1016/j.laa.2014.12.031. ^ Georgiou, Tryphon; Truthahn, Michèle (2015). "Positive Kontraktionsabbildungen für klassische und Quanten-Schrödinger-Systeme". Zeitschrift für Mathematische Physik. 56: 033301-1-24. arXiv:1405.6650. Bibcode:2015JMP....56c3301G. doi:10.1063/1.4915289. ^ Gurvits, Leonid (2004). "Klassische Komplexität und Quantenverschränkung". Zeitschrift für Computerwissenschaften. 69: 448–484. doi:10.1016/j.jcss.2004.06.003. ^ Kästen, Marco (2013). "Sinkhorn-Entfernungen: Lichtgeschwindigkeitsberechnung des optimalen Transports". Fortschritte bei neuronalen Informationsverarbeitungssystemen. pp. 2292–2300. ^ Mensch, Arthur und Blondel, Mathieu und Peyre, Gabriel (2019). "Geometrische Verluste für verteiltes Lernen". Proc ICML 2019. ^ Mena, Gonzalo und Belanger, David und Munoz, Gonzalo und Hecht, Jaspis (2017). "Sinkhorn-Netzwerke: Verwendung optimaler Transporttechniken zum Erlernen von Permutationen". NIPS-Workshop zu optimalem Transport und maschinellem Lernen. ^ Kogkalidis, Konstantinos und Moortgat, Michael und Moot, Richard (2020). "Neuronale Proof-Netze". Proceedings of the 24th Conference on Computational Natural Language Learning. Kategorien: MatrixtheorieSätze in der linearen Algebra