Satz von Sinkhorn

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

Ist A eine n × n- _Matrix mit ausschließlich positiven Elementen, so existieren Diagonalmatrizen D₁ und D₂ mit ausschließlich positiven Diagonalelementen, sodass _D₁AD₂ doppelt stochastisch ist . Die Matrizen _D₁ und _{D₂ sind bis auf Multiplikation der} ^ersten Matrix mit einer positiven Zahl und Division der zweiten durch dieselbe Zahl ^{eindeutig .} [ ¹ ] ^{[ 2} _]

Ein einfaches iteratives Verfahren zur Annäherung an die doppelte stochastische Matrix besteht darin, abwechselnd alle Zeilen und Spalten von A so zu skalieren , dass ihre Summe 1 ergibt. Sinkhorn und Knopp stellten diesen Algorithmus vor und analysierten seine Konvergenz. ^{[ 3 ]} Dies entspricht im Wesentlichen dem in der Umfragestatistik wohlbekannten iterativen proportionalen Anpassungsalgorithmus.

Das folgende Analogon für unitäre Matrizen gilt ebenfalls: Zu jeder unitären Matrix U existieren zwei diagonale unitäre Matrizen L und R, so dass LUR die Summe ihrer Spalten und Zeilen jeweils 1 ergibt. ^{[ 4 ]}

Die folgende Erweiterung auf Abbildungen zwischen Matrizen gilt ebenfalls (siehe Satz 5 ^{[ 5 ]} und auch Satz 4.7 ^{[ 6 ]} ): Gegeben sei ein Kraus-Operator , der die Quantenoperation Φ darstellt, die eine Dichtematrix in eine andere abbildet,

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

das ist spurenerhaltend,

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

und darüber hinaus existieren Skalierungen x_{_j} , für j ∈ {0,1}, deren Wertebereich im Inneren des positiv definiten Kegels liegt (strikte Positivität), die positiv definit sind, sodass der reskalierte Kraus-Operator

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

ist doppelt stochastisch. Anders ausgedrückt: Es ist so beschaffen, dass sowohl

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

sowie für die Adjungierte,

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

wobei I den Identitätsoperator bezeichnet.

In den 2010er Jahren wurde das Sinkhorn-Theorem zur Lösung von entropieregularisierten optimalen Transportproblemen eingesetzt . ^{[ 7 ]} Dies ist im Bereich des maschinellen Lernens von Interesse , da solche „Sinkhorn-Distanzen“ zur Bewertung der Unterschiede zwischen Datenverteilungen und Permutationen verwendet werden können. ^{[ 8 ] [ 9 ] [ 10 ]} Dadurch wird das Training von Algorithmen des maschinellen Lernens in Situationen verbessert, in denen das Training mittels Maximum-Likelihood- Schätzung nicht die beste Methode darstellt.