Today we are going to begin a 6 part series on Optimal Transport. My Honours thesis was based on Optimal Transport and I am fortunate enough to be taking Alessio Figalli’s course on Optimal Transport this year at the ETH. The focus of this blog is to run through in detail the mathematics behind solving the Optimal Transport problem. This post will introduce the Optimal Transport problem and then in the latter posts we will delve deeply into the mathematics behind it’s solution.

1. The Monge Problem

In 1781, Monge was interested in finding the most economic way of moving a pile of soil to a mound. Given points of masses {\{m_1,m_2,...\}}, at locations {\{x_1,x_2,...\}} in {{\mathbb R}^3} that needed to be moved to locations {\{y_1,y_2,...\}}, Monge was interested in finding a bijective map {T:\{x_1,x_2,...\}\rightarrow\{y_1,y_2,...\}} that minimized the weighted distance cost

\displaystyle  	I[T]=\sum m_i|{x_i-T(x_i)}|. 	 	\ \ \ \ \ (1)

This minimizing map is known as the optimal transport map. In his memoir, he used geometric arguments to deduce that if an optimal map does exist then it must be determined by a potential {\phi}. The precise contribution given by Monge was that if the optimal map {T} exists, then it must satisfy

\displaystyle  	\frac{T(x)-x}{|{T(x)-x}|}=-D\phi . 	 	\ \ \ \ \ (2)

A continuous, general version of the Monge problem can be restated as follows. Let {X} and {Y} be measure spaces with probability measures {\mu} and {\nu} respectively – these represent the pile of soil we wish to move and the mound we wish to create. We define the cost function {c} as a measurable function {c(x,y): X\times Y \rightarrow {\mathbb R}\cup\left\{+\infty\right\}}. Note that in Monge’s original consideration, this was simply the weighted distance in (1). A transport map {T: X \rightarrow Y} is a measurable map such that {\nu} is the push forward of {\mu} by {T}. This means that for any measurable set {B\subset Y}, we should have that

\displaystyle  	\nu(B)=\mu(T^{-1}(B)), 	\ \ \ \ \ (3)

and we write {\nu=T_{\sharp}\mu}. With the above defined, the Monge Optimisation problem is to minimise

\displaystyle  	I[T]:=\int_X c(x,T(x))d\mu 	 	\ \ \ \ \ (4)

over all measurable maps {T} that satisfy {\nu=T\#\mu}. The solution to the Monge Problem (4) is called the optimal transport map and the cost associated with it is known as the optimal transportation cost. We will denote the optimal transportation cost between probability measures {\mu} and {\nu} by {\mathcal{T}_c(\mu,\nu)}; i.e.

\displaystyle \mathcal{T}_c(\mu,\nu)=\inf_{T\#\mu=\nu} I[T].

2. The Kantorovich Problem

In 1942, Kantorovich introduced the following relaxed version of the Monge optimisation problem. We again consider two measure spaces {X} and {Y} with probability measures {\mu} and {\nu} respectively. We define an admissible transport plan {\pi} as a joint probability measure on {X\times Y} that has marginals {\mu} and {\nu}. This means that for all measurable sets {A\subset X} and {B\subset Y} we have

\displaystyle  	\pi[A\times Y]=\mu[A],\hspace{1cm}\pi[X\times B]=\nu[B]. 	 	\ \ \ \ \ (5)

The set of all admissible transport plans will be denoted as {\Pi(\mu,\nu)}. Kantorovichs minimisation problem is to minimise

\displaystyle  	I[\pi]=\int_{X\times Y}c(x,y)d\pi(x,y) 	 	\ \ \ \ \ (6)

for all {\pi\in\Pi(\mu,\nu)}. He showed that a solution to his problem exists and that it is indeed determined by a potential, as was argued by Monge. In 1948, Kantorovich related his problem to the Monge optimization problem and showed that his results from could be applied. In fact, the Kantorovich problem is just a relaxed version of the Monge problem. The Monge problem is more stringent in that it does not allow a piece of mass at a point {x\in X} to be split up and sent to multiple different locations in {Y}. We can write the transport plans for the Kantorovich problem in terms of the transport maps of the Monge problem as

\displaystyle  	d\pi(x,y)=d\mu(x)\delta[y=T(x)], 	 	\ \ \ \ \ (7)

where {\delta[y=T(x)]} is the Dirac measure defined to be {1} if {y=T(x)} and {0} otherwise.

That brings us to the end of this introduction, stay tuned for all the details in the next few weeks!

Free WordPress Themes
%d bloggers like this: