Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster
in
Workshop: OPT 2022: Optimization for Machine Learning

Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm

Yiling Xie · Yiling Luo · Xiaoming Huo


Abstract: We observe that 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 between marginals with m and n atoms (mn), the computational complexity of the proposed algorithm is O(m2n). Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where we have m=n2. The associate computational complexity of our algorithm is O(n5), while the order of applying the classic Hungarian algorithm is O(n6). Numerical experiments validate our theoretical analysis. Broader applications of the proposed algorithm are discussed at the end.

Chat is not available.