Pointwise Convergence Analysis for Approximations of Optimal Transport Problems with a Target Measure that Has Unbounded Support

1. Problem Statement

The paper addresses the Monge optimal transport problem in Euclidean space $\mathbb{R}^n$ where:

• Source Measure ($\mu$): Has bounded (compact) support $\Omega \subset \mathbb{R}^n$ and an absolutely continuous density $f_\mu$.
• Target Measure ($\nu$): Has unbounded support on $\mathbb{R}^n$ with density $f_\nu$.
• Cost Function: Primarily focuses on the squared Euclidean distance $c(x,y) = \frac{1}{2}|x-y|^2$, though the radial section considers general costs $c(x,y) = h(|x-y|)$.

The Core Challenge:
Standard numerical solvers for the Monge-Ampère equation (which characterizes the optimal transport map) typically require compact domains. When the target measure has unbounded support, direct numerical solution is infeasible. The paper investigates the validity and convergence rates of a cutoff approximation, where the unbounded target $\nu$ is approximated by a truncated measure $\nu_R$ supported on a ball (or cube) of radius $R$.

2. Methodology

The author employs a two-pronged approach: theoretical analysis of convergence rates and discussion of numerical implementation.

A. The Cutoff Approximation

The unbounded target $\nu$ is approximated by a probability measure $\nu_R$ defined as:
$$\nu_R(E) = \frac{\nu(E \cap B_R(0))}{\nu(B_R(0))}$$
where $B_R(0)$ is a ball of radius $R$. The paper analyzes the convergence of the optimal maps ($T_{\mu;R}, T_{\nu;R}$) and potential functions ($\phi_{\mu;R}, \phi_{\nu;R}$) associated with $\nu_R$ to their true counterparts as $R \to \infty$.

B. Analytical Framework

1. Radial Symmetry (Section 3):

   • Assumes $\mu$ and $\nu$ are radially symmetric.
   • Utilizes the explicit formula for 1D optimal transport (via cumulative distribution functions) extended to $\mathbb{R}^n$.
   • Derives explicit $L^\infty$ convergence rates for maps and potentials based on the tail decay of the target distribution.

2. General Case (Section 4):

   • Relaxes radial symmetry, assuming only that $\mu$ and $\nu$ have densities.
   • Relies on $L^2$ stability bounds established by Delalande and Mérigot [7], which relate the $L^2$ distance between optimal maps to the Wasserstein-1 distance ($W_1$) between the target measures.
   • Key Step: Estimates $W_1(\nu, \nu_R)$ for two classes of distributions:
     • Finite $p$-th Moment: $W_1(\nu, \nu_R) = O(R^{1-p})$.
     • Log-Concave Distributions: $W_1(\nu, \nu_R) = O(R^n e^{-aR})$ (Exponential convergence).
   • Pointwise Convergence: Uses the convexity of Brenier potentials and the $L^2$ bounds to upgrade weak convergence to pointwise convergence on the interior of the support and almost-everywhere (a.e.) convergence for the maps.
   • Explicit Rates: Combines $L^1$ convergence of potentials with Hölder continuity properties (for $p > n$) to derive explicit, non-asymptotic uniform convergence rates for the potentials.

3. Inverse Problem:

   • Analyzes the inverse optimal transport (from $\nu$ to $\mu$).
   • Proves that the inverse Brenier potential is Lipschitz continuous (unlike the forward potential which may be unbounded).
   • Establishes convergence rates for the inverse potential and map, leveraging the stability of subdifferentials of convex functions.

C. Numerical Implications (Section 5)

• Discusses how to solve the resulting cutoff problem using monotone finite-difference schemes for the Monge-Ampère PDE, referencing the convergence framework of Hamfeldt [10].
• Proposes solving the inverse problem numerically (which has a bounded domain for the potential) and interpolating to find the forward map, as the forward potential may blow up near the boundary of the unbounded domain.

3. Key Contributions

1. Quantitative Pointwise Convergence Rates:
   The paper provides the first explicit, non-asymptotic pointwise convergence rates for optimal transport maps and potentials when approximating an unbounded target via cutoff.

   • For log-concave targets, the convergence is exponential in $R$.
   • For targets with finite $p$-th moments, the rate is polynomial, dependent on $p$.

2. Generalization of Stability Theory:
   It extends the $L^2$ stability results of Delalande and Mérigot (originally for compact domains) to the unbounded support case by rigorously bounding the $W_1$ distance between $\nu$ and its cutoff approximation.

3. Inverse Potential Analysis:
   The paper establishes that the inverse Brenier potential is Lipschitz continuous and derives convergence rates for it, offering a more stable numerical alternative to the forward problem in certain regimes.

4. Almost-Everywhere Convergence for Maps:
   While pointwise convergence for the map $T$ is generally impossible due to discontinuities, the paper proves almost-everywhere convergence for both forward and inverse maps under mild regularity assumptions (density bounded away from zero).

4. Main Results

• Theorem 16 & 17 (Radial Case): Explicit $O(1 - F_\nu(R))$ convergence rates for radial maps and potentials.
• Theorem 23 & 24 (General $L^2$ Bounds): Establishes that $\|T_{\mu} - T_{\mu;R}\|_{L^2} \leq C W_1(\nu, \nu_R)^\alpha$.
• Theorem 39 & 41 (Explicit Uniform Rates): For $p > n$ and $p \geq 4$, the uniform error in the Brenier potential is bounded by:
  $$\|\phi_{\mu;R} - \phi_\mu\|_\infty \leq C (W_1(\nu, \nu_R))^{\frac{1 - n/p}{1 + n/q}}$$
  This yields exponential rates for log-concave distributions.
• Theorem 45 & 51 (Inverse Convergence): Proves that if the forward potential converges, the inverse potential (which is Lipschitz) converges with the same rate, and the inverse map converges almost everywhere.
• Proposition 29: Proves that for log-concave distributions, $W_1(\nu, \nu_R) \leq C R^n e^{-aR}$.

5. Significance and Applications

• Justification of Numerical Methods: The results provide a rigorous theoretical foundation for using cutoff approximations in numerical solvers (e.g., Monge-Ampère solvers) for problems with unbounded targets. Without these bounds, truncating the domain is an ad-hoc heuristic; this paper proves it is a convergent approximation with quantifiable error.
• Efficiency in High Dimensions: The exponential convergence rate for log-concave distributions (common in statistics and machine learning, e.g., Gaussian, sub-Gaussian) implies that relatively small cutoff radii $R$ are sufficient for high accuracy, making the approach computationally feasible.
• Inverse Problem Utility: By showing the inverse potential is well-behaved (Lipschitz), the paper suggests a practical numerical strategy: solve the inverse problem on a bounded domain and recover the forward map, avoiding the numerical instabilities associated with the unbounded forward potential.
• Broad Applicability: The methodology applies to various fields requiring optimal transport with unbounded supports, including sampling methods, mesh generation, generative modeling, and fluid dynamics.

In summary, Turnquist's work bridges the gap between theoretical optimal transport on unbounded domains and practical numerical computation by proving that simple truncation (cutoff) yields rapid, quantifiable convergence for a wide class of probability distributions.