Computing empirical Wasserstein distance in the independence test is an optimal transport (OT) problem with a special structure. This observation inspires us to study a special type of OT problem and propose a modified Hungarian algorithm to solve it exactly. For an OT problem involving two marginals with $m$ and $n$ atoms ($m\geq n$), respectively, the computational complexity of the proposed algorithm is $O(m^2n)$. Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where $m=n^2$. The associated computational complexity of the proposed algorithm is $O(n^5)$, while the order of applying the classic Hungarian algorithm is $O(n^6)$. In addition to the aforementioned special type of OT problem, it is shown that the modified Hungarian algorithm could be adopted to solve a wider range of OT problems. Broader applications of the proposed algorithm are discussed -- solving the one-to-many and the many-to-many assignment problems. Numerical experiments are conducted to validate our theoretical results. The experiment results demonstrate that the proposed modified Hungarian algorithm compares favorably with the Hungarian algorithm and the well-known Sinkhorn algorithm.
翻译：独立测试中的算法瓦瑟斯坦距离是一个特殊结构的最佳运输(OT)问题。 这一观察激励我们研究一种特殊类型的OT问题,并提出一个修改的匈牙利算法来确切地解决这个问题。对于一个分别涉及两边的OT问题,分别涉及美元和美元原子(m\geq n$)的OT问题,拟议算法的计算复杂性为$O(m%2n)美元。计算独立测试中的经验瓦瑟斯坦距离需要解决这一特殊类型的OT问题,即$m=n%2$。拟议算法的相关计算复杂性是$O(n)5美元,而应用经典匈牙利算法的顺序是$O(n)6美元。除了上述特殊类型的OT问题外,还表明,修改后的匈牙利算法可以用来解决更广泛的OT问题。讨论拟议的算法的更广泛应用 -- 解决一对一和多对多任务分配问题。正在进行纳米实验,以验证我们的理论结果。实验结果是,应用经典的匈牙利算法的顺序是$(n_6美元)。 实验结果表明,拟议的匈牙利变的顺的匈牙利算法和高的匈牙利算法。
相关内容
微信扫码咨询专知VIP会员