Research

My primary research interest revolves around the numerical analysis of Optimal Transport (OT) problems. In general, the OT problem consists in seeking an optimal transport plan, that is the joint probability density function 𝝅(x,y) , having the source density 𝝁(x)  and the target density 𝝂(y) as marginals, which realizes the minimum of the functional J(𝝅) below:

J(𝝅) = ∫c(x,y)d𝝅

where the cost function c(x,y) represents the cost of moving one unit of mass from x to y.

There are three main types of OT problem, which are based on the type of marginal densities: discrete, semi-discrete, and continuous. See Figure 1 below.

Figure 1. Three types of OT problems

Continuous OT Problems

For the first project [2], we have analyzed existing OT algorithms in the continuous setting with squared Euclidean cost function. In this case, it is well known that the solution to the OT problem exists and is unique.

The main goal of the project was to compare existing OT algorithms for continuous problems and provided thorough numerical implementation details.

In addition, we have discovered the special class of continuous OT problems that we called separable. The continuous OT problem in 2-d is called separable if source and target densities can be written as a product of one-variable dependent functions. Then it is possible to reformulate the 2-d problem into two 1-d problems, which can be solved much faster and more accurately compared to the 2-d problems.

Semi-Discrete OT Problems

For the next project [3] we have focused on semi-discrete OT problems. In this situation, the target density is discrete and it is given at specific target points and the problem is to find a partition, called Laguerre tessellation, of a domain with respect to these target points. 

The problem has been well-studied in the literature when the cost function is the squared 2-norm. In this case, each Laguerre tessellation forms a polygonal region. However, computational techniques do not appear to be very well developed for other cases because of the lack of a simple geometrical shape of Laguerre tessellations. As a result, our goal has been to devise an accurate and fast algorithm for these cases.

Firstly, we proved that all Laguerre cells are star-shaped with respect to the corresponding target point when the cost function is given by a vector norm, c(x,y) = ||x - y||. This result does not hold for 2-norm squared case since this cost function does not satisfy all norm properties. See Figures 2 and 3 below.

Figure 2. Problem with 2-norm cost

Figure 3. Problem with 2-norm squared cost

Above result implies that the boundary of any Laguerre cell in 2-d can be parameterized by an angular coordinate. Then we were able to develop and provide thorough implementation details of an efficient algorithm in 2-d, which computes the gradient and the Hessian of the minimization function up to a desired accuracy by exploiting star-shapedness, smoothness, and structure of the Hessian matrix. 

In addition, we programmed and tested ours method to solve several semi-discrete OT problems: different initial guesses, different source densities, different target densities, different p-norm cost functions, and different domains. For example, see Figures 4-7 below.

Figure 4. Problem with 

32-norm cost function

Figure 5. Problem with non-uniform source density

Figure 6. Problem with circular domain

Figure 7. Problem with triangular domain

Future Research

Publications




Teaching