A REMARK ON THE GEOMETRIC INTERPRETATION OF THE A3W CONDITION FROM OPTIMAL TRANSPORT

Abstract

We provide a geometric interpretation of the well-known A3w condition for regularity in optimal transport.

1 Introduction

In optimal transport, a condition known as A3w is necessary for regularity of the optimal transport map. Here we provide a geometric interpretation of A3w. We use freely the notation from [4]. Let $c \in C^2(\mathbf {R}^n \times \mathbf {R}^n)$ satisfy A1 and A2 (see Section 2). Keeping in mind the prototypical case $c(x,y) = |x-y|^2$ , we fix $x_0,y_0 \in \mathbf {R}^n$ and perform a linear transformation so that $c_{xy}(x_0,y_0) = -I$ . Define coordinates

(1.1) $$ \begin{align} q(x)&:= -c_y(x,y_0), \end{align} $$

(1.2) $$ \begin{align} p(\,y)&:= -c_x(x_0,y), \end{align} $$

and denote the inverse transformations by $x(q),y(p)$ . Write $c(q,p) = c(x(q),y(p))$ and let $q_0=q(x_0)$ and $p_0=p(\,y_0)$ . We prove A3w is satisfied if and only if whenever these transformations are performed,

$$ \begin{align*} (q-q_0)\cdot (p-p_0) \geq 0 {\implies} c(q,p)+c(q_0,p_0) \leq c(q,p_0)+c(q_0,p). \end{align*} $$

Heuristically, A3w implies that when $q-q_0$ ‘points in the same direction’ as $p-p_0$ , it is cheaper to transport q to p and $q_0$ to $p_0$ than the alternative q to $p_0$ and $q_0$ to p. Thus, A3w represents compatibility between directions in the cost-convex geometry and the cost of transport.

A3w first appeared (in a stronger form) in [4]. It was weakened in [6] and a new interpretation was given in [2]. The impetus for the above interpretation is Lemma 2.1 in [1]. Our result can also be realised by a particular choice of c-convex function in the unpublished preprint [5].

2 Proof of result

Let $c \in C^2(\mathbf {R}^n \times \mathbf {R}^n)$ satisfy the following well-known conditions.

1. A1. For each $x_0,y_0 \in \mathbf {R}^n$ , the mappings

   $$ \begin{align*} x \mapsto c_y(x,y_0) \quad\text{and} \quad y \mapsto c_x(x_0,y) \end{align*} $$
   are injective.

2. A2. For each $x_0,y_0 \in \mathbf {R}^n$ , we have $\det c_{i,j}(x_0,y_0) \neq 0$ .

Here, and throughout, subscripts before a comma denote differentiation with respect to the first variable, subscripts after a comma denote differentiation with respect to the second variable.

By A1, we define on $\mathcal {U}:= \{(x,c_x(x,y)): x,y \in \mathbf {R}^n\}$ a mapping $Y:\mathcal {U}\rightarrow \mathbf {R}^n$ by

$$ \begin{align*} c_x(x,Y(x,p)) = p. \end{align*} $$

The A3w condition, usually expressed with fourth derivatives but written here as in [3], is the following statement.

1. A3w. Fix x. The function

   $$ \begin{align*} p \mapsto c_{ij}(x,Y(x,p))\xi_i\xi_j\end{align*} $$
   is concave along line segments orthogonal to $\xi $ .

To verify A3w, it suffices to verify the midpoint concavity, that is, whenever ${\xi \cdot \eta = 0}$ , it follows that

(2.1) $$ \begin{align} 0 \geq [c_{ij}(x,Y(x,p+\eta)) - 2c_{ij}(x,Y(x,p)) + c_{ij}(x,Y(x,p-\eta))]\xi_i\xi_j. \end{align} $$

