Semidiscrete Optimal Transport

Semidiscrete optimal transport refers to situations in optimal transport where two input measures are considered, and one measure is a discrete measure and the other one is continuous. Hence, because only one of the two measures is discrete, we arrive at the appropriate name "semidiscrete."

Formulation of the semidiscrete dual problem

In particular, we will examine semidiscrete optimal transport in the case of the dual problem. The general dual problem for continuous measures can be stated as

$$\max _{(\varphi ,\psi )\in R(c)}{\Big \{}\int _{X}\varphi d\mu +\int _{Y}\psi d\nu {\Big \}}$$

where $\mu ,\nu$ denote probability measures on domains $X,Y$ respectively, and $c(x,y)$ is a cost function defined over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \times Y } . $R(c)$ denotes the set of possible dual potentials, and the condition $\varphi (x)+\psi (y)\leq c(x,y)$ is satisfied. It should also be noted that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu } has a density such that $\mu =f(x)dx$. Now, we would like to extend this notion of the dual problem to the semidiscrete case. Such a case can be reformulated as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max_{\varphi \in \R^m} \Big\{ \mathcal{E}(\varphi) = \int_X \varphi^c d\mu + \sum_j \varphi_j b_j \Big\}. }

Aside from using a discrete measure in place of what was originally a continuous one, there are a few other notable distinctions within this reformulation. The first is that $\psi$ is replaced completely with $\varphi$. The second is that $\varphi ^{c}$ denotes the c-transform of $\varphi$. The c-transform can be defined as $\varphi ^{c}(x):=\min _{j}\{c(x,y_{j})-\varphi _{j}\}$.

Voronoi cells to find weights

Now, we will establish the notion of Voronoi cells. The Voronoi cells refer to a special subset of $X$, and the reason we are interested in such a subset is because we can use the Voronoi cells as a domain to find the weights $b_{j}$ that we established in our reformulation of the dual problem. In particular, if we denote the set of Voronoi cells as $V_{\varphi }(j)$, we can find our weights using the fact Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j = \int_{V_{\varphi}(j)} f(x)dx } . Recall that $f(x)$ refers to a density of the measure Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu } , i.e., Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu = f(x)dx } . We define the Voronoi cells with

$$V_{\varphi }(j)={\Big \{}x\in X:\forall j'\neq j,{\frac {1}{2}}|x-y_{j}|^{2}-\varphi _{j}\leq {\frac {1}{2}}|x-y_{j'}|^{2}-\varphi _{j'}{\Big \}}.$$

We use the specific cost function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x,y) = \frac{1}{2}|x-y|^2 } here. This is a special case and we may generalize to other cost functions if we desire. When we have this special case, the decomposition of our space $X$ is similarly named a \textbf{power diagram}.

Now that we've defined $V_{\varphi }(j)$, we may use this as our domain of integration to find weights $b_{j}$.

A final thing to note is that another name for Voronoi cells is Laguerre cells.

Finding the weights via the gradient

Finding the weights via the above method is equivalent to maximizing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{E}(\varphi) } , and we may do this by taking the partial derivatives of this function with respect to $\varphi _{j}$. This is the same as taking the gradient of ${\mathcal {E}}(\varphi )$. In partial derivative form, we have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\partial \mathcal{E} }{\partial \varphi_j} = - \int_{V_{\varphi}(j)} f(x)dx + b_j } ,

and in gradient form, we have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla \mathcal{E}(\varphi)_j = - \int_{V_{\varphi}(j)} f(x)dx + b_j .}

Since $\nabla {\mathcal {E}}(\varphi )_{j}=0$ when it attains a maximum, we have the relation between the weights and the measure density that we established in the previous section. Note that the maximum is taken and not the minimum because our function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{E}(\varphi) } is a concave function. The discrete summation contained within this function is linear, but an infimum of a linear function is evaluated for the integration part, making the overall function concave.

Algorithm discussion

In an attempt to find a maximum of ${\mathcal {E}}(\varphi )$, we may use certain algorithms. The first one is gradient ascent.