Il teorema di Sinkhorn

Il teorema di Sinkhorn Il teorema di Sinkhorn afferma che ogni matrice quadrata con elementi positivi può essere scritta in una certa forma standard.

Contenuti 1 Teorema 2 Algoritmo Sinkhorn-Knopp 3 Analoghi ed estensioni 4 Applicazioni 5 Riferimenti Teorema Se A è una matrice n × n con elementi strettamente positivi, allora esistono matrici diagonali D1 e D2 con elementi diagonali strettamente positivi tali che D1AD2 è doppiamente stocastico. Le matrici D1 e D2 sono modulo unico moltiplicando la prima matrice per un numero positivo e dividendo la seconda per lo stesso numero.[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 e Knopp hanno presentato questo algoritmo e ne hanno analizzato la convergenza.[3] Questo è essenzialmente lo stesso dell'algoritmo di adattamento proporzionale iterativo, ben noto nelle statistiche dei sondaggi.

Analogues and extensions The following analogue for unitary matrices is also true: per ogni matrice unitaria U esistono due matrici unitarie diagonali L e R tali che LUR abbia ciascuna delle sue colonne e righe sommate a 1.[4] Vale anche la seguente estensione alle mappe tra matrici (vedi Teorema 5[5] e anche Teorema 4.7[6]): dato un operatore di Kraus che rappresenta l'operazione quantistica Φ che mappa una matrice di densità in un'altra, {displaystyle Smapsto Phi (S)=somma _{io}B_{io}SB_{io}^{*},} cioè preservare le tracce, {somma dello stile di visualizzazione _{io}B_{io}^{*}B_{io}= io,} e, Inoltre, la cui estensione è all'interno del cono definito positivo (rigorosa positività), esistono ridimensionamenti xj, per j in {0,1}, che sono definiti positivi in ​​modo che l'operatore Kraus ridimensionato {displaystyle Smapsto x_{1}Phi (X_{0}^{-1}Sx_{0}^{-1})X_{1}=somma _{io}(X_{1}B_{io}X_{0}^{-1})S(X_{1}B_{io}X_{0}^{-1})^{*}} è doppiamente stocastico. In altre parole, è tale che entrambi, {stile di visualizzazione x_{1}Phi (X_{0}^{-1}Ix_{0}^{-1})X_{1}= io,} così come per l'aggiuntivo, {stile di visualizzazione x_{0}^{-1}Phi^{*}(X_{1}Ix_{1})X_{0}^{-1}= io,} dove I denota l'operatore di identità.

Applications In the 2010s Sinkhorn's theorem came to be used to find solutions of entropy-regularised optimal transport problems.[7] Questo è stato di interesse per l'apprendimento automatico perché tale "Distanze di sinkhorn" può essere utilizzato per valutare la differenza tra le distribuzioni e le permutazioni dei dati.[8][9][10] Ciò migliora la formazione degli algoritmi di apprendimento automatico, in situazioni in cui l'allenamento con la massima verosimiglianza potrebbe non essere il metodo migliore.

Riferimenti ^ Sinkhorn, Richard. (1964). "Una relazione tra matrici positive arbitrarie e matrici doppiamente stocastiche." Anna. Matematica. Statista. 35, 876–879. doi:10.1214/aoms/1177703591 ^ Marshall, A.W., & Olkin, io. (1967). "Ridimensionamento delle matrici per ottenere somme di righe e colonne specificate." matematica numerica. 12(1), 83–90. doi:10.1007/BF02170999 ^ Sinkhorn, Richard, & Knopp, Paolo. (1967). "Per quanto riguarda le matrici non negative e le matrici doppiamente stocastiche". Pacifico J. Matematica. 21, 343–348. ^ Ideale, Martino; Lupo, Michele M. (2015). "Forma normale di sinkhorn per matrici unitarie". Algebra lineare e sue applicazioni. 471: 76–84. arXiv:1408.5728. doi:10.1016/j.laa.2014.12.031. ^ Georgiou, Trifone; tacchino, Michele (2015). "Mappature di contrazione positiva per sistemi di Schrödinger classici e quantistici". Giornale di fisica matematica. 56: 033301-1-24. arXiv:1405.6650. Bibcode:2015JMP....56c3301G. doi:10.1063/1.4915289. ^ Gurvit, Leonide (2004). "Complessità classica e entanglement quantistico". Giornale di scienze computazionali. 69: 448–484. doi:10.1016/j.jcss.2004.06.003. ^ Scatole, Marco (2013). "Distanze di sinkhorn: Calcolo della velocità della luce del trasporto ottimale". Progressi nei sistemi neurali di elaborazione delle informazioni. pp. 2292–2300. ^ Mensch, Arthur e Blondel, Mathieu e Peyre, Gabriele (2019). "Perdite geometriche per l'apprendimento distributivo". Proc ICML 2019. ^ Mena, Gonzalo e Belanger, David e Munoz, Gonzalo e Pike, Diaspro (2017). "Reti di sinkhorn: Utilizzo di tecniche di trasporto ottimali per apprendere le permutazioni". Workshop NIPS in trasporto ottimale e apprendimento automatico. ^ Kogkalidis, Costantino e Moortgat, Michael e Moot, Richard (2020). "Reti di prova neurale". Atti del 24° Convegno sull'apprendimento computazionale delle lingue naturali. Categorie: Teoremi delle matrici nell'algebra lineare