Teorema de Sinkhorn

Teorema de Sinkhorn O teorema de Sinkhorn afirma que toda matriz quadrada com entradas positivas pode ser escrita em uma certa forma padrão.

Conteúdo 1 Teorema 2 Algoritmo Sinkhorn-Knopp 3 Análogos e extensões 4 Formulários 5 Teorema das Referências Se A é uma matriz n × n com elementos estritamente positivos, então existem matrizes diagonais D1 e D2 com elementos diagonais estritamente positivos tais que D1AD2 é duplamente estocástico. As matrizes D1 e D2 são módulos únicos multiplicando a primeira matriz por um número positivo e dividindo a segunda pelo mesmo número.[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 apresentaram esse algoritmo e analisaram sua convergência.[3] Isso é essencialmente o mesmo que o algoritmo de ajuste proporcional iterativo, bem conhecido em estatísticas de pesquisa.

Analogues and extensions The following analogue for unitary matrices is also true: para cada matriz unitária U existem duas matrizes unitárias diagonais L e R tais que LUR tem cada uma de suas colunas e linhas somando a 1.[4] A seguinte extensão para mapas entre matrizes também é verdadeira (ver Teorema 5[5] e também teorema 4.7[6]): dado um operador de Kraus que representa a operação quântica Φ mapeando uma matriz de densidade em outra, {estilo de exibição Smapsto Phi (S)=soma _{eu}B_{eu}SB_{eu}^{*},} isso é preservar vestígios, {soma de estilo de exibição _{eu}B_{eu}^{*}B_{eu}=eu,} e, além do que, além do mais, cujo alcance está no interior do cone positivo definido (positividade estrita), existem escalas xj, para j em {0,1}, que são definidos positivos para que o operador de Kraus reescalonado {estilo de exibição Smapsto x_{1}Phi (x_{0}^{-1}Sx_{0}^{-1})x_{1}=soma _{eu}(x_{1}B_{eu}x_{0}^{-1})S(x_{1}B_{eu}x_{0}^{-1})^{*}} é duplamente estocástico. Em outras palavras, é tal que ambos, {estilo de exibição x_{1}Phi (x_{0}^{-1}Ix_{0}^{-1})x_{1}=eu,} bem como para o adjunto, {estilo de exibição x_{0}^{-1}Phi^{*}(x_{1}Ix_{1})x_{0}^{-1}=eu,} onde I denota o operador identidade.

Applications In the 2010s Sinkhorn's theorem came to be used to find solutions of entropy-regularised optimal transport problems.[7] Isso tem sido de interesse em aprendizado de máquina porque tais "Distâncias Sinkhorn" pode ser usado para avaliar a diferença entre distribuições de dados e permutações.[8][9][10] Isso melhora o treinamento de algoritmos de aprendizado de máquina, em situações em que o treinamento de máxima probabilidade pode não ser o melhor método.

Referências ^ Sinkhorn, Ricardo. (1964). "Uma relação entre matrizes positivas arbitrárias e matrizes duplamente estocásticas." Ana. Matemática. Estatista. 35, 876–879. doi:10.1214/aoms/1177703591 ^ Marshall, A. W., & Olkin, EU. (1967). "Dimensionamento de matrizes para obter somas de linhas e colunas especificadas." matemática numérica. 12(1), 83-90. doi:10.1007/BF02170999 ^ Sinkhorn, Ricardo, & Knopp, Paulo. (1967). "Sobre matrizes não negativas e matrizes duplamente estocásticas". Pacific J. Matemática. 21, 343-348. ^ Ideal, Martinho; Lobo, Michael M. (2015). "Forma normal Sinkhorn para matrizes unitárias". Álgebra Linear e suas Aplicações. 471: 76-84. arXiv:1408.5728. doi:10.1016/j.laa.2014.12.031. ^ Georgiou, Tryphon; peru, Michele (2015). "Mapeamentos de contração positiva para sistemas de Schrödinger clássicos e quânticos". Revista de Física Matemática. 56: 033301-1-24. arXiv:1405.6650. Bibcode:2015JMP....56c3301G. doi:10.1063/1.4915289. ^ Gurvits, Leonid (2004). "Complexidade clássica e emaranhamento quântico". Revista de Ciência da Computação. 69: 448-484. doi:10.1016/j.jcss.2004.06.003. ^ Caixas, Marco (2013). "Distâncias Sinkhorn: Computação da velocidade da luz do transporte ideal". Avanços em sistemas de processamento de informação neural. pp. 2292–2300. ^ Mensch, Arthur e Blondel, Mathieu e Peyre, Gabriel (2019). "Perdas geométricas para aprendizagem distributiva". Processo ICML 2019. ^ Mena, Gonzalo e Belanger, Davi e Muñoz, Gonzalo e Pike, Jaspe (2017). "Redes Sinkhorn: Usando técnicas de transporte ideais para aprender permutações". Workshop NIPS em Transporte Ótimo e Aprendizado de Máquina. ^ Kogkalidis, Konstantinos e Moortgat, Michael e Moot, Ricardo (2020). "Redes de Prova Neural". Anais da 24ª Conferência sobre Aprendizagem Computacional de Línguas Naturais. Categorias: Teoria de matrizesTeoremas em álgebra linear