Théorème de Sinkhorn

Le théorème de Sinkhorn Le théorème de Sinkhorn stipule que chaque matrice carrée avec des entrées positives peut être écrite sous une certaine forme standard.

Contenu 1 Théorème 2 Algorithme Sinkhorn-Knopp 3 Analogues et extensions 4 Applications 5 Références Théorème Si A est une matrice n × n à éléments strictement positifs, alors il existe des matrices diagonales D1 et D2 à éléments diagonaux strictement positifs telles que D1AD2 est doublement stochastique. Les matrices D1 et D2 sont uniques modulo en multipliant la première matrice par un nombre positif et en divisant la seconde par le même nombre.[1] [2] Algorithme Sinkhorn – Knopp Une méthode itérative simple pour approcher la double matrice stochastique consiste à redimensionner alternativement toutes les lignes et toutes les colonnes de A pour additionner à 1. Sinkhorn et Knopp ont présenté cet algorithme et analysé sa convergence.[3] Ceci est essentiellement le même que l'algorithme d'ajustement proportionnel itératif, bien connu dans les statistiques d'enquête.

Analogues et extensions L'analogue suivant pour les matrices unitaires est également vrai: pour chaque matrice unitaire U, il existe deux matrices unitaires diagonales L et R telles que LUR a chacune de ses colonnes et lignes sommant à 1.[4] L'extension suivante aux cartes entre matrices est également vraie (voir Théorème 5[5] et aussi théorème 4.7[6]): étant donné un opérateur de Kraus qui représente l'opération quantique Φ cartographier une matrice de densité dans une autre, {style d'affichage Smapsto Phi (S)=somme _{je}B_{je}SB_{je}^{*},} qui préserve les traces, {somme de style d'affichage _{je}B_{je}^{*}B_{je}=je,} et, en outre, dont la portée est à l'intérieur du cône défini positif (positivité stricte), il existe des échelles xj, pour j dans {0,1}, qui sont définies positives de sorte que l'opérateur de Kraus remis à l'échelle {style d'affichage Smapsto x_{1}Phi (X_{0}^{-1}Sx_{0}^{-1})X_{1}=somme _{je}(X_{1}B_{je}X_{0}^{-1})S(X_{1}B_{je}X_{0}^{-1})^{*}} est doublement stochastique. Autrement dit, il est tel que les deux, {style d'affichage x_{1}Phi (X_{0}^{-1}Ix_{0}^{-1})X_{1}=je,} ainsi que pour l'adjoint, {style d'affichage x_{0}^{-1}Phi ^{*}(X_{1}Ix_{1})X_{0}^{-1}=je,} où je désigne l'opérateur d'identité.

Applications Dans les années 2010, le théorème de Sinkhorn a été utilisé pour trouver des solutions aux problèmes de transport optimal régularisés par l'entropie.[7] Cela a été intéressant pour l'apprentissage automatique parce que de tels "Distances du gouffre" peut être utilisé pour évaluer la différence entre les distributions de données et les permutations.[8][9][10] Cela améliore la formation des algorithmes d'apprentissage automatique, dans des situations où l'entraînement à probabilité maximale n'est peut-être pas la meilleure méthode.

Références ^ Sinkhorn, Richard. (1964). "Une relation entre des matrices positives arbitraires et des matrices doublement stochastiques." Anne. Math. Statiste. 35, 876–879. est ce que je:10.1214/aoms/1177703591 ^ Marshall, A. W., & Olkin, je. (1967). "Mise à l'échelle des matrices pour obtenir des sommes de lignes et de colonnes spécifiées." Mathématiques numériques. 12(1), 83–90. est ce que je:10.1007/BF02170999 ^ Corne d'évier, Richard, & Knopp, Paul. (1967). "Concernant les matrices non négatives et les matrices doublement stochastiques". Pacifique J. Math. 21, 343–348. ^ Idéal, Martin; Loup, Michel M. (2015). "Forme normale Sinkhorn pour les matrices unitaires". Algèbre linéaire et ses applications. 471: 76–84. arXiv:1408.5728. est ce que je:10.1016/j.laa.2014.12.031. ^ Georgiou, Tryphon; dinde, Michèle (2015). "Cartographies de contraction positive pour les systèmes de Schrödinger classiques et quantiques". Journal de physique mathématique. 56: 033301-1-24. arXiv:1405.6650. Code bib:2015JMP....56c3301G. est ce que je:10.1063/1.4915289. ^ Gourvits, Léonid (2004). "Complexité classique et intrication quantique". Journal des sciences informatiques. 69: 448–484. est ce que je:10.1016/j.jcss.2004.06.003. ^ Boîtes, Marco (2013). "Distances du gouffre: Calcul à la vitesse de la lumière du transport optimal". Progrès dans les systèmes de traitement de l'information neuronale. pp. 2292–2300. ^ Mensch, Arthur et Blondel, Mathieu et Peyré, gabriel (2019). "Pertes géométriques pour l'apprentissage distributionnel". Procédure ICML 2019. ^ Ména, Gonzalo et Bélanger, David et Munoz, Gonzalo et Pike, Jaspe (2017). "Réseaux de puits: Utiliser des techniques de transport optimales pour apprendre les permutations". Atelier NIPS sur le transport optimal et l'apprentissage automatique. ^ Kogkalis, Konstantinos et Moortgat, Michael et Moot, Richard (2020). "Réseaux à l'épreuve des neurones". Actes de la 24e conférence sur l'apprentissage informatique des langues naturelles. Catégories: Théorie des matricesThéorèmes en algèbre linéaire