跳至內容

辛克宏定理[編輯]

維基百科,自由的百科全書

辛克宏定理(英語:Sinkhorn's theorem)是線性代數中的一個定理,指所有元素為正的方塊矩陣都可以寫成一個正對角矩陣、一個雙隨機矩陣英語Doubly stochastic matrix與另一個正對角矩陣之積的形式。

定理

[編輯]

如果是所有元素都嚴格為正的矩陣,則存在元素嚴格為正的對角矩陣,使得是雙隨機矩陣,即每一行或列之和均為1。矩陣在前者乘以一個正數、後者除以相同正數的情況下是唯一的。[1][2]

辛克宏-諾普算法

[編輯]

一個逼近雙隨機矩陣的簡單迭代方法是交替地縮放中所有行與列的比例,使其元素之和為1。辛克宏和諾普(Knopp)提出了該算法並分析了其收斂性。這一算法與調查統計學中的迭代比例擬合英語Iterative proportional fitting本質上相同。

擴展

[編輯]

酉矩陣中存在類似的結論:對於任意酉矩陣,都存在兩個對角酉矩陣,使得的每一列和每一行的元素之和均為1。[3]

對矩陣間映射也有類似的擴展結論[4][5]:給定一個克勞斯(Kraus)算子表示將一個密度矩陣映射到另一個密度矩陣的量子操作,即

其滿足跡不變

並且其範圍在正定錐內部(嚴格正定)。在此條件下,存在正定的縮放因子),使得縮放後的克勞斯算子

是雙隨機的,即

其中表示恆等算子。

應用

[編輯]

2010年代,辛克宏定理開始被用於求解熵正則化的最優傳輸問題。[6]這一方法在機器學習領域引起了關注,因為由此得到的辛克宏距離(Sinkhorn distance)可用於評估數據分布之間的差異。[7][8][9]在一些最大似然訓練效果不佳的情況下,這種方法可以改進機器學習算法的訓練效果。

參考文獻

[編輯]
  1. ^ Sinkhorn, Richard. (1964). "A relationship between arbitrary positive matrices and doubly stochastic matrices." Ann. Math. Statist. 35, 876–879. doi:10.1214/aoms/1177703591
  2. ^ Marshall, A.W., & Olkin, I. (1967). "Scaling of matrices to achieve specified row and column sums." Numerische Mathematik. 12(1), 83–90. doi:10.1007/BF02170999
  3. ^ Idel, Martin; Wolf, Michael M. Sinkhorn normal form for unitary matrices. Linear Algebra and Its Applications. 2015, 471: 76–84. S2CID 119175915. arXiv:1408.5728可免費查閱. doi:10.1016/j.laa.2014.12.031. 
  4. ^ Georgiou, Tryphon; Pavon, Michele. Positive contraction mappings for classical and quantum Schrödinger systems. Journal of Mathematical Physics. 2015, 56 (3): 033301–1–24. Bibcode:2015JMP....56c3301G. S2CID 119707158. arXiv:1405.6650可免費查閱. doi:10.1063/1.4915289. 
  5. ^ Gurvits, Leonid. Classical complexity and quantum entanglement. Journal of Computational Science. 2004, 69 (3): 448–484. doi:10.1016/j.jcss.2004.06.003可免費查閱. 
  6. ^ Cuturi, Marco. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems: 2292–2300. 2013. 
  7. ^ Mensch, Arthur; Blondel, Mathieu; Peyre, Gabriel. Geometric losses for distributional learning. Proc ICML 2019. 2019. arXiv:1905.06005可免費查閱. 
  8. ^ Mena, Gonzalo; Belanger, David; Munoz, Gonzalo; Snoek, Jasper. Sinkhorn networks: Using optimal transport techniques to learn permutations. NIPS Workshop in Optimal Transport and Machine Learning. 2017. 
  9. ^ Kogkalidis, Konstantinos; Moortgat, Michael; Moot, Richard. Neural Proof Nets. Proceedings of the 24th Conference on Computational Natural Language Learning. 2020.