Finally, we recall that a set $A \subset \mathbf {R}^n$ is called c-convex with respect to $y_0$ provided $c_y(A,y_0)$ is convex. When the A3w condition is satisfied and $y,y_0 \in \mathbf {R}^n$ are given, the section $\{x \in \mathbf {R}^n: c(x,y)> c(x,y_0)\}$ is c-convex with respect to $y_0$ [3].

Now fix $(x_0,p_0) \in \mathcal {U}$ and $y_0 = Y(x_0,p_0)$ . To simplify the proof, we assume $x_0,y_0,q_0,p_0 = 0$ . Up to an affine transformation (replace y with $\tilde {y}:=-c_{xy}(0,0)y$ ), we assume $c_{xy}(0,0) = -I$ . Note that with $q,p$ , as defined in (1.1), (1.2), this implies ${\partial q}/{\partial x}(0) = I$ . Put

$$ \begin{align*} \tilde{c}(x,y) &:= c(x,y) - c(x,0) - c(0,y) + c(0,0),\\ \overline{c}(q,p) &:= \tilde{c}(x(q),y(p)). \end{align*} $$

Theorem 2.1. The A3w condition is satisfied if and only if whenever the above transformations are applied, the following implication holds:

(2.2) $$ \begin{align} q \cdot p \geq 0 {\implies} \overline{c}(q,p) \leq 0. \end{align} $$

Proof. Observe by a Taylor series

(2.3) $$ \begin{align} \overline{c}(q,p) = -(q \cdot p) + \overline{c}_{ij}(\tau q,p)q_iq_j \end{align} $$

for some $\tau \in (0,1)$ . First, assume A3w and let $q \cdot p> 0$ . By (2.3), we have $\overline {c}(-tq,p)> 0 > \overline {c}(tq,p)$ for $t>0$ sufficiently small. If $\overline {c}(q,p)> 0$ , then the c-convexity (in our coordinates, convexity) of the section

$$ \begin{align*} \{ q : \overline{c}(q,p)> \overline{c}(q,0) = 0 \} \end{align*} $$

is violated. By continuity, $\overline {c}(q,p) \leq 0$ whenever $q \cdot p \geq 0$ .

In the other direction, take nonzero q with $q \cdot p = 0$ and small t. By (2.2) and (2.3),

$$ \begin{align*} 0 \geq \overline{c}(t q,p)/t^2 = \overline{c}_{ij}(t \tau q,p)q_iq_j. \end{align*} $$

This inequality also holds with $-p$ . Moreover, $\overline {c}_{ij}(t \tau q, 0) = 0$ . Thus,

$$ \begin{align*} 0 \geq [\overline{c}_{ij}(t \tau q,p) - 2\overline{c}_{ij}(t \tau q , 0) + \overline{c}_{ij}(t \tau q, -p)]q_iq_j.\end{align*} $$

Sending $t \rightarrow 0$ and returning to our original coordinates, we obtain (2.1).

Remark 2.2. On a Riemannian manifold with $c(x,y) = d(x,y)^2$ , for d the distance function, Loeper [2] proved A3w implies nonnegative sectional curvature. Our result expedites his proof. Let $x_0=y_0 \in M$ and $u,v \in T_{x_0}M$ satisfy $u\cdot v = 0$ with $x = \exp _{x_0}(tu)$ and $y=\exp _{x_0}(tv)$ . Working in a sufficiently small local coordinate chart, our previous proof implies that if A3w is satisfied,

(2.4) $$ \begin{align} d(x,y)^2 \leq d(x_0,y)^2+d(x_0,x)^2 = 2t. \end{align} $$

The sectional curvature in the plane generated by $u,v$ is the $\kappa $ satisfying

(2.5) $$ \begin{align} d(\exp_{x_0}(tu),\exp_{x_0}(tv)) = \sqrt{2}t\bigg(1-\frac{\kappa}{12}t^2+O(t^3)\bigg) \quad\text{as }t \rightarrow 0, \end{align} $$

whereby comparison with (2.4) proves the result. (See [7, Equation (1)] for (2.5).) We note Loeper proved his result using an infinitesimal version of (2.4).