Twierdzenie Sinkhorna

Twierdzenie Sinkhorna stwierdza, że ​​każdą macierz kwadratową z wpisami dodatnimi można zapisać w określonej postaci standardowej.

Twierdzenie

Jeśli A jest macierzą n × n ze ściśle dodatnimi elementami, to istnieją macierze diagonalne D ₁ i D ₂ ze ściśle dodatnimi elementami diagonalnymi, takie że D ₁ AD ₂ jest podwójnie stochastyczna . Macierze D ₁ i D ₂ są unikalne modulo mnożąc pierwszą macierz przez liczbę dodatnią i dzieląc drugą przez tę samą liczbę.

Algorytm Sinkhorna-Knoppa

Prostą iteracyjną metodą podejścia do podwójnej macierzy stochastycznej jest naprzemienne przeskalowanie wszystkich wierszy i wszystkich kolumn A w celu zsumowania do 1. Sinkhorn i Knopp przedstawili ten algorytm i przeanalizowali jego zbieżność. Zasadniczo jest to to samo, co iteracyjny algorytm dopasowywania proporcjonalnego , dobrze znany w statystykach ankietowych.

Analogi i rozszerzenia

Następująca analogia dla macierzy unitarnych jest również prawdziwa: dla każdej macierzy unitarnej U istnieją dwie diagonalne macierze unitarne L i R takie, że LUR ma sumę każdej kolumny i wiersza do 1.

Prawdziwe jest również następujące rozszerzenie odwzorowań między macierzami (patrz Twierdzenie 5, a także Twierdzenie 4.7): biorąc pod uwagę operator Krausa , który reprezentuje operację kwantową Φ odwzorowującą macierz gęstości na inną,

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

czyli zachowanie śladów,

${\ Displaystyle \ suma _ {i} B_ {i} ^ {*} B_ {i} = ja,}$

a ponadto, którego zakres znajduje się we wnętrzu dodatnio określonego stożka (ścisła pozytywność), istnieją skalowania x _j , dla j w {0,1}, które są dodatnio określone, tak że przeskalowany operator Krausa

${\ Displaystyle S \ mapsto x_ {1} \ Phi (x_{0}^{-1}Sx_{0}^{-1})x_{1}=\suma _{i}(x_{1}B_{i}x_{0}^{-1} )S(x_{1}B_{i}x_{0}^{-1})^{*}}$

jest podwójnie stochastyczny. Innymi słowy, jest tak, że zarówno

${\ Displaystyle x_ {1} \ Phi (x_ {0} ^ {-1} Ix_ {0} ^ {- 1}) x_ {1} = ja,}$

jak również dla sąsiednich,

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

gdzie I oznacza operatora tożsamości.

Aplikacje

W 2010 roku twierdzenie Sinkhorna zaczęto wykorzystywać do znajdowania rozwiązań problemów transportu optymalnego z regulacją entropii . Było to interesujące w uczeniu maszynowym , ponieważ takie „odległości Sinkhorn” można wykorzystać do oceny różnicy między rozkładami danych a permutacjami. Poprawia to szkolenie algorytmów uczenia maszynowego w sytuacjach, w których z maksymalnym prawdopodobieństwem może nie być najlepszą metodą.