Sharp local sparsity of regularized optimal transport

论文技术总结：正则化最优传输的尖锐局部稀疏性

1. 研究背景与问题定义

背景：
最优传输（Optimal Transport, OT）是连接两个概率测度 $\lambda$ 和 $\mu$ 的数学框架。近年来，**熵正则化最优传输（EOT）**因其计算高效性（如 Sinkhorn 算法）而广受欢迎，但其传输计划具有最大支撑集（即密度处处非零），缺乏稀疏性。相比之下，$L^p$ 型正则化最优传输（ROT）（其中 $p \in (1, 2]$）被证明具有稀疏支撑集，且计算复杂度为线性，避免了维数灾难。

核心问题：
虽然已知 ROT 的支撑集 $\text{supp}(\pi_\varepsilon)$ 会随着正则化参数 $\varepsilon \to 0$ 收缩回原始 OT 问题的支撑集，但这种收敛的速率（Rate of Convergence）是多少？ 这是一个开放性问题。
具体而言，对于给定的 $x$，条件支撑集 $S_x = \{y : \rho_\varepsilon(x, y) > 0\}$ 的直径如何随 $\varepsilon$ 变化？

模型定义：
考虑如下正则化问题 (ROT)：
$$\text{ROT}_{\varepsilon,p} := \inf_{\pi \in \Pi(\lambda, \mu)} \int \frac{1}{2}\|x-y\|^2 d\pi + \varepsilon \int h_p\left(\frac{d\pi}{d(\lambda \otimes \mu)}\right) d(\lambda \otimes \mu)$$
其中 $h_p(z) = \frac{|z|^p-1}{p-1}$，$p \in (1, 2]$。其共轭指数为 $q = \frac{p}{p-1}$。
最优传输计划 $\pi_\varepsilon$ 的密度由下式给出：
$$\rho_\varepsilon(x, y) = \frac{1}{\varepsilon^{q-1} q^{q-1}} \left( f_\varepsilon(x) + g_\varepsilon(y) - \frac{1}{2}\|x-y\|^2 \right)_+^{q-1}$$
其中 $(\cdot)_+$ 表示正部。由于正部的存在，当括号内项为负时密度为零，从而产生稀疏性。

2. 主要贡献与核心结果

本文在 $\lambda$ 和 $\mu$ 具有紧支撑且密度光滑的假设下，获得了远离边界的尖锐局部结果。

贡献一：支撑集收缩的尖锐速率 (Sharp Local Sparsity)

• 定理 3.1 (内部尖锐稀疏性)：
  对于支撑集 $\Omega_0$ 内部的任意光滑子域 $K_0 \Subset \Omega_0$，存在常数 $R_0$ 和 $\varepsilon_0$，使得对于所有 $x \in K_0$ 和 $\varepsilon \in (0, \varepsilon_0]$，条件支撑集 $S_x$ 被夹在两个球之间：
  $$B\left(\nabla\varphi_\varepsilon(x), \frac{1}{R_0}\varepsilon^{\frac{1}{d(p-1)+2}}\right) \subset S_x \subset B\left(\nabla\varphi_\varepsilon(x), R_0\varepsilon^{\frac{1}{d(p-1)+2}}\right)$$
  其中 $\nabla\varphi_\varepsilon(x)$ 是正则化势函数的梯度（近似于最优传输映射）。
  • 结论： 支撑集 $S_x$ 的直径以速率 $\varepsilon^{\frac{1}{d(p-1)+2}}$ 收缩。
  • 尖锐性： 作者在第 6 节通过环面上的自传输（Self-transport）显式解证明了该速率是尖锐的（Sharp），即无法改进。

贡献二：正则化势函数的强凸性 (Uniform Strong Convexity)

• 推论 3.2：
  证明了正则化势函数 $\varphi_\varepsilon$ 在内部区域是一致强凸的。即存在常数 $C$，使得对于所有 $x \in \text{int}(\Omega_0)$：
  $$\inf_{\|h\|=1} \langle \nabla^2\varphi_\varepsilon(x)h, h \rangle \geq \frac{1}{C}$$
  这一性质对于控制 Hessian 矩阵的逆以及推导收敛速率至关重要。

贡献三：最优传输映射的收敛速率 (Rates of ROT Map)

