Bao Han, Sakaue Shinsaku
Graduate School of Informatics and The Hakubi Center for Advanced Research, Kyoto University, Kyoto 604-8103, Japan.
Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 153-8505, Japan.
Entropy (Basel). 2022 Nov 10;24(11):1634. doi: 10.3390/e24111634.
Optimal transport is a mathematical tool that has been a widely used to measure the distance between two probability distributions. To mitigate the cubic computational complexity of the vanilla formulation of the optimal transport problem, regularized optimal transport has received attention in recent years, which is a convex program to minimize the linear transport cost with an added convex regularizer. Sinkhorn optimal transport is the most prominent one regularized with negative Shannon entropy, leading to densely supported solutions, which are often undesirable in light of the interpretability of transport plans. In this paper, we report that a deformed entropy designed by , a popular generalization of the standard algebra studied in Tsallis statistical mechanics, makes optimal transport solutions supported sparsely. This entropy with a deformation parameter interpolates the negative Shannon entropy (q=1) and the squared 2-norm (q=0), and the solution becomes more sparse as tends to zero. Our theoretical analysis reveals that a larger leads to a faster convergence when optimized with the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. In summary, the deformation induces a trade-off between the sparsity and convergence speed.
最优传输是一种数学工具，已被广泛用于测量两个概率分布之间的距离。为了减轻最优传输问题原始形式的立方计算复杂度，近年来正则化最优传输受到了关注，它是一个凸规划，通过添加凸正则化项来最小化线性传输成本。Sinkhorn最优传输是用负香农熵正则化的最突出的一种，它会导致密集支持的解，从传输计划的可解释性来看，这些解通常是不理想的。在本文中，我们报告了由Tsallis统计力学中研究的标准代数的一种流行推广所设计的变形熵，它能使最优传输解得到稀疏支持。这种具有变形参数q的熵在负香农熵（q = 1）和平方2 - 范数（q = 0）之间进行插值，并且当q趋于零时，解会变得更加稀疏。我们的理论分析表明，当使用布罗伊登 - 弗莱彻 - 戈德法布 - 香农（BFGS）算法进行优化时，较大的q会导致更快的收敛。总之，这种变形在稀疏性和收敛速度之间引发了一种权衡。
