Optimal Transport

Theoretical Foundations

Monge Problem

先从离散情形出发：两组点携带相同的总质量，我们希望以尽可能小的代价把源端的质量搬到目标端。如果每个源点只能选择一个去向，这就是确定性的运输；对于点数相同、权重均匀的两组点，它退化为匹配问题。

Definition 1 (Discrete Measure, 离散测度). A discrete probability measure supported on $x_1,\ldots,x_n$ is $$ \alpha=\sum_{i=1}^n a_i\delta_{x_i}, \qquad a_i\geq0,\qquad \sum_{i=1}^n a_i=1. $$ Similarly, write $\beta=\sum_{j=1}^m b_j\delta_{y_j}$.

这里，$a=(a_1,\ldots,a_n)^\top$ 和 $b=(b_1,\ldots,b_m)^\top$ 记录各点的质量，Dirac 测度则记录质量所在的位置。质量与位置是两个不同的信息，后面的运输代价同时依赖它们。

Definition 2 (Discrete Monge Transport). A deterministic transport sends each source point to a single target point: $T(x_i)=y_{\sigma(i)}$. For uniform measures with $n=m$ and $a=b=\mathbf1_n/n$, a feasible transport corresponds to a permutation $\sigma\in\operatorname{Perm}(n)$. With $C_{ij}=c(x_i,y_j)$, the matching problem is $$ \min_{\sigma\in\operatorname{Perm}(n)} \frac1n\sum_{i=1}^n C_{i,\sigma(i)}. $$

从离散点推广到一般测度时，首先需要说明：一个作用在点上的映射，怎样把整份质量分布推到另一处？

Definition 3 (Push-forward Measure, 前推测度). Let $T:\mathcal X\to\mathcal Y$ be measurable and let $\alpha$ be a measure on $\mathcal X$. The push-forward measure $T_\#\alpha$ is defined by $$ (T_\#\alpha)(B)=\alpha(T^{-1}(B)), \qquad B\subseteq\mathcal Y\text{ measurable}. $$

这一定义表达了质量守恒：运输后落在集合 $B$ 中的质量，恰好等于运输前位于原像 $T^{-1}(B)$ 中的质量。$T$ 移动的是点，而 $T_\#$ 移动的是测度。