• 推论 3.3：
  基于支撑集的收缩速率和强凸性，推导了正则化传输映射 $\nabla\varphi_\varepsilon$ 向原始 OT 映射 $\nabla\varphi$ 收敛的 $L^2$ 速率：
  $$\|\nabla\varphi_\varepsilon - \nabla\varphi\|_{L^2(K_0)} \leq C \varepsilon^{\frac{1}{d(p-1)+2}}$$
  这量化了正则化方案逼近经典最优传输方案的精度。

3. 方法论与技术路线

1. 对偶性与正则化势函数：
   利用 ROT 的对偶问题，引入凸函数 $\varphi_\varepsilon = \|\cdot\|^2/2 - f_\varepsilon$ 和 $\psi_\varepsilon = \|\cdot\|^2/2 - g_\varepsilon$。支撑集 $S_x$ 的几何性质完全由 $\xi(x, y) = \langle x, y \rangle - \varphi_\varepsilon(x) - \psi_\varepsilon(y)$ 的正部决定。

2. Hessian 的一致有界性：
   利用先前工作 [GK26] 的结果，即 $\|\nabla^2\varphi_\varepsilon\|_{L^\infty_{loc}} \leq C$。这一上界保证了势函数在局部是 Lipschitz 连续的，且其二阶导数不会爆炸。

3. 上下界估计策略：

   • 上界（$S_x$ 不会太大）： 利用 Fenchel 不等式和 $\nabla\psi_\varepsilon$ 的 Lipschitz 性质，结合 $\xi(x, y)$ 在支撑集边界处为零的条件，推导出 $\xi(x, y)$ 的最大值与 $\varepsilon$ 的关系，进而限制 $S_x$ 的半径。
   • 下界（$S_x$ 不会太小）： 利用 Jensen 不等式和 $\varphi_\varepsilon$ 的凸性，证明 $\nabla\varphi_\varepsilon(x)$ 位于 $S_x$ 内部，且 $\xi(x, \nabla\varphi_\varepsilon(x))$ 具有特定的下界量级，从而保证支撑集包含一个半径为 $\varepsilon^{\dots}$ 的球。

4. Reynolds 传输定理的应用：
   为了处理支撑集边界随 $x$ 变化带来的导数计算问题（特别是在 $p=2$ 时），作者使用了改进的 Reynolds 传输定理来计算 $\nabla^2\varphi_\varepsilon$ 的表达式，并分析其正定性以证明强凸性。

5. 显式构造验证：
   在环面 $T^d$ 上考虑 $\lambda = \mu = \text{Lebesgue}$ 的自传输问题。利用对称性，证明对偶变量为常数，从而得到显式的密度公式。通过计算积分约束，直接得出支撑半径 $R_\varepsilon \sim \varepsilon^{\frac{1}{d(p-1)+2}}$，验证了理论速率的尖锐性。

4. 关键结果总结

5. 意义与影响

1. 理论突破： 本文首次在多变量（Multivariate）和非自传输（Non-self-transport）的一般设置下，给出了 ROT 支撑集收缩的尖锐速率。这填补了从 EOT（无稀疏性）到 ROT（稀疏性）的理论空白。
2. 算法理解： 结果解释了为什么 ROT 比 EOT 更适合某些需要稀疏解的应用场景（如图像分割、特征匹配）。它量化了正则化参数 $\varepsilon$ 与解的稀疏程度之间的精确权衡。
3. 推广性： 本文结果推广了 González-Sanz & Nutz (2024) 和 Wiesel & Xu (2025) 的工作，将一维或自传输的特殊情况推广到了更一般的多元概率测度情形。
4. 数值启示： 收敛速率 $\varepsilon^{\frac{1}{d(p-1)+2}}$ 表明，在高维空间中，为了获得高精度的稀疏解，$\varepsilon$ 需要非常小，这为数值算法的参数选择提供了理论依据。

总结：
该论文通过精细的凸分析和几何估计，揭示了 $L^p$ 正则化最优传输中支撑集收缩的几何结构，证明了其局部行为类似于半径为 $\varepsilon^{\frac{1}{d(p-1)+2}}$ 的球，并确立了正则化势函数的强凸性，从而为理解和使用稀疏最优传输提供了坚实的理论基础。