Annealed quantitative estimates for the quadratic 2D-discrete random matching problem

以下是论文《二次二维离散随机匹配问题的退火定量估计》（作者：Nicolas Clozeau 和 Francesco Mattesini）的详细技术总结。

1. 问题陈述

本文研究了在闭的、紧致的二维黎曼流形 $M$（无边界）上的二次随机匹配问题。

• 设置：从 $M$ 中采样两个随机点序列 $\{X_i\}_{i=1}^n$ 和 $\{Y_j\}_{j=1}^m$。目标是使匹配点对之间的总平方黎曼距离最小化。
• 数学表述：这等价于寻找经验测度 $\mu_n = \frac{1}{n}\sum \delta_{X_i}$ 和 $\nu_m = \frac{1}{m}\sum \delta_{Y_j}$ 之间的二次 Wasserstein 距离 $W_2^2(\mu_n, \nu_m)$。
• 背景：虽然独立同分布（i.i.d.）均匀样本的代价渐近标度已被充分理解（在二维中按 $\frac{\log n}{n}$ 标度），但本工作专注于更一般条件下传输映射本身的定量估计：
  1. 非均匀密度：点根据密度 $\rho$ 分布（有界且严格为正）。
  2. 相关性：点不一定是独立同分布的；它们可能表现出相关性（例如通过 $\alpha$-混合或马尔可夫链）。
  3. 样本量不等：$n$ 和 $m$ 渐近等价但不一定相等。

2. 方法论

作者采用了线性化拟设，结合定量稳定性分析和概率集中不等式。

A. 蒙日 - 安培方程的线性化

核心思想源自 Caracciolo 等人 [16] 并由 Ambrosio 等人 [6] 严格证明，即通过单位映射的扰动来近似最优传输映射 $T^n$：
$$T^n \approx \text{Id} + \nabla h_n$$
其中 $h_n$ 是势函数。形式上，蒙日 - 安培方程 $(\nu_n \circ T^n) \det(\nabla T^n) = \mu_n$ 被线性化，导出一个泊松型方程：
$$\nabla \cdot (\rho \nabla h_n) = \mu_n - \nu_n$$
然而，源项 $\mu_n - \nu_n$ 过于粗糙（狄拉克质量的和），导致 $h_n$ 无法直接属于 $H^1$ 空间。

B. 正则化策略

为了处理这种粗糙性，作者在时间 $t \sim \frac{\log^\kappa n}{n}$ 引入了热半群正则化。

1. 平滑测度：定义 $\mu_{n,t} = P_t \mu_n$ 和 $\nu_{m,t} = P_t \nu_m$，其中 $P_t$ 是热半群。
2. 正则化偏微分方程：在方程中求解 $h_{n,t}$：
   $$\nabla \cdot (\rho \nabla h_{n,t}) = \mu_{n,t} - \nu_{m,t}$$
3. 近似方案：构造候选传输计划 $\gamma_{n,t} = (\text{Id}, \exp(\nabla h_{n,t}))_\# \mu_{n,t}$。

C. 误差分解

证明策略将最优计划 $\pi$ 与近似计划 $\gamma_{n,t}$ 之间的误差分解为两个主要部分：

1. 正则化误差：平滑计划 $\gamma_{n,t}$ 与源自未平滑（但正则化密度）解的计划之间的距离。这利用能量估计和具有粗糙系数的椭圆算子的 Meyers 估计进行控制。
2. 稳定性误差：平滑计划与真实最优计划之间的距离。这依赖于传输映射的定量稳定性（定理 2.1），该定理指出，如果目标测度在 $W_2$ 中接近，则传输映射在 $L^2$ 中接近。

D. 处理相关性

一个重大的技术障碍是处理非独立同分布样本。作者假设：

• $\alpha$-混合：相关性以拉伸指数速率衰减：$\alpha_\ell \leq a \exp(-b \ell^\eta)$。
• $\beta$-混合：通过混合系数的和进行控制。
• 马尔可夫链：结果扩展到满足漂移条件的次几何遍历马尔可夫链。
  作者利用针对这些相关序列调整的集中不等式（命题 A.1）来界定经验测度波动和偏微分方程解的波动。

3. 主要贡献与结果

主要定理

本文建立了传输映射收敛的退火定量估计（期望中的界）。

• 定理 1.2（完全匹配）：对于满足混合假设的两个点云，$\mu_n$ 和 $\nu_m$ 之间的最优传输计划 $\pi$ 被 $\gamma_{n,t}$ 定量近似。
  $$\inf_{\pi} W_2^2(\pi, \gamma_{n,t}) \leq C_n \frac{\log n}{n} \sqrt{\frac{\log \log n}{\log n}}$$
  其中 $C_n$ 是具有有界矩的随机变量。如果混合衰减足够快（$\eta > 2$），则界限得到改善，并且可以放弃对 $\beta$-混合系数之和的假设。

• 定理 1.3（半离散匹配）：对于连续测度 $\rho dm$ 与经验测度 $\mu_n$ 之间的匹配，最优映射 $T^n$ 在 $L^2$ 中被 $\exp(\nabla f_{n,t})$ 近似，具有相同的收敛速率。

技术创新

1. 扩展到相关数据：这是第一项在最优传输背景下，严格证明相关随机点（超越独立同分布）线性化拟设有效性的工作。
2. 次几何遍历性：结果扩展到一类不满足几何遍历性但满足次几何漂移条件的离散时间马尔可夫链。
3. 精细的正则化：作者优化了正则化参数（时间 $t$ 和密度平滑 $\delta$），以平衡源项的粗糙性与传输映射的稳定性，实现了与已知最优代价标度相匹配的速率。
4. 傅里叶分析与集中：证明严重依赖于热核的傅里叶分析以及针对相关和的新颖集中不等式，以控制势函数 $h_{n,t}$ 梯度的 $L^q$ 范数。

4. 意义

• 物理启发式方法的严格证明：本文为统计物理中广泛使用的“线性化拟设”（例如 Caracciolo, Lucibello, Parisi, Sicuro 使用的方法）推导渐近代价提供了严格的数学基础。它超越了仅关注代价，深入到了传输映射的结构。
• 对依赖关系的鲁棒性：通过处理相关数据和马尔可夫链，这些结果适用于独立性假设不佳的更广泛物理和经济系统（例如相互作用粒子系统、时间序列数据）。
• 定量精度：本文提供了具有精确随机可积性（例如误差常数的指数矩）的显式收敛速率，这对于需要高概率保证的应用至关重要。
• 未解决问题：作者讨论了这些速率的尖锐性（表明可能需要二阶线性化才能达到最优性），并探讨了向 $p$-代价、吉本斯系综和库仑气体扩展的潜力。

结论

Clozeau 和 Mattesini 成功推广了二维随机匹配的定量理论。他们证明，经过适当正则化的线性化蒙日 - 安培方程，即使在存在复杂相关性和非均匀密度的情况下，也能提供最优传输计划的高度准确近似，其收敛速率与匹配代价的理论极限相匹配。