The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:353

Article

Dieci, Luca¹  Walsh, J. D., III² 

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Naval Surface Warfare Ctr, Panama City Div X24, 110 Vernon Ave, Panama City, FL 32407 USA

关键词: Optimal transport;    Monge-Kantorovich;    Semi-discrete;    Wasserstein distance;    Boundary method;   

DOI  :  10.1016/j.cam.2018.12.034

来源: Elsevier

【 摘 要 】

We introduce a new technique, which we call the boundary method, for solving semi discrete optimal transport problems with a wide range of cost functions. The boundary method reduces the effective dimension of the problem, thus improving complexity. For cost functions equal to a p-norm with p is an element of (1, infinity), we provide mathematical justification, convergence analysis, and algorithmic development. Our testing supports the boundary method with these p-norms, as well as other, more general cost functions. Published by Elsevier B.V.

【 授权许可】

Free