On Sinkhorn’s Algorithm and Choice Modeling
建立了Luce选择模型与矩阵平衡问题之间的广泛联系，利用这些联系解决了非负矩阵Sinkhorn算法收敛性的开放问题，刻画了全局线性收敛速度并推导了渐近速率。
On Sinkhorn’s Algorithm and Choice Modeling Choice modeling is an important topic that underlies a wide range of applications involving human decision making, and it traces its roots to the 1920s. Matrix balancing has an equally long history and wide applicability (e.g., in transportation and mobility networks). Recently, its celebrated Sinkhorn’s algorithm has been instrumental in the efficient approximation of optimal transport distances. However, the two topics have largely developed independently. In “On Sinkhorn’s Algorithm and Choice Modeling,” Qu, Galichon, Gao, and Ugander establish extensive connections between a class of Luce choice models and a common matrix-balancing problem. They leverage these connections to resolve open problems on the convergence of Sinkhorn’s algorithm for nonnegative matrices, characterizing its global linear convergence rate in terms of the algebraic connectivity and deriving the sharp asymptotic rate. The connections established in this paper between two seemingly unrelated topics help the transmission of ideas and lead to further interesting results.