A discrete method for the initialization of semi-discrete optimal transport problem

摘要

Semi-discrete optimal transport setting is a very important formulation in the computation of Wasserstein distance, as it is an approximation form of the continuous setting of optimal transport. However, initialization process of dual weight vector for the dual problem in this setting is required for the computation of the first and second order methods, since the Laguerre cells associated to the dual weight vector ought to have positive mass during the calculation. Although there are approaches to initialize the weight vector, systematic computing procedure has not been available. To resolve this problem, we discretize the domain of source distribution of this problem, approximate the Laguerre cells with respect to the weight vector, and finally employ the local perturbation method (Jocelyn, 2019) combined with boundary method to force all measures of the Laguerre cells great than zero. In addition, we study the corresponding theoretical results of the computation process and provide the algorithm, ensuring that the problem can indeed be efficiently computed.