טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentTenetov Evgeny
SubjectTopics in Semi-Discrete Optimal Transport
DepartmentDepartment of Applied Mathematics
Supervisor Professor Gershon Wolansky


Abstract

The optimal transport theory has various applications in PDE, fluid dynamics, probability and many other fields in mathematics as well as in computer science and economics. In the last years, the interest for optimal transport theory in the fields of data science, machine learning and image processing has grown tremendously. Hence efficient computation of the optimal transport distance, also known as the earth mover’s distance (EMD), has become an area of active study.


This thesis deals with semi-discrete approaches for solving the optimal transport problem as well as related problems. It consists of two main parts. In the first part we propose an extension of the classical semi-discrete approach. We discretize the cost function itself, rather than one of the measures. The resulting problem has a dual formulation which converts the optimization to a convex optimization on a smaller dimension space which allows efficient calculation. The costs which we can handle include costs of the form c(x, y) = d(x, y)p , where p ≥ 1 and d is the geodesic distance on a Riemannian manifold.


We also generalize this approach to vector valued measures and to the unbalanced transport case. Applications of vector-valued optimal transport may include optimal matching of colored images, as well as modular merging of images.


The second part of the thesis deals with the entropic regularized version of the optimal transport distance. Under entropy regularization, optimal transportation can be solved using the Bregman projections algorithm (also known as the Sinkhorn algorithm in this case). This algorithm can be implemented using only matrix multiplications of the matrix exp(−C/ε) (pointwise exponent) and pointwise vector multiplications, where C is a cost matrix, and ε is the regularization parameter. We use the semi-discrete approximation to obtain a low-rank decomposition of this matrix and exploit it to accelerate the Bregman projection algorithm.