Proposition 4 (Integration Formula). For any integrable function $f:\mathcal Y\to\mathbb R$, $$ \int_{\mathcal Y}f(y)\,d(T_\#\alpha)(y) =\int_{\mathcal X}f(T(x))\,d\alpha(x). $$

Remark 5（密度的前推）. 设 $T:\mathbb R^d\to\mathbb R^d$ 为微分同胚，$d\alpha(x)=\rho_\alpha(x)\,dx$、$d\beta(y)=\rho_\beta(y)\,dy$，且 $\beta=T_\#\alpha$。由换元公式， $$ \rho_\alpha(x)=\rho_\beta(T(x))\,|\det DT(x)|. $$

也可以从目标位置反过来写：$\rho_\beta(y)=\rho_\alpha(T^{-1}(y))/|\det DT(T^{-1}(y))|$。Jacobian 的作用是补偿局部体积的变化：映射不仅改变质量的位置，也可能把同一份质量压缩或拉伸。

Remark 6（测度与随机变量）. 随机变量是可测映射 $X:(\Omega,\mathcal F,P)\to\mathcal X$，其分布正是前推测度 $\alpha=X_\#P$。若 $Y=T(X)$，则 $$ \operatorname{Law}(Y) =T_\#\alpha =T_\#(X_\#P) =(T\circ X)_\#P. $$

事实上，$\alpha(A)=P(X\in A)=P(X^{-1}(A))$ 正是前推的定义。因此，若 $X\sim\alpha$ 且 $T_\#\alpha=\beta$，那么 $T(X)\sim\beta$。这给出了运输的采样解释：对来自源分布的样本应用同一个确定映射，便得到目标分布的样本。

Definition 7 (Pull-back Operator, 后拉算子). For a map $T:\mathcal X\to\mathcal Y$ and a function $f:\mathcal Y\to\mathbb R$, the pull-back is $T^\#f=f\circ T$, or equivalently $(T^\#f)(x)=f(T(x))$.

Remark 8（前推与后拉）. 测度从 $\mathcal X$ 前推到 $\mathcal Y$，函数则从 $\mathcal Y$ 后拉到 $\mathcal X$。两者满足 $$ \int_{\mathcal Y}f\,d(T_\#\alpha) =\int_{\mathcal X}T^\#f\,d\alpha. $$

可以把后拉理解为“沿着映射读取函数值”：为了在源点 $x$ 处评价目标函数，先到达 $T(x)$，再计算 $f(T(x))$。但密度不能只靠函数复合来变换；它还需要 Jacobian，即 $\rho_\alpha=|\det DT|\,T^\#\rho_\beta$。

Definition 9 (Monge Problem). Given probability measures $\alpha$ on $\mathcal X$ and $\beta$ on $\mathcal Y$, and a cost $c:\mathcal X\times\mathcal Y\to\mathbb R$, the Monge problem is $$ \inf_{T:\,T_\#\alpha=\beta} \int_{\mathcal X}c(x,T(x))\,d\alpha(x). $$

约束 $T_\#\alpha=\beta$ 要求映射把源分布准确地推到目标分布。这里最强的限制是确定性：位于同一个 $x$ 的所有质量必须一起送到 $T(x)$，不能分流。因此，可行映射未必存在。例如，$\alpha=\delta_0$ 无法通过确定映射变成 $\beta=\tfrac12\delta_{-1}+\tfrac12\delta_1$，因为单个 Dirac 测度的前推仍然只能是单个 Dirac 测度。

Kantorovich Relaxation

上一节的例子表明，Monge 映射可能因为不能分流而不存在。Kantorovich 的做法是把“每个源点选择一个去向”改为“记录每对源点与目标点之间运送多少质量”。这样既允许分流，又把优化变量从映射变成了满足线性约束的运输计划。先看离散矩阵形式，再推广到一般测度，便能看清这种松弛与原问题的关系。

Definition 1 (Admissible Coupling, 可行耦合). For discrete measures $\alpha=\sum_i a_i\delta_{x_i}$ and $\beta=\sum_j b_j\delta_{y_j}$, the set of admissible couplings is $$ U(a,b)=\left\{ P\in\mathbb R_+^{n\times m}: P\mathbf1_m=a,\; P^\top\mathbf1_n=b \right\}. $$

这里 $P_{ij}$ 是从 $x_i$ 运往 $y_j$ 的质量：行和固定每个源点运出的总量，列和固定每个目标点收到的总量。同一行可以有多个正元素，因此质量能够分流。在这些计划中选择成本最小的一个，就得到离散 Kantorovich 问题。

Definition 2 (Discrete Kantorovich Problem). With $C_{ij}=c(x_i,y_j)$, define $$ L_C(a,b)=\min_{P\in U(a,b)}\langle C,P\rangle =\min_{P\in U(a,b)}\sum_{i,j}C_{ij}P_{ij}. $$

这一形式的关键在于：$U(a,b)$ 是凸集，运输成本对 $P$ 是线性的，所以这是一个线性规划。对于非离散的分布，“每对位置之间运送多少质量”由乘积空间上的测度来描述，矩阵的行和与列和则推广为边缘测度。

Definition 3 (Coupling of Measures). A coupling of $\alpha\in\mathcal M_+^1(\mathcal X)$ and $\beta\in\mathcal M_+^1(\mathcal Y)$ is a probability measure $\pi$ on $\mathcal X\times\mathcal Y$ with marginals $\alpha$ and $\beta$. The admissible set is $$ \Pi(\alpha,\beta)=\left\{ \pi: (\operatorname{proj}_{\mathcal X})_\#\pi=\alpha,\; (\operatorname{proj}_{\mathcal Y})_\#\pi=\beta \right\}. $$

离散计划 $P$ 对应的测度就是 $\pi=\sum_{i,j}P_{ij}\delta_{(x_i,y_j)}$。把离散成本求和换成对 $\pi$ 的积分，便得到一般形式。

Definition 4 (Kantorovich Problem). The Kantorovich optimal transport cost is $$ L_c(\alpha,\beta)=\inf_{\pi\in\Pi(\alpha,\beta)} \int_{\mathcal X\times\mathcal Y}c(x,y)\,d\pi(x,y). $$ The feasible set is nonempty because $\alpha\otimes\beta\in\Pi(\alpha,\beta)$. Under standard regularity assumptions on the spaces and cost, an optimal coupling exists.

Remark 5（联合分布的解释）. 若把耦合看作 $\pi=\operatorname{Law}(X,Y)$，那么成本就是 $\mathbb E_\pi[c(X,Y)]$。边缘分布只规定 $X$ 和 $Y$ 各自的分布，优化选择的是它们之间的依赖关系。给定 $x$ 后，条件分布 $\pi(dy\mid x)$ 描述该处质量如何分流；若它退化为 $\delta_{T(x)}(dy)$，就回到了确定关系 $Y=T(X)$。

这也解释了为什么 Kantorovich 是 Monge 的松弛：每个可行映射都给出一个耦合，而且成本完全相同。

Proposition 6 (Monge-induced Coupling). If $T_\#\alpha=\beta$, then $\pi_T=(\operatorname{Id},T)_\#\alpha$ belongs to $\Pi(\alpha,\beta)$, and $$ \int_{\mathcal X\times\mathcal Y}c(x,y)\,d\pi_T(x,y) =\int_{\mathcal X}c(x,T(x))\,d\alpha(x). $$

因此，Kantorovich 的最优值不会高于 Monge 的下确界；扩大可行集合后得到的计划却未必来自某个映射。当最优耦合集中在可测映射 $T$ 的图像上时，它才重新给出一个 Monge 最优解。

最后回到均匀离散测度：这里虽然允许分流，但松弛并不会改变匹配问题的最优值。这可以从可行集合的极点结构看出来。

Definition 7 (Birkhoff Polytope). The Birkhoff polytope is the set of doubly stochastic matrices: $$ \mathcal B_n=\left\{ Q\in\mathbb R_+^{n\times n}: Q\mathbf1_n=\mathbf1_n,\; Q^\top\mathbf1_n=\mathbf1_n \right\}. $$

当 $a=b=\mathbf1_n/n$ 时，$U(a,b)=\tfrac1n\mathcal B_n$；因此，理解双随机矩阵的结构，就能理解这个特殊情形的最优运输计划。

Theorem 8 (Birkhoff–von Neumann). Every doubly stochastic matrix is a convex combination of permutation matrices: $$ Q=\sum_{k=1}^K\lambda_kP_{\sigma_k}, \qquad \lambda_k\geq0,\qquad \sum_{k=1}^K\lambda_k=1. $$ Equivalently, the extreme points of $\mathcal B_n$ are exactly the permutation matrices.

Remark 9（均匀匹配中的松弛是紧的）. 每个可行计划都是排列耦合的凸组合，而成本是线性的，所以总能选到一个排列耦合作为最优解。允许分流扩大了可行集合，却没有降低这个特殊情形的最优值。

Wasserstein Distance

Definition 1 (Discrete Wasserstein Distance). Let $a,b\in\Sigma_n$, and let $D\in\mathbb R_+^{n\times n}$ be a metric matrix on $\{1,\ldots,n\}$. For $p\geq1$, define $$ W_p(a,b)=L_{D^p}(a,b)^{1/p} =\left(\min_{P\in U(a,b)}\sum_{i,j}D_{ij}^pP_{ij}\right)^{1/p}. $$

这里 $D^p$ 表示逐元素取幂。与一般运输代价相比，Wasserstein 距离以空间本身的距离为基础，并在最优的 $p$ 次代价之后取 $p$ 次方根。

Remark 2（指数不超过一的情形）. 当 $p$ 为正且不超过一时，$W_p^p=L_{D^p}$ 构成距离，但 $W_p$ 本身未必满足三角不等式。

原因是非负数满足 $(x+y)^p\leq x^p+y^p$，所以 $D^p$ 仍满足三角不等式。需要区分这里构成距离的是 $W_p^p$，而不是一般意义下的 $W_p$ 本身。

Definition 3 (Continuous Wasserstein Distance). Let $(\mathcal X,d)$ be a metric space, let $\alpha,\beta\in\mathcal M_+^1(\mathcal X)$, and let $p\geq1$. Define $$ W_p(\alpha,\beta)=\left( \inf_{\pi\in\Pi(\alpha,\beta)} \int_{\mathcal X\times\mathcal X}d(x,y)^p\,d\pi(x,y) \right)^{1/p}. $$

Remark 4（随机变量解释与无穷阶距离）. 若 $(X,Y)\sim\pi$，Wasserstein 距离可以等价地写成 $$ W_p(\alpha,\beta) =\inf_{\pi\in\Pi(\alpha,\beta)}\bigl(\mathbb E_\pi[d(X,Y)^p]\bigr)^{1/p} =\inf_{\pi\in\Pi(\alpha,\beta)}\|d(X,Y)\|_{L^p(\pi)}. $$

这就是说，在所有具有指定边缘分布的随机变量配对中，让运输距离的 $L^p$ 范数尽可能小。相应的无穷阶版本定义为 $$ W_\infty(\alpha,\beta) =\inf_{\pi\in\Pi(\alpha,\beta)} \operatorname*{ess\,sup}_{(x,y)\sim\pi}d(x,y). $$

其中 essential supremum 就是 $\|d(X,Y)\|_{L^\infty(\pi)}$。有限阶强调平均意义下的距离，无穷阶则控制最坏情况下的距离，忽略零概率事件。

Definition 5 (Weak Convergence). On a compact space $\mathcal X$, a sequence $\alpha_k\in\mathcal M_+^1(\mathcal X)$ converges weakly to $\alpha$, written $\alpha_k\rightharpoonup\alpha$, if for every $g\in C(\mathcal X)$, $$ \int_{\mathcal X}g(x)\,d\alpha_k(x) \longrightarrow\int_{\mathcal X}g(x)\,d\alpha(x). $$

Remark 6（分布收敛与 Wasserstein 距离）. 若 $X_k\sim\alpha_k$ 且 $X\sim\alpha$，则 $\alpha_k$ 弱收敛到 $\alpha$ 等价于 $X_k\xrightarrow{d}X$。在紧度量空间上， $$ W_p(\alpha_k,\alpha)\longrightarrow0 \quad\Longleftrightarrow\quad \alpha_k\rightharpoonup\alpha. $$

弱收敛通过连续测试函数观察分布；Wasserstein 收敛则通过运输代价衡量分布间的距离。在紧空间上，这两种看法给出相同的收敛概念。

Proposition 7 (Centering Decomposition). For probability measures on $\mathbb R^d$ with finite second moments, let $m_\alpha$ and $m_\beta$ be their means and set $T_\tau(x)=x-\tau$. Define $\tilde\alpha=(T_{m_\alpha})_\#\alpha$ and $\tilde\beta=(T_{m_\beta})_\#\beta$. Then $$ W_2(\alpha,\beta)^2 =W_2(\tilde\alpha,\tilde\beta)^2+\|m_\alpha-m_\beta\|^2. $$

平方距离恰好分成两部分：均值的位移，以及去掉均值后分布形状之间的差异。