1 Introduction
1.1 Motivation
Let us, for the moment, picture the Euclidean space \((\R^n, \absval{\cdot})\). Crucially, it is a complete separable metric space, i.e., a Polish space (see Definition 3.1), and it has a (simple) metric geometry together (geodesics and averages) with differential calculus. Can we do the same on probability measures?
Let \(\mu, \nu \in \probs{\R^d}\) be from the space of Borel probability measures on \(\R^d\).
For single-point Dirac measure (both the source and target one), one can transport it by the geodesic in \(\R^d\). Alternatively, we could consider a linear average, see Figure 1.2.
It turns out this is the geodesic with respect to the so-called total variation distance, see [1]. However, such transport does not take into account the geometry of the underlying base space!
Let us start by considering the space of Dirac measures, i.e., \(\mu = \dirac_{\vi x}\), \(\nu = \dirac_{\vi y}\). The main idea will be to lift the geometry of \(\R^d\) to the space of probability measures \(d(\dirac_{\vi x}, \dirac_{\vi y}) := \absval{\vi x - \vi y}\). Similarly, we can define the average of \(\dirac_{\vi x}\) and \(\dirac_{\vi y}\) as \(\dirac_{\frac{\vi x + \vi y} 2}\). Can this be generalized?
1.1.1 Empirical Measures
Let us consider \(\mu, \nu\) to be convex combinations of Dirac measures, i.e., \[ \mu = \sum_{i = 1}^n \mu_i \dirac_{\vi x_i}, \quad \& \quad \nu = \sum_{j = 1}^m \nu_j \dirac_{\vi y_j}, \] and denote \(\mcal X := \set{\vi x_1, \dots, \vi x_n}\), \(\mcal Y := \set{\vi y_1, \dots, \vi y_m}\). The first (naive) idea is to transport “mass at \(\vi x_i\) to mass at \(\vi y_j\)”, i.e., define a transport map \(\vi T \colon \mcal X \to \mcal Y\) s.t. \[ \pf{\vi T}{\mu} = \sum_{i = 1}^n \mu_i \dirac_{\vi T(\vi x_i)} = \nu, \] where \(\pf{\vi T}{\mu}\) is the pushforward of \(\mu\) with respect to \(\vi T\). Surely, there are often many different transport maps (among which we must choose) and there exist various visualizations, see Figure 1.3.
We follow up by another idea of selecting the “optimal” map by the “least action principle”. That is, we take a cost function \(\cc \colon \mcal X \times \mcal Y \to \R\). Given a transport map, it induces the corresponding transport cost \(\sum_{i = 1}^n \mu_i \cc(\vi x_i, \vi T(\vi x_i))\). This leads to the Monge formulation, \[ \inf_{\pf{\vi T}{\mu} = \nu} \sum_{i = 1}^n \mu_i \cc(\vi x_i, \vi T(\vi x_i)). \tag{1.1}\]
The Monge formulation is often ill-posed!
A way to relax from the Monge formulation (and avoid the ill-posedness) is to allow for mass-splitting, which leads to the Kantorovich (standard) formulation, see Figure 1.4.
Indeed, consider the following Kantorovich optimal transport problem, \[ \begin{gathered} \inf_{\pi} \sum_{i,j = 1}^{n,m} \pi_{i,j} \cc(\vi x_i, \vi y_j), \; \text{ s.t. } \; \lcases{ \pi_{i,j} \geq 0, \\ \sum_{j = 1}^m \pi_{i,j} = \mu_i, \\ \sum_{i = 1}^n \pi_{i,j} = \nu_j. } \end{gathered} \tag{1.2}\] Note that the set of constraints is convex, compact and non-empty (e.g., \(\pi_{i,j} = \mu_i \cdot \nu_j\) satisfy the constraints). Thus, we have a standard linear programming problem! Moreover, one can make the following observations:
- The cost is linear in \(\pi\), hence there exists an optimizer1;
- Strong duality: (1.2) = (1.3), where \[ \sup_{(f_i)_i, (g_j)_j} \sum_{i = 1}^n \mu_i f_i + \sum_{j = 1}^m \nu_j g_j \; \text{ s.t. } \; f_i + g_j \leq \cc_{ij} = \cc(\vi x_i, \vi y_j) \tag{1.3}\] and \(f_i, g_j\) are Lagrange multipliers of the marginal constraints. Assume \((f,g)\) and \(\pi\) are admissible, then also weak-duality holds \[ \sum_{i = 1}^n f_i \mu_i + \sum_{j = 1}^m g_j \nu_j = \sum_{i,j = 1}^{n,m} \pi_{i,j} \underbrace{(f_i + g_j)}_{\leq \cc_{ij}} \leq \sum_{i,j = 1}^{n,m} \pi_{i,j} \cc_{i,j}; \]
- Complementary slackness: \((f,g)\) and \(\pi\) are optimal if and only if \(\pi_{i,j} > 0 \implies f_i + g_j = \cc_{ij}\);
- \(c\)-cyclical monotonicity: Let \(\pi\) be optimal, \(\Gamma = \supp \pi := \set{(\vi x_i, \vi y_j) \in \mcal X \times \mcal Y \mid \pi_{i,j} > 0}\). Then taking \((\hat{\vi x}_1, \hat{\vi y}_1), \dots, (\hat{\vi x}_k, \hat{\vi y}_k) \in \Gamma\) also gives \[ \sum_{i = 1}^k \cc(\hat{\vi x}_i, \hat{\vi y}_i) \leq \sum_{i = 1}^k \cc(\hat{\vi x}_i, \hat{\vi y}_{i+1}) \tag{1.4}\] with \(\hat{\vi y}_{k+1} = \hat{\vi y}_1\). In fact, \(\pi\) is optimal if and only if it is \(\cc\)-cyclically monotone, i.e., (1.4) holds. Let us show “\(\implies\)”. Indeed, for \(\pi\) optimal we also have \(f,g\) optimal for (1.3) and (3.) yields equality \(f(\hat{\vi x}_i) + g(\hat{\vi y}_i) = \cc(\hat{\vi x}_i, \hat{\vi y}_i)\) on the support. Thus summing over \(i\) gives us \[\begin{align*} \sum_{i = 1}^k \cc(\hat{\vi x}_i, \hat{\vi y}_i) &= \sum_{i = 1}^k f(\hat{\vi x}_i) + g(\hat{\vi y}_i) \\ &= \sum_{i = 1}^k f(\hat{\vi x}_i) + g(\hat{\vi y}_{i+1}) \\ &\leq \sum_{i = 1}^k \cc(\hat{\vi x}_i, \hat{\vi y}_{i+1}). \end{align*}\]
Hence the cost is also continuous over a compact convex feasible set, thus we have existence.↩︎