4cm4cm3cm3cm

# Transport type metrics on the space of probability measures involving
singular base measures111B.P. is pleased to acknowledge the support of
National Sciences and Engineering Research Council of Canada Discovery Grant
number 04658-2018. He is also grateful for the kind hospitality at the
Institut de Mathématiques d’Orsay, Université Paris-Sud during his stay in
November of 2019 as a missionaire scientifique invité, when this work was
partially completed. L.N. would like to acknowledge the support from the
project MAGA ANR-16-CE40-0014 (2016-2020) and the one from the CNRS PEPS JCJC
(2021). They are also indebted to two anonymous referees for their many
insightful comments on an earlier draft of this work.

Luca Nenna Université Paris-Saclay, CNRS, Laboratoire de mathématiques
d’Orsay, 91405, Orsay, France<EMAIL_ADDRESS>Brendan
Pass Department of Mathematical and Statistical Sciences, 632 CAB, University
of Alberta, Edmonton, Alberta, Canada, T6G 2G1<EMAIL_ADDRESS>
###### Abstract

We develop the theory of a metric, which we call the $\nu$-based Wasserstein
metric and denote by $W_{\nu}$, on the set of probability measures
$\mathcal{P}(X)$ on a domain $X\subseteq\mathbb{R}^{m}$. This metric is based
on a slight refinement of the notion of generalized geodesics with respect to
a base measure $\nu$ and is relevant in particular for the case when $\nu$ is
singular with respect to $m$-dimensional Lebesgue measure; it is also closely
related to the concept of linearized optimal transport. The $\nu$-based
Wasserstein metric is defined in terms of an iterated variational problem
involving optimal transport to $\nu$; we also characterize it in terms of
integrations of classical Wasserstein metric between the conditional
probabilities when measures are disintegrated with respect to optimal
transport to $\nu$, and through limits of certain multi-marginal optimal
transport problems. We also introduce a class of metrics which are dual in a
certain sense to $W_{\nu}$, defined relative to a fixed based measure $\mu$,
on the set of measures which are absolutely continuous with respect to a
second fixed based measure $\sigma$.

As we vary the base measure $\nu$, the $\nu$-based Wasserstein metric
interpolates between the usual quadratic Wasserstein metric (obtained when
$\nu$ is a Dirac mass) and a metric associated with the uniquely defined
generalized geodesics obtained when $\nu$ is sufficiently regular (eg,
absolutely continuous with respect to Lebesgue). When $\nu$ concentrates on a
lower dimensional submanifold of $\mathbb{R}^{m}$, we prove that the
variational problem in the definition of the $\nu$-based Wasserstein metric
has a unique solution. We also establish geodesic convexity of the usual class
of functionals, and of the set of source measures $\mu$ such that optimal
transport between $\mu$ and $\nu$ satisfies a strengthening of the generalized
nestedness condition introduced in [16]. We finally introduce a slight variant
of the dual metric mentioned above in order to prove convergence of an
iterative scheme to solve a variational problem arising in game theory.

###### Contents

  1. 1 Introduction
  2. 2 Definition and basic properties
    1. 2.1 Background on optimal transport
    2. 2.2 The $\nu$-based Wasserstein metric
    3. 2.3 Dual metrics
  3. 3 Unequal dimensional optimal transport
    1. 3.1 Nestedness and its high dimensional generalization
    2. 3.2 Sufficient conditions for nestedness
  4. 4 Uniqueness of optimal couplings and structure of geodesics when $\nu$ concentrates on a lower dimensional submanifold
  5. 5 Convexity properties
    1. 5.1 Geodesic convexity of functionals
    2. 5.2 Geodesic convexity of the set of nested sources
  6. 6 Fixed point characterization of solutions to variational problems
  7. A Hierarchical metrics with multiple reference measures

##  1 Introduction

Given two probability measures $\mu_{0}$ and $\mu_{1}$ on a convex, bounded
domain $X\subseteq\mathbb{R}^{m}$, the Wasserstein distance between them is
defined as the infimal value in the Monge-Kantorovich optimal transport
problem; that is,

$W_{2}(\mu_{0},\mu_{1}):=\sqrt{\inf_{\gamma\in\Pi(\mu_{0},\mu_{1})}\int_{X\times
X}|x_{0}-x_{1}|^{2}d\pi(x_{0},x_{1})}$ (1)

where the infimum is over the set $\Pi(\mu_{0},\mu_{1})$ of joint measures
$\gamma$ on $X\times X$ whose marginals are $\mu_{0}$ and $\mu_{1}$.

Among the many important properties of the Wasserstein distance (reviewed in
[19][20] and [21] for example) is the fact that it is a metric on the set
$\mathcal{P}(X)$ of probability measures on $X$. In turn, the geodesics
induced by this metric, known as _displacement interpolants_ and introduced in
[14], play key roles in many problems, both theoretical and applied. Variants
of displacement interpolants, known as _generalized geodesics_ (introduced in
[1], see Definition 2 below), are a natural and important tool in the analysis
of problems involving a fixed base measure $\nu\in\mathcal{P}(X)$. For
example, a variety of problems in game theory, economics and urban planning
consist in minimizing functionals on $\mathcal{P}(X)$ involving optimal
transport to a fixed $\nu$. In particular, we mention the optimal transport
based formulation of Cournot-Nash equilibria in game theory of Blanchet-
Carlier, in which $\nu$ parameterizes a population of players and one searches
for their equilibrium distribution of strategies, parameterized by
$\mu\in\mathcal{P}(X)$ [3][2][4]. When $\nu$ is absolutely continuous with
respect to the Lebesgue measure $\mathcal{L}^{m}$ on $X$, these interpolants
are uniquely defined, and are in fact geodesics for a metric under which
$\mathcal{P}(X)$ is isomorphic to a subset of the Hilbert space
$L^{2}(X,\mathbb{R}^{n})$; that is, under this isomorphism, generalized
geodesics are mapped to line segments.

On the other hand, it is natural in certain problems to consider _singular_
base measures222For instance, in game theory problems derived from spatial
economics, $\nu$ may represent a population of players, parametrized by their
location $y\in\mathbb{R}^{2}$ [4]; it is often the case that the population is
essentially concentrated along a one dimensional subset, such as a major
highway or railroad., and our goal here is to initiate the development of a
framework to study these. We study a metric on an appropriate subset of
$\mathcal{P}(X)$ for each choice of base measure $\nu$, which we call the
$\nu$-based Wasserstein metric (see Definition 3); essentially, this metric
arises from minimizing the average squared distance among all couplings of
$\mu_{0}$ and $\mu_{1}$ corresponding to generalized geodesics. It is also
very closely related to the concept of linear optimal transport, introduced in
[22]333In fact, in the case we are most interested in, when there exists a
unique optimal transport between $\nu$ and each of the measures to be
compared, the $\nu$-based Wasserstein metric coincides with the metric derived
from solving the linear optimal transport problem, denoted by $d_{LOT,\nu}$ in
[22]. They differ slightly for more general measures; in this case, the
$\nu$-based Wasserstein metric is in fact only a semi-metric.. Linear optimal
transport was mainly used in [22] for image comparison problems, and the base
measure $\nu$ was often taken to be discrete. In that work, and, to the best
of our knowledge, in the considerable literature on linear optimal transport
following from it, the theoretical properties of the metric, especially for
base measures supported on lower dimensional submanifolds, to which we pay
special attention below, have largely been left undeveloped.

Geodesics with respect to the $\nu$-based Wasserstein metric will always be
generalized geodesics with respect to $\nu$, but, for different structures of
$\nu$, very different geometry is induced. In particular, when $\nu$ is
absolutely continuous, we obtain the Hilbert space geometry discussed above,
whereas when $\nu$ is a Dirac mass, we obtain the Wasserstein metric,
independently of the $y$ parameterizing $\nu=\delta_{y}$ within this class. We
pay special attention to the cases in between, in particular when $\nu$
concentrates on a lower dimensional submanifold of $\mathbb{R}^{m}$, in which
case the problem has a natural interplay with the unequal dimensional optimal
transport problem explored in [8], [9], [16] and [17]. In the particular case
when $\nu$ concentrates on a line segment, we show that our metric coincides
with the layerwise-Wasserstein metric (see (10)) introduced in [12] to analyze
anisotropic data such as plants’ root shapes.

We establish three equivalent characterizations of the $\nu$-based Wasserstein
metric, roughly speaking:

  1. 1.

as an optimal transport problem restricted to couplings which are correlated
along $\nu$ (we take this as the definition);

  2. 2.

by optimally coupling conditional probabilities of $\mu_{0}$ and $\mu_{1}$
after disintegrating with respect to optimal transport to $\nu$;

  3. 3.

as limits of multi-marginal optimal transport between $\mu_{0}$, $\mu_{1}$ and
$\nu$.

In many cases of interest, we establish uniqueness of the corresponding
geodesics (although uniqueness of generalized geodesics for regular base
measures was established in [1], they are generally not unique when the base
measure is singular). We also study geodesic convexity of several functionals
which play a key role in optimal transport research; many of these functionals
were originally introduced by McCann [14], who established their displacement
convexity. Using the standard terminology (see Section 5 for the definition of
these terms) convexity along $W_{\nu}$ geodesics of potential energies,
interaction energies and the Wasserstein distance to $\nu$ follow immediately
from known results ( namely, their convexity along any generalized geodesic,
established in [1]), whereas convexity along $W_{\nu}$ geodesics of the
internal energy, under certain conditions, requires a new proof (convexity of
the internal energy is known to hold along some, but not all, generalized
geodesics [1]). We note that this applies in particular to the layerwise-
Wasserstein distance, yielding a far reaching improvement to Corollary 4.2 in
[12]. We also show that when $\nu$ concentrates on a lower dimensional
submanifold, the set of measures $\mu$ for which the model
$(|x-y|^{2},\mu,\nu)$ satisfies a strengthening of the generalized nested
condition ( see Definition 21) is geodesically convex (we recall that
nestedness, introduced in [9] and its higher dimensional generalization from
[16], are important properties of unequal dimensional optimal transport
problems; when present, they greatly simplify analysis of these problems).

We also introduce a class of metrics which is in a certain sense dual to the
$\nu$-based Wasserstein metric, relevant in the case when the measure $\mu$ on
$X\subset\mathbb{R}^{m}$ is fixed, and one would like to interpolate between
measures on a fixed, lower dimensional submanifold $Y$ (see the precise
definition (13)). This is often the case in a variety of applications. The
seemingly natural choice, generalized geodesics with base $\mu$, which
essentially interpolates between Kantorovich potentials, namely the optimal
dual variable of the optimal transport problem, on the $X$ side, does not
generally result in interpolants supported on $Y$. Here, we instead compare
and interpolate between Kantorovich potentials on the $Y$ side in order to
compare and interpolate between measures on $Y$. This is in a certain sense
complementary, or dual, to our original metric on $\mathcal{P}(X)$ (which
involves comparing potentials on $Y$, in order to compare measures on $X$ –
with an additional embedded optimization problem, since potentials on $Y$ do
not uniquely determine measures supported on $X$). We, finally, show how the
ideas introduced here can be applied to prove convergence of computational
methods to find equilibria in some game theoretic models. In particular we
identify conditions under which equilibria are fixed points of a contractive
mapping, implying uniqueness of the equilibrium (although this is easily
deduced by other methods as well) and, perhaps more importantly, that it can
be computed by iterating the mapping. This iteration had already been
introduced as a method of computation by Blanchet-Carlier when $m=1$, but
without a proof of convergence, and in higher dimensions, with a proof of
convergence but for simpler interaction terms [3]. Here, we prove that the
relevant mapping is a contraction with respect to a variant of the dual metric
described above444In fact, the actual metric used in the proof differs
slightly from the dual metric in general, although they coincide under certain
conditions..

The manuscript is organized as follows. In the next section we introduce the
$\nu$-based Wasserstein metric, establish several basic properties of it, and
also introduce our class of dual metrics. In Section 3, we recall relevant
facts about unequal dimensional optimal transport, and prove a new lemma on
the structure of optimal plans which will be crucial in subsequent sections.
In the fourth section, we identify conditions under which the variational
problem arising in the definition of the $\nu$-based Wasserstein metric has a
unique solution, and establish a result on the structure of geodesics for the
$\nu$-based Wasserstein metric. We use this structure in Section 5 to
establish geodesic convexity results. In the sixth section, we identify
conditions under which certain game theoretic equilibria can be characterized
by fixed points of a contractive mapping with respect to an appropriate
metric.

##  2 Definition and basic properties

Throughout this paper, for a given set $S$, a semi-metric will be a function
$d:S\times S\rightarrow[0,\infty)$ satisfying:

  * •

$d(x,y)=0$ if and only if $x=y$ (separation).

  * •

$d(x,y)=d(y,x)$ for all $x,y\in S$ (symmetry).

A semi-metric $d$ will be called a metric if it also satisfies:

  * •

$d(x,y)\leq d(x,z)+d(y,z)$ for all $x,y,z\in S$ (triangle inequality).

We will often refer to $d(x,y)$ as the distance between $x$ and $y$.

###  2.1 Background on optimal transport

In what follows, $\nu\in\mathcal{P}(X)$ will be a fixed reference measure on a
convex, bounded555We have chosen to work on a bounded set $X$ here mostly out
of technical convenience and to keep the presentation simple. We expect that
most results can be extended to unbounded domains under appropriate hypotheses
(for instance, decay conditions on the measures).  domain
$X\subseteq\mathbb{R}^{m}$. Given measures $\mu_{0},\mu_{1}\in\mathcal{P}(X)$,
we denote by $\Pi(\nu,\mu_{i})$ the set of probability measures on $X\times X$
whose marginals are $\nu$ and $\mu_{i}$, for $i=0,1$ and by
$\Pi(\nu,\mu_{0},\mu_{1})$ the set of probability measures on $X\times X\times
X$ with $\nu,\mu_{0}$ and $\mu_{1}$ as marginals. For a measure
$\gamma\in\mathcal{P}(X\times X\times X)$, we will denote its first, second
and third marginals by $\gamma_{y},\gamma_{x_{0}}$ and $\gamma_{x_{1}}$,
respectively. Similarly, we will denote by $\gamma_{yx_{0}}$,
$\gamma_{yx_{1}}$ and $\gamma_{x_{0}x_{1}}$ its projections onto the
appropriate product $X\times X$; for example, $\gamma_{yx_{0}}$ is the push
forward of $\gamma$ under the mapping $(y,x_{0},x_{1})\mapsto(y,x_{0})$.

The optimal transport problem between $\mu_{i}$ and $\nu$, for a general
continuous cost function
$c:\overline{X}\times\overline{X}\rightarrow\mathbb{R}$ is to minimize over
$\pi\in\Pi(\mu_{i},\nu)$

$\int_{X\times X}c(x_{i},y)d\pi(x_{i},y).$ (2)

We will most often be interested in the quadratic cost function,
$c(x_{i},y)=|x_{i}-y|^{2}$, where $|\cdot|$ denotes here the standard
euclidean norm. Notice that in the quadratic case, (2) is the problem arising
in (1). In addition, (2) has a well known dual problem; the minimum in (2) is
equal to the maximum of

$\int_{X}u(x)d\mu_{i}(x)+\int_{X}v(y)d\nu(y)$ (3)

among pairs of functions $(u,v)\in L^{1}(\mu_{i})\times L^{1}(\nu)$ with
$u(x)+v(y)\leq c(x,y)$. It is well known that maximizers to (3) exist and they
may be taken to be $c$-conjugate; that is,

$u(x)=v^{c}(x):=\min_{y\in X}[c(x,y)-v(y)],\text{ }v(y)=u^{c}(y):=\min_{x\in
X}[c(x,y)-u(x)].$

We let $\Pi_{opt}(\nu,\mu_{i})$ be the set of optimal couplings between $\nu$
and $\mu_{i}$ with respect to optimal transport for the quadratic cost
function; that is:

$\Pi_{opt}(\nu,\mu_{i}):=\operatorname{argmin}_{\pi\in\Pi(\nu,\mu_{i})}\int_{X\times
X}|x_{i}-y|^{2}d\pi(x_{i},y).$ (4)

######  Definition 1.

A _Wasserstein geodesic_ between $\mu_{0}$ and $\mu_{1}$ (also known as a
_displacement interpolant_ , using the terminology originally introduced by
McCann [14]) is a curve $\mu_{t}$ in $\mathcal{P}(X)$ of the form
$\mu_{t}=((1-t)e_{0}+te_{1})_{\\#}\pi$ for some
$\pi\in\Pi_{opt}(\mu_{0},\mu_{1})$, where for $i=0,1$, $e_{i}:X\times
X\rightarrow X$ is defined by $e_{i}(x_{0},x_{1})=x_{i}$.

Recall that, in general, a curve $z_{t}$ parametrized by $t\in[0,1]$ in a
metric space $(Z,d)$ is a minimizing geodesic if
$d(z_{s},z_{t})=|s-t|d(z_{0},z_{1})$ for all $s,t\in[0,1]$. It is well known
that the Wasserstein geodesic defined above is in fact a geodesic in this
sense for the Wasserstein metric.

We now give the definition of generalized geodesics from [1].

######  Definition 2.

A generalized geodesic with base measure $\nu$ from $\mu_{0}$ to $\mu_{1}$ is
a curve $\mu_{t}$ in $\mathcal{P}(X)$ of the form
$\mu_{t}=((1-t)e_{0}+te_{1})_{\\#}\gamma$ for some
$\gamma\in\mathcal{P}(X\times X\times X)$ where
$\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ for $i=0,1$.

We note that we are especially interested here in the case where $\nu$ is
singular with respect to Lebesgue measure. Even in this case,
$\Pi_{opt}(\nu,\mu_{i})$ will very often consist of a single probability
measure; in fact, by Brenier’s theorem this is the case as soon as $\mu_{i}$
is absolutely continuous with respect to Lebesgue measure [5]. It will turn
out that our definition below is not a metric on all of $\mathcal{P}(X)$, but
is when restricted to the set $\mathcal{P}_{\nu}^{u}(X)$ of probability
measures on $X$ for which the solution to the optimal transport problem to
$\nu$ is unique; that is, the set such that $\Pi_{opt}(\nu,\mu)$ is a
singleton.

Before closing this section, we recall the well known notion of disintegration
of measures. Given $\pi_{i}\in\Pi(\nu,\mu_{i})$, we disintegrate with respect
to $\nu$. There exists a measurable collection $\mu_{i}^{y}$ of probability
measures on $X$, indexed by $y$, such that

$\pi_{i}(x,y)=\nu(y)\otimes\mu_{i}^{y}(x);$

that is, for every bounded continuous function $g$ on $X\times X$, we have

$\int_{X\times
X}g(x,y)d\pi_{i}(x,y)=\int_{X}\bigg{[}\int_{X}g(x,y)d\mu_{i}^{y}(x)\bigg{]}d\nu(y).$

We will sometimes call $\mu_{i}^{y}$ the _conditional probability_ of
$\pi_{i}$ given $y$.

###  2.2 The $\nu$-based Wasserstein metric

We now define our metric with base point $\nu$ as follows.

######  Definition 3.

Let $\nu\in\mathcal{P}(X)$. For $\mu_{0},\mu_{1}\in\mathcal{P}(X)$, we define
the $\nu$-based Wasserstein metric as

$W_{\nu}(\mu_{1},\mu_{0}):=\sqrt{\inf_{\gamma\in\Gamma}\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma(y,x_{0},x_{1})},$ (5)

where $\Gamma:=\\{\gamma\in\mathcal{P}(X\times X\times
X)\;|\;\gamma_{yx_{i}}\in\Pi_{opt}(\mu_{i},\nu),i=0,1\\}$.

######  Remark 4.

As we will see below, the name $\nu$-based Wasserstein metric is a slight
abuse of terminology, since $W_{\nu}$ is only a semi-metric on
$\mathcal{P}(X)$ in general, although it is a metric on an appropriate subset.

Note that the glueing lemma (see [19][Lemma 5.5], for example) implies the
existence of a $\gamma\in\Pi(\nu,\mu_{0},\mu_{1})$ such that
$\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ for $i=0,1$; therefore, $W_{\nu}$
is well defined. Standard arguments imply the existence of a minimizing
$\gamma$ in (5).

######  Remark 5.

This definition is closely related to the concept of linear optimal transport,
introduced in [22]. The difference is that in linear optimal transport, a
_fixed_ optimal transport $\pi_{\mu_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ is selected
for each $\mu_{i}$ (see equation (3) in [22]), whereas in the definition of
$W_{\nu}$ one minimizes over the entire set $\Pi_{opt}(\nu,\mu_{i})$. For
$\mu_{i}\in\mathcal{P}^{u}_{\nu}(X)$, the two concepts clearly coincide, and
it is on this set that $W_{\nu}$ yields a metric (see Lemma 6 below). Outside
of this set, $W_{\nu}$ still yields a semi-metric, whereas linear optimal
transport might be better described as defining a metric on the selected
$\pi_{\mu_{i}}\in\Pi_{opt}(\nu,\mu_{i})$, since it is dependent on these
choices; this idea will be developed briefly in Remark 8 below, but first let
us rigorously establish that $W_{\nu}$ is indeed a semi-metric.

The proof of the following Lemma is very similar to the proof that the
classical Wasserstein metric is in fact a metric (see for example,
[19][Proposition 5.1]). Recall that a semi-metric satisfies the symmetry and
identity of indiscernibles axioms in the definition of a metric, but does not
satisfy the triangle inequality.

######  Lemma 6.

$W_{\nu}$ is a semi-metric on $\mathcal{P}(X)$. It is a metric on
$\mathcal{P}_{\nu}^{u}(X)$.

###### Proof.

It is immediate that $W_{\nu}(\mu_{0},\mu_{1})\geq 0$, with equality if and
only if $\mu_{0}=\mu_{1}$, and that
$W_{\nu}(\mu_{0},\mu_{1})=W_{\nu}(\mu_{1},\mu_{0})$. Therefore, $W_{\nu}$ is a
semi-metric.

It remains to show that $W_{\nu}$ is a metric on $\mathcal{P}_{\nu}^{u}(X)$;
we must only verify the triangle inequality. Let $\mu_{0},\mu_{1}$ and
$\mu_{2}$ belong to $\mathcal{P}_{\nu}^{u}(X)$. Let
$\gamma_{1}\in\Pi(\nu,\mu_{0},\mu_{1})$ and
$\gamma_{2}\in\Pi(\nu,\mu_{0},\mu_{2})$ be optimal couplings in (5); that is
$W_{\nu}(\mu_{0},\mu_{1})=\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma_{1}(y,x_{0},x_{1})$ and
$W_{\nu}(\mu_{0},\mu_{2})=\int_{X\times X\times
X}|x_{0}-x_{2}|^{2}d\gamma_{2}(y,x_{0},x_{2})$. Now note that both
$(\gamma_{1})_{yx_{0}}$ and $(\gamma_{2})_{yx_{0}}$ are both optimal
transports between $\nu$ and $\mu_{0}$; by the uniqueness assumption, we
therefore have $(\gamma_{1})_{yx_{0}}=(\gamma_{2})_{yx_{0}}$. The glueing
lemma (the version in [20], Lemma 7.6, is sufficiently general) then implies
the existence of a measure $\gamma\in\mathcal{P}(X\times X\times X\times X)$
such that $\gamma_{yx_{0}x_{1}}=\gamma_{1}$ and
$\gamma_{yx_{0}x_{2}}=\gamma_{2}$. We note that $\gamma_{yx_{1}x_{2}}$
satisfies
$(\gamma_{yx_{1}x_{2}})_{yx_{1}}=\gamma_{yx_{1}}=(\gamma_{1})_{yx_{1}}\in\Pi_{opt}(\nu,\mu_{1})$
and
$(\gamma_{yx_{1}x_{2}})_{yx_{2}}=\gamma_{yx_{2}}=(\gamma_{2})_{yx_{2}}\in\Pi_{opt}(\nu,\mu_{2})$.
Therefore, we have

$\displaystyle W_{\nu}(\mu_{1},\mu_{2})$ $\displaystyle\leq$
$\displaystyle\sqrt{\int_{X\times X\times
X}|x_{1}-x_{2}|^{2}d\gamma_{yx_{1}x_{2}}(y,x_{1},x_{2})}$ $\displaystyle=$
$\displaystyle\sqrt{\int_{X\times X\times X\times
X}|x_{1}-x_{2}|^{2}d\gamma(y,x_{0},x_{1},x_{2})}$ $\displaystyle=$
$\displaystyle||x_{1}-x_{2}||_{L^{2}(\gamma)}$ $\displaystyle\leq$
$\displaystyle||x_{1}-x_{0}||_{L^{2}(\gamma)}+||x_{2}-x_{0}||_{L^{2}(\gamma)}$
$\displaystyle=$ $\displaystyle\sqrt{\int_{X\times X\times X\times
X}|x_{1}-x_{0}|^{2}d\gamma(y,x_{0},x_{1},x_{2})}+\sqrt{\int_{X\times X\times
X\times X}|x_{0}-x_{2}|^{2}d\gamma(y,x_{0},x_{1},x_{2})}$ $\displaystyle=$
$\displaystyle\sqrt{\int_{X\times X\times
X}|x_{1}-x_{0}|^{2}d\gamma_{1}(y,x_{0},x_{1})}+\sqrt{\int_{X\times X\times
X}|x_{0}-x_{2}|^{2}d\gamma_{2}(y,x_{0},x_{2})}$ $\displaystyle=$
$\displaystyle W_{\nu}(\mu_{0},\mu_{1})+W_{\nu}(\mu_{0},\mu_{2})$

∎

The following example confirms that the triangle inequality can fail if we do
not restrict to $\mathcal{P}^{u}_{\nu}(X)$.

######  Example 7.

(Failure of the triangle inequality outside of $\mathcal{P}_{\nu}^{u}(X)$) Let
$X\subseteq\mathbb{R}^{2}$, and take
$\nu=\frac{1}{2}[\delta_{(1,0)}+\delta_{(-1,0)}]$,
$\mu_{0}=\frac{1}{2}[\delta_{(0,1)}+\delta_{(0,-1)}]$,
$\mu_{1}=\frac{1}{2}[\delta_{(\varepsilon,1)}+\delta_{(-\varepsilon,-1)}]$,
$\mu_{2}=\frac{1}{2}[\delta_{(-\varepsilon,1)}+\delta_{\varepsilon,-1)}]$, for
some $\varepsilon>0$. Then any measure $\pi\in\Pi(\nu,\mu_{0})$ is optimal
between $\nu$ and $\mu_{0}$. The only optimal transport plan between $\nu$ and
$\mu_{1}$, on the other hand, maps $(1,0)$ to $(\varepsilon,1)$ and $(-1,0)$
to $(-\varepsilon,-1)$. Similarly, the only optimal transport plan between
$\nu$ and $\mu_{2}$, maps $(1,0)$ to $(\varepsilon,-1)$ and $(-1,0)$ to
$(-\varepsilon,1)$. We therefore compute that

$W_{\nu}(\mu_{0},\mu_{1})=\varepsilon=W_{\nu}(\mu_{0},\mu_{2})$

but

$W_{\nu}(\mu_{1},\mu_{2})=2.$

Therefore,
$W_{\nu}(\mu_{1},\mu_{2})>W_{\nu}(\mu_{0},\mu_{1})+W_{\nu}(\mu_{0},\mu_{2})$
for $\varepsilon<1$, and so the triangle inequality fails.

######  Remark 8.

As an alternative to our definition one may equivalently define first a metric
on optimal couplings and then optimize over all such couplings. More
precisely, let $\Pi_{opt}(\nu)=\cup_{\mu\in\mathcal{P}(X)}\Pi_{opt}(\nu,\mu)$
be the subset of optimal couplings in $\mathcal{P}(X\times X)$ whose first
marginal is $\nu$. It is then straightforward to show that

$\tilde{W}_{\nu}(\pi_{0},\pi_{1})=\sqrt{\inf_{\gamma\in\mathcal{P}(X\times
X\times X)|\gamma_{yx_{i}}=\pi_{i},i=0,1}\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma(y,x_{0},x_{1})}$ (6)

is a metric on $\Pi_{opt}(\nu)$, which we will refer to as the _$\nu$ -based
Wasserstein metric on couplings_. Moreover, the $\nu$-based Wasserstein metric
then has the following characterization:

$W_{\nu}(\mu_{0},\mu_{1})=\inf_{\pi_{i}\in\Pi_{opt}(\nu,\mu_{i}),i=0,1}\tilde{W}_{\nu}(\pi_{0},\pi_{1}).$

In addition, we note that the linearized optimal transport framework defined
in [22] is essentially metric (6) between couplings.

We pause now to describe the $\nu$-based Wasserstein metric for several simple
examples of choices for $\nu$.

######  Example 9.

We recall the main example used to introduce generalized geodesics in Section
9.2 of [1]. Let $\nu$ be absolutely continuous with respect to $m$-dimensional
Lebesgue measure on $X$. Then by Brenier’s theorem [5] there exist unique
optimal couplings of the form $(Id,\tilde{T}_{i})_{\\#}\nu$ in
$\Pi_{opt}(\nu,\mu_{i})$, and therefore the only measure $\gamma$ with
$\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ for $i=0,1$ is
$\gamma=(Id,\tilde{T}_{0},\tilde{T}_{1})_{\\#}\nu$. We then have

$W_{\nu}(\mu_{0},\mu_{1})=\int_{X}|\tilde{T}_{0}(y)-\tilde{T}_{1}(y)|^{2}d\nu(y)$

so that the metric space $(\mathcal{P}(X),W_{\nu})$ is isometric to a subset
of the Hilbert space $L^{2}(\nu)$. Geodesics for this metric take the form
$t\mapsto\Big{(}tT_{1}+(1-t)T_{0}\Big{)}_{\\#}\nu$; these are the standard
generalized geodesics found in, for example, Definition 7.31 of [19].

######  Example 10.

At the other extreme, suppose $\nu=\delta_{y}$ is a Dirac mass. Then for any
coupling $\pi\in\Pi(\mu_{0},\mu_{1})$, the measure
$\gamma=\delta_{y}\otimes\pi$ has
$\gamma_{yx_{i}}=\delta\otimes\mu_{i}\in\Pi_{opt}(\nu,\mu_{i})$. Since

$\int_{X\times X\times X}|x_{0}-x_{1}|^{2}d\gamma(y,x_{0},x_{1})=\int_{X\times
X}|x_{0}-x_{1}|^{2}d\pi(x_{0},x_{1})$

we have

$W^{2}_{\nu}(\mu_{0},\mu_{1})=\inf_{\pi\in\Pi(\mu_{0},\mu_{1})}\int_{X\times
X}|x_{0}-x_{1}|^{2}d\pi(x_{0},x_{1})$

which is exactly the standard quadratic Wasserstein metric.

In this paper, we will be especially interested in the cases in between these
extremes, when $\nu$ is singular with respect to Lebesgue measure but not a
Dirac mass. One of the simplest such cases is the following example.

######  Example 11.

Suppose that $\nu$ concentrates on a line segment and is absolutely continuous
with respect to one dimensional Hausdorff measure. It then turns out that the
$\nu$-based Wasserstein metric coincides with the layerwise-Wasserstein metric
introduced in [12]. The proof of this fact is slightly more involved than the
previous two examples, and is included as a separate proposition below
(Proposition 16 – note that the definition of the layerwise-Wasserstein metric
is recalled in equation (10) below as well).

As we show below, $W_{\nu}$ is also related to the following multi-marginal
optimal transport problem. Fix $\varepsilon>0$ and set

$\operatorname{MM}_{\nu}^{\varepsilon}(\mu_{0},\mu_{1}):=\inf_{\gamma\in\Pi(\nu,\mu_{0},\mu_{1})}\int_{X\times
X\times
X}[\varepsilon|x_{0}-x_{1}|^{2}+|x_{0}-y|^{2}+|x_{1}-y|^{2}]d\gamma(y,x_{0},x_{1}).$
(7)

The following result establishes two different characterizations of the
$\nu$-based Wasserstein metric.

######  Theorem 12.

The following holds

  1. 1.

$W^{2}_{\nu}(\mu_{1},\mu_{0})=\inf_{\pi_{i}\in\Pi_{opt}(\mu_{i},\nu),i=0,1}\int_{X}W_{2}^{2}(\mu_{0}^{y},\mu_{1}^{y})d\nu(y)$,
where $\mu_{i}^{y}$ is the conditional probability given $y$ of the optimal
coupling $\pi_{i}=\nu(y)\otimes\mu_{i}^{y}(x)\in\Pi_{opt}(\nu,\mu_{i})$
between $\nu$ and $\mu_{i}$.

  2. 2.

Furthermore, any weak limit point $\overline{\gamma}$ as
$\varepsilon\rightarrow 0$ of minimizers $\gamma_{\varepsilon}$ of the multi-
marginal problem (7) is an optimal coupling between $\mu_{0}$ and $\mu_{1}$
for the problem (5) defining $W_{\nu}$.

###### Proof.

The first part is almost immediate: for fixed
$\pi_{i}\in\Pi_{opt}(\mu_{i},\nu)$, if $\gamma\in\mathcal{P}(X^{3})$ is
disintegrated with respect to $\nu$,
$\gamma(y,x_{0},x_{1})=\gamma^{y}(x_{0},x_{1})\otimes\nu(y)$, then
$\gamma_{x_{i}y}=\pi_{i}$ is equivalent to the conditional probability
$\gamma^{y}$ on $X\times X$ having the conditional probabilities $\mu_{i}^{y}$
of the $\pi_{i}(x_{i},y)=\mu_{i}^{y}(x_{i})\otimes\nu(y)$ as marginals for
almost every fixed $y$. We can therefore rewrite the integral in (5) as
$\int_{Y}\int_{X\times X}|x_{0}-x_{1}|^{2}d\gamma^{y}(x_{0},x_{1})d\nu(y)$.
Lemma 12.4.7 in [1] then implies that we can choose a Borel family
$\gamma^{y}\in\mathcal{P}(X\times X)$, where for $\nu$ almost every $y$,
$\gamma^{y}$ is an optimal coupling between the $\mu_{i}^{y}$. The choice
$\gamma(y,x_{0},x_{1})=\gamma^{y}(x_{0},x_{1})\otimes\nu(y)$ then minimizes
the integral in (5), which yields the desired formula.

Turning to the second point, let $\gamma$ be any competitor in the definition
of $W_{\nu}$; that is, assume $\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ for
$i=0,1$. Since this clearly implies $\gamma\in\Pi(\nu,\mu_{0},\mu_{1})$,
optimality of $\gamma_{\varepsilon}$ in the multi-marginal problem yields

$\begin{split}&\int_{X\times X\times
X}[\varepsilon|x_{0}-x_{1}|^{2}+|x_{0}-y|^{2}+|x_{1}-y|^{2}]d\gamma_{\varepsilon}(y,x_{0},x_{1})\\\
&\leq\int_{X\times X\times
X}[\varepsilon|x_{0}-x_{1}|^{2}+|x_{0}-y|^{2}+|x_{1}-y|^{2}]d\gamma(y,x_{0},x_{1}).\end{split}$
(8)

Taking the limit as $\varepsilon\rightarrow 0$ gives

$\int_{X\times X\times
X}[|x_{0}-y|^{2}+|x_{1}-y|^{2}]d\overline{\gamma}(y,x_{0},x_{1})\leq\int_{X\times
X\times X}[|x_{0}-y|^{2}+|x_{1}-y|^{2}]d\gamma(y,x_{0},x_{1}),$

or

$\displaystyle\int_{X\times
X}|x_{0}-y|^{2}d\overline{\gamma}_{yx_{0}}(y,x_{0})+\int_{X\times
X}|x_{1}-y|^{2}d\overline{\gamma}_{yx_{1}}(y,x_{1})$
$\displaystyle\leq\int_{X\times
X}|x_{0}-y|^{2}]d\gamma_{yx_{0}}(y,x_{0})+\int_{X\times
X}|x_{1}-y|^{2}d\gamma_{yx_{1}}(y,x_{1})$

which immediately implies the optimality of the two-fold marginals of
$\overline{\gamma}$ in (4),
$\overline{\gamma}_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ for $=0,1$.

Furthermore, the optimality of the two-fold marginals of $\gamma$,
$\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$ means that $\int_{X\times X\times
X}|x_{i}-y|^{2}d\gamma(y,x_{0},x_{1})\leq\int_{X\times X\times
X}|x_{i}-y|^{2}d\gamma_{\varepsilon}(y,x_{0},x_{1})$; combined with (8), this
implies that we must have, for all $\varepsilon$,

$\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma_{\varepsilon}(y,x_{0},x_{1})\leq\int_{X\times
X\times X}|x_{0}-x_{1}|^{2}d\gamma(y,x_{0},x_{1}).$

Passing to the limit gives

$\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\overline{\gamma}(y,x_{0},x_{1})\leq\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma(y,x_{0},x_{1}).$

Since this holds for every $\gamma$ with
$\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$, it implies the desired result.

∎

Adapting the techniques in the proof of the second part of the preceding
theorem, we can also establish the following $\Gamma$-convergence result
relating $MM_{\nu}^{\varepsilon}$ and $W_{\nu}$.

######  Proposition 13.

The functional on $\mathcal{P}(X)\times\mathcal{P}(X)$ defined by

$(\mu_{0},\mu_{1})\mapsto
F^{\varepsilon}_{\nu}(\mu_{0},\mu_{1}):=\frac{1}{\varepsilon}\operatorname{MM}_{\nu}^{\varepsilon}(\mu_{0},\mu_{1})-\frac{1}{\varepsilon}W_{2}^{2}(\nu,\mu_{0})-\frac{1}{\varepsilon}W_{2}^{2}(\nu,\mu_{0})$

$\Gamma$-converges to $(\mu_{0},\mu_{1})\mapsto W_{\nu}^{2}(\mu_{0},\mu_{1})$
as $\varepsilon\rightarrow 0$ with respect to the product on
$\mathcal{P}(X)\times\mathcal{P}(X)$ of the weak topology on $\mathcal{P}(X)$
with itself

###### Proof.

Fix $\mu_{0}$ and $\mu_{1}$ in $\mathcal{P}(X)$; to establish
$\Gamma$-convergence, we must:

  1. 1.

Show that whenever $\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon}$ converge
weakly to $\mu_{0},\mu_{1}$ as $\varepsilon\rightarrow 0$ we have

$W_{\nu}^{2}(\mu_{0},\mu_{1})\leq\liminf_{\varepsilon\rightarrow
0}F^{\varepsilon}_{\nu}(\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon})$

  2. 2.

Show that there exists $\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon}$
converging weakly to $\mu_{0},\mu_{1}$ as $\varepsilon\rightarrow 0$ such that

$W_{\nu}^{2}(\mu_{0},\mu_{1})\geq\limsup_{\varepsilon\rightarrow
0}F^{\varepsilon}_{\nu}(\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon})$

We tackle $1$ first. Let $\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon}$
converge weakly to $\mu_{0},\mu_{1}$. Note that for all $\varepsilon$, letting
$\gamma_{\varepsilon}$ be optimal in (7) with marginals
$\mu_{0}^{\varepsilon}$ and $\mu_{1}^{\varepsilon}$, we have $\int_{X\times
X\times X}|x_{i}-y|^{2}d\gamma_{\varepsilon}(x_{0},x_{1},y)\geq
W_{2}^{2}(\nu,\mu_{i}^{\varepsilon})$, and so

$F^{\varepsilon}_{\nu}(\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon})\geq\int_{X\times
X\times X}|x_{0}-x_{1}|^{2}d\gamma_{\varepsilon}(x_{0},x_{1},y).$ (9)

Now, let $\gamma_{0}$ be a weak∗ limit point of the $\gamma_{\varepsilon}$. By
Theorem 5.20 in [21]666Although Theorem 5.20 in [21] is stated only for two
marginal problems, the same result may be proven for multi-marginal problems
in exactly the same way, using the equivalence between $c$-cyclical
monotonicity and optimality established in [11]., $\gamma_{0}$ solves (7) with
$\varepsilon=0$; that is, multi-marginal optimal transport with cost
$c_{0}(x_{0},x_{1},y)=|x_{0}-y|^{2}+|x_{1}-y|^{2}$ and marginals
$\mu_{0},\mu_{1}$ and $\nu$. This means that $\gamma_{x_{i}y}$ must be optimal
for optimal transport with the quadratic cost between $\mu_{i}$ and $\nu$, for
$i=0,1$, respectively. Therefore, $\gamma_{0}$ is a competitor in the problem
(5) used to define $W_{\nu}$ and so

$\int_{X\times X\times X}|x_{0}-x_{1}|^{2}d\gamma_{0}(x_{0},x_{1},y)\geq
W^{2}_{\nu}(\mu_{0},\mu_{1}).$

Passing to the limit in (9), we get

$\liminf_{\varepsilon\rightarrow
0}F^{\varepsilon}_{\nu}(\mu_{0}^{\varepsilon},\mu_{1}^{\varepsilon})\geq\int_{X\times
X\times X}|x_{0}-x_{1}|^{2}d\gamma_{0}(x_{0},x_{1},y)\geq
W^{2}_{\nu}(\mu_{0},\mu_{1})$

along each subsequence for which $\gamma_{\varepsilon}$ converges. This
establishes property 1. Property 2 is simpler; we may take
$\mu_{i}^{\varepsilon}=\mu_{i}$ for $i=0,1$. To see this, note that choosing
$\gamma$ in (7) with optimal two-fold marginals,
$\gamma_{x_{i}y}\in\Pi_{opt}(\mu_{i},\nu)$ so that $\int_{X\times X\times
X}|x_{i}-y|^{2}d\gamma(x_{0},x_{1},y)=W_{2}^{2}(\mu_{0},\mu_{1})$, causes the
last terms in $F^{\varepsilon}_{\nu}$ to cancel, we get

$F^{\varepsilon}_{\nu}(\mu_{0},\mu_{1})\leq\int_{X\times X\times
X}|x_{0}-x_{1}|^{2}d\gamma(x_{0},x_{1},y).$

As this holds for each $\gamma$ with
$\gamma_{x_{i}y}\in\Pi_{opt}(\mu_{i},\nu)$, we can minimize over all such
$\gamma$ to obtain

$F^{\varepsilon}_{\nu}(\mu_{0},\mu_{1})\leq W^{2}_{\nu}(\mu_{0},\mu_{1}).$

Therefore,

$\limsup_{\varepsilon\rightarrow 0}F^{\varepsilon}_{\nu}(\mu_{0},\mu_{1})\leq
W^{2}_{\nu}(\mu_{0},\mu_{1})$

as desired. ∎

######  Remark 14.

In this paper, we will pay special attention to the case where $\nu$ is
concentrated on a lower dimensional submanifold, parametrized by
$f:Y\rightarrow X$, where $Y\subset\mathbb{R}^{n}$, with $n<m$, and $f$ is a
smooth injection. In this case, by a slight abuse of notation, we will often
consider $\nu$ to be a probability measure on $Y$, and the quadratic optimal
transport problem in the definition (4) is equivalent to optimal transport
between $X$ and $Y$ with cost function $c(x,y)=|x-f(y)|^{2}$, or,
equivalently, $c(x,y)=-x\cdot f(y)$.

We next consider the case when $\nu$ concentrates on a line; we show below
that in this case, $W_{\nu}$ corresponds to the layerwise-Wasserstein metric
from [12], whose definition is recalled below.

######  Definition 15.

The layerwise-Wasserstein metric between measures
$\mu_{0},\mu_{1}\in\mathcal{P}(X)$ is given by

$d^{2}_{LW}(\mu_{0},\mu_{1}):=W_{2}^{2}(\mu_{0}^{V},\mu_{1}^{V})+\int_{0}^{1}W_{2}^{2}(\tilde{\mu}_{0}^{l},\tilde{\mu}_{1}^{l})dl$
(10)

where the $\mu_{i}^{V}=\Big{(}x=(x^{1},x^{2},...,x^{m})\mapsto
x^{1}\Big{)}_{\\#}\mu_{i}$ are the vertical marginals of the $\mu_{i}$,
$\tilde{\mu}_{i}$ are rescaled versions of the $\mu_{i}$, defined by
$\tilde{\mu}_{i}=(F_{\mu_{i}},Id)_{\\#}\mu_{i}$ where $F_{\mu_{i}}$ is the
cumulative distribution function of $\mu_{i}^{V}$, with the identity mapping
$Id$ applied on the last $m-1$ coordinates (so that
$(F_{\mu_{i}},Id)(x^{1},x^{2},...,x^{m})=(F_{\mu_{i}}(x^{1}),x^{2},...,x^{m})$)
and $\tilde{\mu}_{i}=\mu_{i}^{l}\otimes dl$ is disintegrated with respect to
its uniform vertical marginal (see [12] for a more detailed description).

######  Proposition 16.

Suppose $\nu$ is concentrated on the line segment
$\\{(t,0,0,...0):t\in\mathbb{R}\\}$ and is absolutely continuous with respect
to $1$-dimensional Hausdorff measure. Then $W_{\nu}$ is equal to the layerwise
Wasserstein metric.

###### Proof.

Using the framework described in Remark 14 with $n=1$ and
$f(y)=(y,0,0,...,0)$, we consider optimal transport between $\mu_{i}$ on $X$
and $\nu$ on $Y\subseteq\mathbb{R}$ with cost function
$|x_{i}-f(y)|^{2}=(x^{1}_{i}-y)^{2}+(x^{2}_{i})^{2}+...(x^{m}_{i})^{2}$, or,
equivalently, the cost function $c(x_{i},y)=(x^{1}_{i}-y)^{2}$. This is an
_index cost_ in the terminology of [16]; that is,
$c(x_{i},y)=\tilde{b}(I(x_{i}),y)$ depends on $x_{i}\in\mathbb{R}^{m}$ only
through the lower dimensional variable $I(x_{i})=x_{i}^{1}$. For such costs,
the optimal transport problem can be solved semi-explicitly, essentially by
solving the optimal transport problem between the one dimensional variables
$I(x_{i})=x_{i}^{1}$ and $y$. We described the solution below.

The level set $(T_{i})^{-1}(y)$ of the optimal transport map
$T_{i}:X\rightarrow Y$ consists of the hyperplane
$\\{(z_{i}(y),x_{i}^{2},...,x_{i}^{m})\\}$ where the fixed $z_{i}(y)$ is
chosen so that

$\mu_{i}(\\{(x_{i}^{1},x_{i}^{2},...x_{i}^{m}):x_{i}^{1}\leq
z_{i}(y)\\})=\nu(-\infty,y).$ (11)

By the first part of Theorem 12, the optimal arrangement $\gamma$ in (5) then
pairs the conditional probability $\mu_{0}^{y}$ on
$\\{z_{0}(y)\\}\times\mathbb{R}^{m-1}$ with the corresponding conditional
probability $\mu_{1}^{y}$ on $\\{z_{1}(y)\\}\times\mathbb{R}^{m-1}$.

By Theorem 12, we then have

$W^{2}_{\nu}(\mu_{0},\mu_{1})=\int_{Y}W_{2}^{2}(\mu_{0}^{y},\mu_{1}^{y})d\nu(y)$

Note that
$|(z_{0}(y),x_{0}^{2},...,x_{0}^{m})-(z_{1}(y),x_{1}^{2},...,x_{1}^{m})|^{2}=|(x_{0}^{2},...,x_{0}^{m})-(x_{1}^{2},...,x_{1}^{m})|^{2}+(z_{0}(y)-z_{1}(y))^{2}$,
so that
$W_{2}^{2}(\mu_{0}^{y},\mu_{1}^{y})=W_{2}^{2}(\hat{\mu}_{0}^{y},\hat{\mu}_{1}^{y})+(z_{0}(y)-z_{1}(y))^{2}$,
where the measures
$\hat{\mu}_{i}^{y}:=\Big{(}(z_{i}(y),x_{i}^{2},...,x_{i}^{m})\mapsto(x_{i}^{2},...,x_{i}^{m})\Big{)}_{\\#}\mu_{i}^{y}$
are measures on $\mathbb{R}^{m-1}$. Letting $F$ be the quantile function of
$\nu$, and changing variables via $l=F(y)$, we have

$\displaystyle W^{2}_{\nu}(\mu_{0},\mu_{1})$ $\displaystyle=$
$\displaystyle\int_{Y}[W_{2}^{2}(\hat{\mu}_{0}^{y},\hat{\mu}_{1}^{y})+(z_{0}(y)-z_{1}(y))^{2}]d\nu(y)$
$\displaystyle=$
$\displaystyle\int_{0}^{1}[W_{2}^{2}(\hat{\mu}_{0}^{F^{-1}(l)},\hat{\mu}_{1}^{F^{-1}(l)})+(z_{0}(F^{-1}(l))-z_{1}(F^{-1}(l))^{2}]dl$

Note that the second term is exactly the Wasserstein metric between the first
marginals of $\mu_{0}$ and $\mu_{1}$. Since the conditional probabilities
$\tilde{\mu}^{l}_{i}$ are both supported on $\\{l\\}\times\mathbb{R}^{m-1}$,
and
$\Big{(}(l,x_{i}^{2},...,x_{i}^{m})\mapsto(x_{i}^{2},...,x_{i}^{m})\Big{)}_{\\#}\tilde{\mu}_{i}^{l}=\hat{\mu}_{i}^{F^{-1}(l)}$,
we have
$W_{2}^{2}(\tilde{\mu}^{l}_{i},\tilde{\mu}^{l}_{i})=W_{2}^{2}(\hat{\mu}_{0}^{F^{-1}(l)},\hat{\mu}_{1}^{F^{-1}(l)})+(l-l)^{2}=W_{2}^{2}(\hat{\mu}_{0}^{F^{-1}(l)},\hat{\mu}_{1}^{F^{-1}(l)})$.
The last line above is then exactly the definition of the layerwise-
Wasserstein metric. ∎

As was noted in [12], in two dimensions the layerwise-Wasserstein metric
corresponds to the Knothe-Rosenblatt rearrangement [13, 18] and so we
immediately obtain the following.

######  Corollary 17.

Let $m=2$. Then, under the assumptions in the preceding Proposition, the
optimal rearrangement $\gamma$ in (5) satisfies
$\gamma_{x_{0}x_{1}}=(Id,G)_{\\#}\mu_{0}$, where $G$ is the Knothe-Rosenblatt
rearrangement.

###### Proof.

For each $y$, the level set of the optimal map $T^{-1}(y)$ is the line segment
$\\{(z_{i}(y),x_{i}^{2})\\}$ where (11) becomes:

$\mu_{i}(\\{(x_{i}^{1},x_{i}^{2}):x_{i}^{1}\leq z_{i}(y)\\})=\nu(-\infty,y).$
(12)

Thus, any matching $\gamma$ with $\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$
must couple $y$ with $\\{(z_{i}(y),x_{i}^{2})\\}$; it follows that
$\gamma_{x_{0}x_{1}}$ must couple $\\{(z_{0}(y),x_{0}^{2})\\}$ to
$\\{(z_{1}(y),x_{1}^{2})\\}$. Since (12) implies
$\mu_{0}(\\{(x_{0}^{1},x_{0}^{2}):x_{0}^{1}\leq
z_{0}(y)\\})=\mu_{1}(\\{(x_{1}^{1},x_{1}^{2}):x_{1}^{1}\leq z_{1}(y)\\})$,
this means that $\gamma_{x_{0}x_{1}}$ is montone in the first coordinate. The
optimal way to couple the conditional probabilites, concentrated on
$\\{(z_{0}(y),x_{0}^{2})\\}$ and $\\{(z_{1}(y),x_{1}^{2})\\}$ is then
monotonic; this exactly characterizes the Knothe-Rosenblatt rearrangement. ∎

######  Remark 18.

One can recover a similar characterization of the Knothe-Rosenblatt
rearrangement in higher dimensions by looking at iterated optimization
problems along an orthogonal basis. This corresponds to the limit of a multi-
marginal problem where the interactions are weighted iteratively, as we show
in Appendix A. This is closely related to the main result in [6], where the
Knothe-Rosenblatt rearrangement is characterized as a limit of optimal
transport maps with anisotropic costs.

###  2.3 Dual metrics

We now define a class of metrics on a lower dimensional space which are dual
to $W_{\nu}$ in a certain sense; more precisely, they use Kantorovich
potentials $v(y)$ on the variable $y$ arising from optimal transport to a
fixed reference measure $\mu(x)$ to compare measures on the $y$ variable,
whereas $W_{\nu}$ uses in part the Kantorovich potential $v(y)$ for optimal
transport from a reference measure $\nu(y)$ on $y$ to measures on $x$ in order
to compare those free measures.

Fix reference measures $\mu\in\mathcal{P}(X)$ and $\sigma\in\mathcal{P}(Y)$ on
bounded domains $X\subseteq\mathbb{R}^{m}$ and $Y\subseteq\mathbb{R}^{n}$,
with $n\leq m$, absolutely continuous with respect to $m$ and $n$ dimensional
Lebesgue measure, respectively. We let
$c:\overline{X}\times\overline{Y}\rightarrow\mathbb{R}$ be a cost function
which is $C^{1}$ up to the boundary and satisfies the _twist condition_ ; that
is, for each fixed $x\in X$, the mapping from $\overline{Y}$ to
$\mathbb{R}^{m}$ defined by

$y\mapsto D_{x}c(x,y)$

is injective. Note that $c\in C^{1}(\overline{X}\times\overline{Y})$ implies
that $c$ is Lipschitz, since $\overline{X}$ and $\overline{Y}$ are compact.

We let $\mathcal{P}_{ac,\sigma}(Y)$ be the set of probability measures on $Y$
which are absolutely continuous with respect to $\sigma$. For measures
$\nu_{0},\nu_{1}\in\mathcal{P}_{ac,\sigma}(Y)$, we define

$W^{*}_{\mu,\sigma,c,p}(\nu_{0},\nu_{1}):=||Dv_{0}-Dv_{1}||_{L^{p}(\sigma)}$
(13)

for some $p\in[1,\infty]$ where $v_{i}$ is the $c$-concave Kantorovich
potential (that is, $c$-conjugate solutions to (3) corresponding to the
optimal transport problem between $\mu$ and $\nu_{i}$ with cost function $c$).

######  Proposition 19.

$W^{*}_{\mu,\sigma,c,p}$ is a metric on $\mathcal{P}_{ac,\sigma}(Y)$.

###### Proof.

Since the $L^{p}$ norm clearly induces a metric, all that needs to be proven
is that for each measure $\nu\in\mathcal{P}_{ac,\sigma}(Y)$, the gradient $Dv$
of the Kantorovich potential is in $L^{p}(\sigma)$, and that the mapping
$\nu\mapsto Dv$ is a bijection. Since the cost function is Lipschitz, a now
standard argument originating in [15], implies that the potential $v$ is
Lipschitz; absolute continuity of $\nu$ with respect to $\sigma$ (and
therefore Lebesgue measure) ensures that it exists $\sigma$ almost everywhere,
by Rademacher’s theorem. Furthermore, since $v$ is semi-convex and Lipschitz,
the gradient $Dv$ is also bounded, and so $Dv\in L^{p}(\sigma)$ for all $p\geq
1$.

Absolute continuity of $\nu$ with respect to $\sigma$, and therefore Lebesgue
measure, ensures that $Dv$ is uniquely determined by $\nu$ [19, Proposition
1.15].

On the other hand, it is well known that the twist condition ensures that the
unique optimizer to the optimal transport problem between $\mu$ and $\nu$
concentrates on a graph, $y=T(x)$, where $T$ is uniquely determined by the
gradient of the potential $u(x)$ via the equation $Du(x)=D_{x}c(x,T(x))$.
Since $\nu=T_{\\#}\mu$, we have that $\nu$ is uniquely determined by $T$ and
therefore $u$. The $c$-concave Kantorovich potential $v(y)=\inf_{x\in
X}[c(x,y)-u(x)]$ is then clearly in one to one correspondence with
$u(x)=\inf_{y\in Y}[c(x,y)-v(y)]$ and, therefore, it uniquely determines
$\nu$. Thus $\nu$ and $Dv$ are in one-to-one correspondence, as desired.

∎

To help explain the motivation behind this metric, it is useful to first
consider the $m=n$ case with $c(x,y)=|x-y|^{2}$. The metric
$W^{*}_{\mu,\sigma,c,2}$ is then similar to the $\nu$-based Wasserstein
metric. Recall from Example 9 that in this case $W_{\nu}(\mu_{0},\mu_{1})$
between two measures in ${\cal P}(X)$ coincides with the $L^{2}$ metric on the
optimal maps from $\nu$ to the $\mu_{i}$; on the other hand,
$W^{*}_{\mu,\sigma,c,2}(\nu_{0},\nu_{1})$ for two measures in ${\cal P}(Y)$
coincides with the $L^{2}$ metric on the optimal maps from the $\nu_{i}$ to
$\mu$. That is, $W^{*}_{\mu,\sigma,c,2}(\nu_{0},\nu_{1})$ compares gradients
of potential on the opposite, rather than same, side of the problem from the
reference measure, and so is in some sense dual to $W_{\nu}$ in Example 9.

The case where $m>n$ is an attempt to generalize this idea in the same way
that the $\nu$-based Wasserstein metric generalizes the $L^{2}$ metric in
Example 9. We emphasize that the motivating example is when $c=|x-f(y)|^{2}$
is quadratic between $x$ and $f(y)$ in a lower dimensional submanifold, using
the convention in Remark 14. In this case, $W^{*}_{\mu,\sigma,c,p}$ is dual to
the $\nu$ based Wasserstein metric, in the sense that it relies on the
Kantorovich potential on the target, rather than source, side.

The metric $W^{*}_{\mu,\sigma,c,p}$ arises naturally in certain variational
problems among measures on $Y$ involving optimal transport to the fixed
measure $\mu$ on $X$, which is more naturally described by the potentials $v$
on $Y$ than $u$ on $X$. We expand on this viewpoint in section 6 below, where
we establish a fixed point characterization of solutions to a class of these
problems. In the proof, we actually use a metric which corresponds to using
the mass splitting $k$, introduced in [16] and recalled in equation (21)
below, rather than potentials (these are the same when the problem satisfies
the nestedness condition introduced in [16], as is the case for the optimal
$\nu$ under appropriate conditions identified in [17] and recalled in (23)
below, but not in general).

##  3 Unequal dimensional optimal transport

When the base measure $\nu$ concentrates on a lower dimensional submanifold,
the definition (5) of the $\nu$-Wasserstein metric relies on unequal
dimensional optimal transport. We briefly review the known theory on this
topic here, and establish a lemma which we will need later on.

For $c(x,y)=-x\cdot f(y)$ as in Remark 14, $y\in Y$ and $p\in-P_{y}$, where
$-P_{y}:=\\{-x\cdot Df(y)\in X:x\in X\\}$, we define, as in [16], noting that
$D_{y}c(x,y)=-x\cdot Df(y)$

$X_{1}(y,p):=\\{x\in X:-x\cdot Df(y)=p\\}.$ (14)

Note that, since our cost is linear in $X$, each $X_{1}(y,p)$ is an affine
$(m-n)$-dimensional submanifold of $X$, provided that $Df(y)$ has full rank.
For a fixed $y$, each $X_{1}(y,p)$ is parallel.

The following result shows that when we disintegrate the optimizer with
respect to $\nu$, the conditional probabilities are absolutely continuous with
respect to $(m-n)$-dimensional Hausdorff measure, and provides a formula for
their densities.

######  Theorem 20.

Consider optimal transport between probability measures $\mu$ on
$X\subseteq\mathbb{R}^{m}$ and $\nu$ on $Y\subseteq\mathbb{R}^{n}$, where
$m>n$, both absolutely continuous with respect to Lebesgue measure, with
densities $\overline{\mu}(x)$ and $\overline{\nu}(y)$, respectively, and cost
function $c(x,y)=-x\cdot f(y)$ where $f\in C^{2}(Y)$ is injective and non-
degenerate, that is $Df(y)$ has full rank everywhere.

Then there is a unique optimal measure $\pi=(Id,T)_{\\#}\mu$ in (2), which
concentrates on the graph of a function $T:X\rightarrow Y$. The Kantorovich
potential $v(y)$ is differentiable for almost every $y$, and at each such
point $T^{-1}(y)$ is concentrated on the affine manifold $X_{1}(y,Dv(y))$. The
conditional probability $\mu^{y}(x)$ corresponding to the disintegration
$\mu=\mu^{y}\otimes\nu(y)$ of $\mu$ with respect to $T$ is absolutely
continuous with respect to $(m-n)$ \- dimensional Hausdorff measure on
$X_{1}(y,Dv(y))$ for almost every $y$. Furthermore, there is a subset
$X(v^{c})\subset X$ of full volume such that this conditional probability is
concentrated on $T^{-1}(y)\cap X(v^{c})$ with density $\overline{\mu}^{y}(x)$
with respect to $(m-n)$ – dimensional Hausdorff measure given by

$\overline{\mu}^{y}(x)=\overline{\mu}(x)/[\overline{\nu}(y)JT^{y}(x)]$ (15)

where $JT^{y}(x)=\frac{\sqrt{\det[Df(y)Df^{T}(y)]}}{\det[-x\cdot
D^{2}f(y)-D^{2}v(y)]}$ is the $n$-dimensional Jacobian of the optimal
transport map defined by $T(x)=(f)^{-1}(-Dv^{c}(x))$, evaluated at any point
$x\in T^{-1}(y)$.

###### Proof.

The existence and uniqueness of an optimal transport map $T$ is well known.
The remainder of the proof is based on the proof of Theorem 2 in [16]. We
repeat the preliminary setup of that argument for the reader’s convenience.
Letting $u(x)=v^{c}(x)$ and $v(y)=u^{c}(y)$ be the Kantorovich potentials, it
is well known that $u$ is semi-concave and therefore its differential $Du(x)$
exists almost everywhere and is locally of bounded variation (see Theorem 6.8
in [10]). Theorem 6.13 in [10] then implies that for each integer $i>0$ there
exists a set $Z_{i}$ of Lebesgue measure less than $1/i$, and a continuously
differentiable map $H_{i}$ with $DH_{i}=Du$ and $D^{2}H_{i}=D^{2}u$ outside of
$Z_{i}$. The $Z_{i}$ may be taken to be nested, that is, $Z_{i+1}\subset
Z_{i}$, and we set $Z_{\infty}=\cap_{i=1}^{\infty}Z_{i}$ and
$X(v^{c})=dom(D^{2}u)\setminus Z_{\infty}$.

Now set $\tilde{Y}=dom(D^{2}v)$ and $\tilde{X}=T^{-1}(\tilde{Y})$. We note
that $u(x)+v(y)-c(x,y)\leq 0$, with equality at $(x,T(x))$. For
$x\in\tilde{X}$, differentiating with respect to $y=T(x)\in\tilde{Y}$ yields
$Dv(y)=x\cdot Df(y)$, or $Dv(T(x))=x\cdot Df(T(x))$. If $x\in dom(DT)$,
differentiating with respect to $x$ then yields:

$[D^{2}v(T(x))-x^{t}D^{2}f(y)]DT(x)=Df(T(x)).$

As the right hand side has full rank by assumption, this means that the
$m\times n$ matrix $DT(x)$ must also have full rank, and so its Jacobian
$JT(x)=det^{1/2}[DT^{t}(x)DT(x)]>0$ must be non-zero. We then set
$\tilde{X}_{i}=\\{x\in\tilde{X}\setminus Z_{i}:|x|\leq i,JT(x)>1/i\\}$ and
$X_{i}=\tilde{X}_{i}\setminus\tilde{X}_{i-1}$, so that $\tilde{X}\setminus
Z_{\infty}=\cup_{i=1}^{\infty}X_{i}$ and the union is pairwise disjoint,

Now, equation (30) in [16] implies that for any $h\in
L^{\infty}(\mathbb{R}^{m})$ we have

$\displaystyle\int_{X_{i}}h(x)\overline{\mu}_{i}(x)dx$ $\displaystyle=$
$\displaystyle\int_{Y}\overline{\nu}(y)\frac{1}{\overline{\nu}(y)}dy\int_{T_{i}^{-1}(y)\cap
X_{i}}\frac{h(x)\overline{\mu}_{i}(x)}{JT^{y}_{i}(x)}d\mathcal{H}^{m-n}(x)$
(16) $\displaystyle=$
$\displaystyle\int_{Y}\overline{\nu}(y)\frac{1}{\overline{\nu}(y)}dy\int_{T_{i}^{-1}(y)\cap
X(v^{s})}\frac{h(x)\overline{\mu}_{i}(x)}{JT_{i}^{y}(x)}d\mathcal{H}^{m-n}(x)$
(17)

One can then sum on $i$ to obtain

$\int_{X}h(x)\overline{\mu}(x)dx=\int_{Y}\overline{\nu}(y)dy\int_{T^{-1}(y)\cap
X(v^{s})}\frac{h(x)\overline{\mu}(x)}{\overline{\nu}(y)JT^{y}(x)}d\mathcal{H}^{m-n}(x).$
(18)

As this holds for every $h\in L^{\infty}(\mathbb{R}^{m})$, it implies the
desired disintegration. ∎

###  3.1 Nestedness and its high dimensional generalization

In what follows, in Section 6 in particular, we will sometimes consider
optimal transport between $\mu$ and $\nu$ with respect to a general cost,
$c(x,y)$ on $X\times Y\subseteq\mathbb{R}^{m}\times\mathbb{R}^{n}$, with
$m\geq n$. In this case, we will denote the analogue of $X_{1}(y,p)$ by

$X^{c}_{1}(y,p):=\\{x\in X:D_{y}c(x,y)=p\\}.$ (19)

Assuming that $c$ is non-degenerate, so that the $m\times n$ matrix
$D^{2}_{xy}c(x,y)$ has full rank $n$, the implicit function theorem implies
that $X^{c}_{1}(y,p)$ is an $m-n$ dimensional submanifold of $X$. If we denote
by $v(y)$ the Kantorovich potential, we have

$c(x,y)-v(y)\geq u(x)=\inf_{y^{\prime}\in Y}(c(x,y^{\prime})-v(y^{\prime}))$

with equality $\gamma$ almost everywhere. For $(x,y)$ such that equality
holds, this implies that $y^{\prime}\mapsto c(x,y^{\prime})-v(y^{\prime})$ is
minimized at $y^{\prime}=y$.

At any such point where $v$ is differentiable, we therefore obtain
$Dv(y)=D_{y}c(x,y)$, so that

$\partial^{c}v(y):=\\{x\in X:c(x,y)-v(y)=\inf_{y^{\prime}\in
Y}(c(x,y^{\prime})-v(y^{\prime}))\\}\subseteq X^{c}_{1}(y,Dv(y)).$

The generalized nestedness condition, introduced in [16] is that this
inclusion is actually an equality.

######  Definition 21.

We say that $(c,\mu,\nu)$ satisfies the _generalized nestedness condition_ if
for all $y$ at which $v$ is differentiable, we have

$\partial^{c}v(y)=X^{c}_{1}(y,Dv(y))$

where $v$ is the $c$-conjugate Kantorovich potential for transport between $u$
and $v$.

The importance of this condition, uncovered in [16], is as follows. Solving
the optimal transport problem (2) is essentially equivalent to solving the
dual problem (3). In turn, it is shown in [16] that the solution $(v^{c},v)$
to (3) can be recovered by solving a partial differential equation for $v$,
which is in general _non-local_ and therefore extremely challenging. Under the
generalized nestedness condition, however, it turns out that this equation
reduces to a local equation, and therefore becomes much more tractable.

The origin of the term generalized nestedness comes from the case when
$Y=(\underline{y},\overline{y})$ is one dimensional, in which case it can be
shown that generalized nestedness is essentially equivalent to nestedness of
the corresponding superlevel sets. More precisely, we define:

$X^{c}_{\geq}(y,p):=\\{x\in X:D_{y}c(x,y)\geq p\\}.$ (20)

Assuming that $\mu$ and $\nu$ are both absolutely continuous, with densities
bounded above and below, for each fixed $y$, we note that the measure
$\mu(X^{c}_{\geq}(y,k))$ of the super level set $X^{c}_{\geq}(y,k)$ is a
decreasing function of $k$. There will then be a unique $k=k(y)$ satisfying
the population balancing condition:

$\mu(X^{c}_{\geq}(y,k))=\nu((\underline{y},y)).$ (21)

The definition of nestedness found in [9] is then the following.

######  Definition 22.

Assume that $Y$ is one dimensional. We say the model $(c,\mu,\nu)$ is nested
if

$X^{c}_{\geq}(y,k(y))\subseteq X^{c}_{\geq}(y^{\prime},k(y^{\prime}))$

whenever $y\leq y^{\prime}$.

The relevance of the nestedness condition is that it allows one to almost
explicitly solve (2) [9]. One can attempt to define a mapping $T:X\rightarrow
Y$ that maps each $x\in X_{1}^{c}(y,k(y))$ to $y$. In general, this may not
result in a well defined mapping, since if $X_{1}^{c}(y,k(y))$ intersects
$X_{1}^{c}(y^{\prime},k(y^{\prime}))$ for $y\neq y^{\prime}$, the procedure
attempts to map each $x$ in the intersection to _both_ $y$ and $y^{\prime}$.
It turns out that the nestedness condition ensures that this does not happen;
furthermore, not only is the mapping $T$ described above well defined for
nested models, but the measure $(Id,T)_{\\#}\mu$ is the solution to the
Kantorovich problem (2) and the $k(y)$ defined above coincides with the
derivative $v^{\prime}(y)$ of the Kantorovich potential.

Before closing this section, we illustrate the nestedness condition with the
following simple example from [9]. Several other examples may be found in [9]
[8][7].

######  Example 23.

Let $c(x,y)=-x\cdot(\cos(y),\sin(y))=-x_{1}\cos(y)-x_{2}\sin(y)$, $\mu$ be
uniform on the subset
$X=\\{x:0<r<1,0<\theta<\overline{\theta}\\}\subset\mathbb{R}^{2}$, of the unit
ball in $\mathbb{R}^{2}$, expressed in polar coordinates, and $\nu$ be uniform
on $Y=(0,\overline{\theta})$. This corresponds to to optimal transport with
the quadratic cost between $X$ and the corresponding circular arc,
parametrized by the angle $y$. The solution clearly maps each $x$ radially
outward to $x/|x|$, so the optimal map is $y=T(x)=\arctan(x_{2}/x_{1})$. We
will illustrate the nestedness concept by considering two cases; in the first
case, the model is nested, and so the procedure described above successfully
constructs the optimal mapping. In the second, the model is not nested, and
the procedure fails to produce a well defined mapping.

Case 1: Suppose that $\overline{\theta}<\pi$. Then $X^{c}_{1}(y,k)=\\{X\in
X:x\cdot(\sin(y),-\cos(y))=k\\}$ is a line segment parallel to
$(\cos(y),\sin(y))$ and $X^{c}_{\geq}(y,k)$ is the portion of $X$ lying below
this line segment. The balancing condition (21) is satisfied for $k=k(y)=0$,
in which case $X^{c}_{1}(y,k)$ passes through the origin and the mass of the
wedge $X^{c}_{\geq}(y,k)=\\{x:0<r<1,0<\theta<y\\}$ satisfies

$\mu(X^{c}_{\geq}(y,k))=y/\overline{\theta}=\nu((0,y)).$

These regions $X^{c}_{\geq}(y,k(y))=X^{c}_{\geq}(y,0)$ are nested,
$X^{c}_{\geq}(y,0)=\\{x:0<r<1,0<\theta<y\\}\subset\\{x:0<r<1,0<\theta<y^{\prime}\\}=X^{c}_{\geq}(y^{\prime},0)$
for $y<y^{\prime}$, and indeed, mapping each $x\in X^{c}_{1}(y,0)$ to $y$
coincides with optimal map, while setting $v^{\prime}(y)=k(y)$ yields the
Kantorovich potential.

Case 2: Suppose now that $\pi<\overline{\theta}<2\pi$. Then for
$y<\overline{\theta}-\pi$, note that the line segment $X^{c}_{1}(y,0)$ through
the origin now intersects $X$ in the quadrant $\\{x_{1},x_{2}<0\\}$ and so
$X^{c}_{\geq}(y,0)=\\{x:0<r<1,0<\theta<y\\}\cup\\{x:0<r<1,\pi+y<\theta<\overline{\theta}\\}$;
we therefore have
$\mu(X^{c}_{\geq}(y,0))=y/\overline{\theta}+\overline{\theta}-\pi-y>y/\overline{\theta}=\nu((0,y))$.
The $k=k(y)$ satisfying (21) must therefore be larger than $0$. Assigning each
$x$ in $X^{c}_{=}(y,k(y))$ to $y$ then clearly does not correspond to the
optimal map, and so the result in [9] implies that the model cannot be nested.
Alternatively, this can be seen directly by noting that $X^{c}_{\geq}(y,k(y))$
contains some point in the quadrant $\\{x_{1},x_{2}<0\\}$ for
$y<\overline{\theta}-\pi$, whereas for $\overline{\theta}-\pi<y^{\prime}<\pi$,
$k(y^{\prime})=0$ as before, so
$X^{c}_{\geq}(y^{\prime},k(y^{\prime}))=\\{x:0<r<1,0<\theta<y\\}$ is contained
in the region where $x_{2}>0$.

###  3.2 Sufficient conditions for nestedness

In our previous work [17], motivated by problems in economics and game theory,
we considered the problem of minimizing among probability measures in
$\mathcal{P}([\underline{y},\overline{y}])$ a class of functionals including:

$\nu\mapsto T_{c}(\mu,\nu)+\int\overline{\nu}(y)\log(\overline{\nu}(y))dy,$
(22)

for a fixed measure $\mu$ on the bounded domain $X\subseteq\mathbb{R}^{m}$,
absolutely continuous with respect to Lebesgue measure, and a fixed domain
$Y:=(\underline{y},\overline{y})\subset\mathbb{R}$. Here
$T_{c}(\mu,\nu):=\inf_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c(x,y)d\pi(x,y)$ is
the cost of optimal transport between $\mu$ and $\nu$ with respect to the cost
function $c(x,y)$ and $\overline{\nu}$ is the density of
$d\nu(y)=\overline{\nu}(y)dy$ with respect to Lebesgue measure (if $\nu$ is
not absolutely continuous, the functional is taken to be infinite).

In [17], we showed that the solution to (22) is nested provided that:

$\sup_{y_{1}\in\operatorname{Y},y_{0}\leq y\leq
y_{1}}\frac{D^{min}_{\mu}(y_{0},y_{1},k(y_{0}))}{y_{1}-y_{0}}-M_{c}\frac{e^{-M_{c}y}}{e^{M_{c}\overline{y}}-e^{M_{c}\underline{y}}}-1<0$
(23)

for all $y_{0}\in\operatorname{Y}$ Here, $k(y_{0})$ is defined by (21),

$D^{min}_{\mu}(y_{0},y_{1},k_{0})=\mu(X_{\geq}(y_{1},k_{max}(y_{0},y_{1},k_{0}))\setminus
X^{c}_{\geq}(y_{0},k_{0}))$

is the minimal mass difference where
$k_{max}(y_{0},y_{1},k_{0})=\sup\\{k:X_{\geq}(y_{0},k_{0})\subseteq
X_{\geq}(y_{1},k)\\}$ and
$M_{c}:=\sup_{(x,y_{0},y_{1})\in(\overline{\operatorname{X}}\times\overline{\operatorname{Y}}\times\overline{Y})}\frac{|c(x,y_{0})-c(x,y_{1})|}{|(x,y_{0})-(x,y_{1})|}$
is the Lipschitz norm with respect to variations in $y$ (note that the
condition has been reformulated slightly from [17], to match the choice of
functional in (22); in [17] more general functionals were studied).

##  4 Uniqueness of optimal couplings and structure of geodesics when $\nu$
concentrates on a lower dimensional submanifold

We note that geodesics for the metric $W_{\nu}$ are generalized geodesics with
base $\nu$, according to the general definition in [1]. When $\nu$ is
sufficiently regular (for instance, absolutely continuous with respect to
Lebesgue measure, as in Example 9), generalized geodesics are _uniquely_
determined by $\mu_{0}$ and $\mu_{1}$. In this case, $\Pi_{opt}(\nu,\mu_{i})$
consists of a single measure concentrated on the graph of a function
$\tilde{T}_{i}:X\mapsto X$ pushing $\nu$ forward to $\mu_{i}$;
$\gamma=(Id,\tilde{T}_{0},\tilde{T}_{1})_{\\#}\nu$ is then the unique measure
satisfying $\gamma_{yx_{i}}\in\Pi_{opt}(\nu,\mu_{i})$, and therefore the
unique coupling minimizing the integral in the definition of
$W_{\nu}(\mu_{0},\mu_{1})$. If $\nu$ is singular, this reasoning does not
apply; existence of minimizers in (5) follows immediately from standard
continuity-compactness results, but they may be non-unique in general.

Here we specialize to the case when $\nu$ concentrates on some lower
dimensional submanifold. Given Proposition 16, we can regard this as a sort of
non-linear generalization of the layerwise-Wasserstein metric. In this
setting, if the $\mu_{i}$ are absolutely continuous with respect to Lebesgue,
we obtain a uniqueness result as a consequence of Theorem 12 and Lemma 26. We
also characterize geodesics with respect to our metric is this setting.

######  Theorem 24.

Assume that both $\mu_{i}$ are absolutely continuous with respect to Lebesgue
measure and that $\nu$ is supported on a smooth $n$-dimensional submanifold of
$X$, and is absolutely continuous with respect to $n$-dimensional Hausdorff
measure. Then the optimal coupling $\gamma$ in (5) is unique and its two-fold
marginal $\gamma_{x_{0}x_{1}}$ is induced by a mapping $G:X\rightarrow X$
pushing $\mu_{0}$ forward to $\mu_{1}$. Letting $T_{i}$ denote the optimal
maps from $\mu_{i}$ to $\nu$, the restriction of $G$ to $T^{-1}_{i}(y)$ is the
optimal mapping pushing $\mu_{0}^{y}$ forward to $\mu_{1}^{y}$ for a.e. $y$,
where, as in Theorem 12, $\mu_{i}(x)=\mu_{i}^{y}(x)\otimes\nu(y)$. This
mapping takes the form $\nabla\varphi^{y}:X_{1}(y,Dv_{0}(y))\rightarrow
X_{1}(y,Dv_{1}(y))$, where
$\varphi^{y}:X_{1}(y,Dv_{0}(y))\rightarrow\mathbb{R}$ is a convex function
defined on the $(m-n)$– dimensional affine subset $X_{1}(y,Dv_{0}(y))$.

###### Proof.

Brenier’s theorem implies that the optimal
$\pi_{i}=(Id,T_{i})_{\sharp}\mu_{i}$ between $\mu_{i}$ and $\nu$ is unique and
concentrated on the graph of a function $T_{i}$ for $i=0,1$ [5]; the
conditional probabilities $\mu_{i}^{y}$ are concentrated on $T_{i}^{-1}(y)$
which are clearly pairwise disjoint. Using the first characterization in
Theorem 12, it is enough to show that for almost every $y$, there is a unique
optimal coupling between the $\mu^{i}(y)$ and that coupling is concentrated on
the graph of a function over $\mu^{0}(y)$. Furthermore, [16] implies that for
almost every $y$ the conditional probabilities $\mu_{i}^{y}$ are concentrated
on $m-n$ dimensional affine subspaces $X_{1}(y,Dv_{i}(y))=\\{x:x\cdot
Df(y)=Dv_{i}(y)\\}$ where $f:Y\rightarrow X$ locally parameterizes the
submanifold supporting $\nu$, as in Remark 14 and $v_{i}$ is the Kantorovich
potential and, by Theorem 20, each $\mu_{i}^{y}$ is absolutely continuous with
respect to $m-n$ dimensional Hausdorff measure. The subspaces
$X_{1}(y,Dv_{0}(y))$ and $X_{1}(y,Dv_{1}(y))$ containing $T^{-1}_{0}(y)$ and
$T^{-1}_{1}(y)$ respectively, are parallel. We decompose each
$x=x^{N}+x^{\perp}$, where $x^{N}$ is in the $m-n$ dimensional null space
$null(Df(y))$ of $Df(y)$ and $x^{\perp}$ in its $n$-dimensional orthogonal
complement, $null(Df(y))^{\perp}$, on which the linear map $Df(y)$ is
injective. Then for $x_{i}\in X_{1}(y,Dv_{i}(y))$, $x_{i}^{\perp}$ must be the
unique element of $null(Df(y))^{\perp}$ such that
$(x_{i}^{\perp})^{T}Df(y)=Dv(y_{i})$; that is, $x_{i}^{\perp}$ is _constant_
on $X_{1}(y,Dv_{i}(y))$.

The quadratic cost between $X_{1}(y,Dv_{0}(y))$ and $X_{1}(y,Dv_{1}(y))$ then
takes the form $|x_{0}-x_{1}|^{2}=|x_{0}^{N}-x_{1}^{N}|^{2}+C$, where
$C=|x_{0}^{\perp}-x_{1}^{\perp}|^{2}$ is constant throughout
$X_{1}(y,Dv_{0}(y))\times X_{1}(y,Dv_{1}(y))$ and therefore doesn’t affect
optimal transport. The optimal transport problem between $\mu_{0}^{y}$ and
$\mu_{1}^{y}$ is then equivalent to optimal transport with respect to the
quadratic cost on $null(Df(y))$, or equivalently, $\mathbb{R}^{m-n}$. The
existence, uniqueness and structure (as the gradient of a convex potential) of
the optimal mapping between them then follows from another application of
Brenier’s theorem. Thus, for almost every $y$, the subset where the optimal
map fails to be uniquely defined has $m-n$ Lebesgue measure $0$, yielding the
desired result. ∎

We now turn to the study of minimizing $W_{\nu}$ geodesics.

######  Proposition 25.

Suppose that $\pi_{0},\pi_{1}\in\Pi_{opt}(\nu)$. Then
$\pi_{t}=((1-t)e_{0}+te_{1},e_{2})_{\\#}\gamma$ is a minimizing geodesic for
the $\nu$-based Wasserstein metric on couplings defined by (6), for each
optimal $\gamma$ in (6), where $e_{0}(x_{0},x_{1},y)=x_{0}$,
$e_{1}(x_{0},x_{1},y)=x_{1}$, and $e_{2}(x_{0},x_{1},y)=y$,

Suppose that $\mu_{0},\mu_{1}\in\mathcal{P}_{\nu}^{u}$. Then the generalized
geodesic $\mu_{t}=((1-t)e_{0}+te_{1})_{\\#}\gamma$ is a minimizing geodesic
for the $\nu$ based Wasserstein metric for each optimal $\gamma$ in (5),
provided that $\mu_{t}\in\mathcal{P}_{\nu}^{u}$ for all $t\in[0,1]$.

###### Proof.

We tackle the first statement first. As in the proof of Lemma 9.2.1 in [1],
$\pi_{t}\in\Pi_{opt}(\nu)$. It is clear that
$\gamma_{t}=(e_{0},(1-t)e_{0}+te_{1},e_{2})_{\\#}\gamma$ has two-fold
marginals $\gamma_{x_{0}y}=\pi_{0}$ and $\gamma_{x_{t}y}=\pi_{t}$. Therefore,

$\displaystyle\tilde{W}^{2}_{\nu}(\pi_{0},\pi_{t})$ $\displaystyle\leq$
$\displaystyle\int_{X\times X\times
X}|x_{0}-x_{t}|^{2}d\gamma_{t}(x_{0},x_{t},y)$ $\displaystyle=$
$\displaystyle\int_{X\times X\times
X}|x_{0}-[(1-t)x_{0}+tx_{1}]|^{2}d\gamma(x_{0},x_{1},y)$ $\displaystyle=$
$\displaystyle\int_{X\times X\times
X}t^{2}|x_{0}-x_{1}|^{2}d\gamma(x_{0},x_{1},y)=t^{2}\tilde{W}^{2}_{\nu}(\pi_{0},\pi_{1})$

So $\tilde{W}_{\nu}(\pi_{0},\pi_{t})\leq t\tilde{W}_{\nu}(\pi_{0},\pi_{1})$. A
very similar argument implies
$\tilde{W}_{\nu}(\pi_{t},\pi_{s})\leq(s-t)\tilde{W}_{\nu}(\pi_{0},\pi_{1})$
for $s>t$, and
$\tilde{W}_{\nu}(\pi_{s},\pi_{1})\leq(1-s)\tilde{W}_{\nu}(\pi_{0},\pi_{1})$.
Adding these three inequalities yields

$\displaystyle\tilde{W}_{\nu}(\pi_{0},\pi_{t})+\tilde{W}_{\nu}(\pi_{t},\pi_{s})+W_{\nu}(\pi_{s},\pi_{1})$
$\displaystyle\leq$ $\displaystyle
t\tilde{W}_{\nu}(\pi_{0},\pi_{1})+(s-t)\tilde{W}_{\nu}(\pi_{0},\pi_{1})+(1-s)\tilde{W}_{\nu}(\pi_{0},\pi_{1})$
$\displaystyle=$ $\displaystyle\tilde{W}_{\nu}(\pi_{0},\pi_{1})$

Since two applications of the triangle inequality imply the opposite
inequality,
$\tilde{W}_{\nu}(\pi_{0},\pi_{1})\leq\tilde{W}_{\nu}(\pi_{0},\pi_{t})+\tilde{W}_{\nu}(\pi_{t},\pi_{s})+W_{\nu}(\pi_{s},\pi_{1})$,
we must have equality throughout; in particular
$\tilde{W}_{\nu}(\pi_{t},\pi_{s})=(s-t)\tilde{W}_{\nu}(\pi_{0},\pi_{1})$, and
so $\pi_{t}$ is a minimizing geodesic for the $\nu$-based Wasserstein metric
on couplings.

The proof of the second assertion is very similar and is omitted. The only
subtely is that in general it is not clear to us that $\mu_{t}$ remains in the
set $\mathcal{P}_{\nu}^{u}$ on which $W_{\nu}$ is a metric, so that property
is added as an assumption. ∎

Under much stronger conditions on the marginals $\mu_{0}$ and $\mu_{1}$ and
the reference measure $\nu$, we are able to use Theorem 24 to show that the
geodesic for the $W_{\nu}$ metric between $\mu_{0}$ and $\mu_{1}$ is unique.

######  Lemma 26 (Structure of geodesics).

Let $\mu_{0}$, $\mu_{1}$ and $\nu$ be as in Theorem 20. Then the geodesic
$\mu_{t}$ between $\mu_{0}$ and $\mu_{1}$ is uniquely defined. The Kantorovich
potential for optimal transport between $\mu_{t}$ and $\nu$ is
$v_{t}=tv_{1}+(1-t)v_{0}$, where $v_{i}:Y\rightarrow\mathbb{R}$ is the
Kantorovich potential between $\mu_{i}$ and $\nu$, for $i=0,1$. For almost
every $y$, the conditional probability $\mu_{t}^{y}$, concentrated on
$X_{1}(y,Dv_{t}(y))$, is the unique displacement interpolant between
$\mu^{y}_{0}$ and $\mu_{1}^{y}$. It is absolutely continuous with respect to
$(m-n)$-dimensional Hausdorff measure; denoting its density by
$\overline{\mu}_{t}^{y}$, and the density of $\mu_{t}$ with respect to
$\mathcal{L}^{m}$ by $\overline{\mu}_{t}$, we have,
$\overline{\mu}_{t}^{y}(x_{t})=\overline{\mu}_{t}(x_{t})/(JT^{y}_{t}(x_{t})\overline{\nu}(y))$
where
$JT^{y}_{t}(x_{t}):=\frac{\sqrt{\det(Df^{T}Df(y))}}{\det[-D^{2}v_{t}(y)-x_{t}\cdot
D^{2}f(y)]}$ is the Jacobian of the optimal map $T_{t}$ from $\mu_{t}$ to
$\nu$, evaluated at $x_{t}\in T_{t}^{-1}(y)\subseteq X_{1}(y,Dv_{t}(y))$.

The Brenier map between $\mu_{0}^{y}$ and $\mu_{t}^{y}$ is then given by
$\nabla\varphi^{y}_{t}=(1-t)I+t\nabla\varphi^{y}$, where
$\nabla\varphi^{y}:T_{0}^{-1}(y)\rightarrow T_{1}^{-1}(y)$ is the Brenier map
between $\mu_{0}^{y}$ and $\mu_{1}^{y}$.

###### Proof.

Constructing $v_{t}$ and each $\mu_{t}^{y}$ as in the statement of the Lemma,
it is clear from Theorem 20 that $v_{t}$ is the Kantorovich potential for
optimal transport between $\mu_{t}(x)=\int_{Y}\mu^{y}_{t}(x)d\nu(y)$ and
$\nu$, and that $\pi_{t}=\nu(y)\otimes\mu_{t}^{y}(x)$ is the unique optimal
transport plan between $\mu_{t}$ and $\nu$. The first part of Theorem 12 then
implies that, for any $s,t$

$W^{2}_{\nu}(\mu_{s},\mu_{t})=\int_{X}W_{2}^{2}(\mu_{t}^{y},\mu_{s}^{y})d\nu(y)=(t-s)^{2}\int_{X}W_{2}^{2}(\mu_{0}^{y},\mu_{1}^{y})d\nu(y)=(t-s)^{2}W^{2}_{\nu}(\mu_{0},\mu_{1})$
(24)

since each $\mu_{t}^{y}$ is a displacement interpolant (that is, a Wasserstein
geodesic) between $\mu_{0}^{y}$ and $\mu_{1}^{y}$. This implies that $\mu_{t}$
is a $W_{\nu}$ geodesic.

Furthermore, the uniqueness of the displacement interpolants $\mu_{t}^{y}$
together implies that any other curve
$\tilde{\mu}_{t}\in\mathcal{P}^{u}_{\nu}(X)$, disintegrated with respect to
$\nu$ as $\tilde{\mu}_{t}^{y}(x)\otimes\nu(y)$, cannot satisfy (24) for all
$s,t$ (as otherwise $\tilde{\mu}_{t}^{y}$ would be a Wasserstein geodesic
between $\mu^{y}_{0}$ and $\mu^{y}_{1}$ for $\nu$ all $y$, which would violate
uniqueness). This yields the desired uniqueness of the $W_{\nu}$ geodesic.

The absolute continuity of $\mu^{y}_{t}$ with respect to $(m-n)$-dimensional
Hausdorff measure on the affine set $X_{1}(y,Dv_{t}(y)$ follows from standard
arguments, since it is the displacement interpolant of two absolutely
continuous measures on parallel affine sets. Absolute continuity of $\mu_{t}$
and the formula relating $\overline{\mu}_{t}$ and $\overline{\mu}_{t}^{y}$
then follows from Theorem 20. Finally, the asserted structure
$\nabla\varphi^{y}_{t}=(1-t)I+t\nabla\varphi^{y}$ of the Brenier map between
between $\mu_{0}^{y}$ and $\mu_{t}^{y}$ then follows by standard optimal
transport arguments applied to the parallel affine subspaces
$X_{1}(y,Dv_{0}(y))$ and $X_{1}(y,Dv_{1}(y))$.

∎

##  5 Convexity properties

We now turn our attention to certain convexity properties of $W_{\nu}$
geodesics. We begin by studying the convexity of various functionals along the
geodesics, and then show that the set of measures satisfying a slight
strengthening of the generalized nested condition is geodesically convex.

###  5.1 Geodesic convexity of functionals

We consider the functionals

$\displaystyle\mu$ $\displaystyle\mapsto$ $\displaystyle W_{2}^{2}(\mu,\nu)$
(25) $\displaystyle\mu$ $\displaystyle\mapsto$
$\displaystyle\int_{X}V(x)d\mu(x)$ (26) $\displaystyle\mu$
$\displaystyle\mapsto$ $\displaystyle\int_{X^{2}}W(x-z)d\mu(x)d\mu(z)$ (27)

and

$\mu\mapsto\left\\{\begin{array}[]{l l}\int U(\overline{\mu}(x))dx&\quad\text{
if }d\mu=\overline{\mu}(x)dx\text{ is a.c. wrt Lebesgue measure on }X\\\
+\infty&\quad\text{ otherwise.}\end{array}\right.$ (28)

Convexity of each of these functionals along more classical interpolants has
been studied extensively. Under suitable conditions, specified below,
functionals (26) – (28) were first shown to be convex along Wasserstein
geodesics (that is, displacement convex) by McCann [14]. Functionals (25) –
(27) were shown to be convex along _every_ generalized geodesic with base
measure $\nu$ in [1]. Functional (28), on the other hand, is not convex along
every generalized geodesics, but it is shown in Proposition 9.3.1 of [1] that
for each $\mu_{0},\mu_{1}\in\mathcal{P}(X)$, there exists a generalized
geodesic joining $\mu_{0}$ to $\mu_{1}$ along which it is convex. In
particular, when the base measure $\nu$ is absolutely continuous with respect
to Lebesgue measure, and so the generalized geodesic between any $\mu_{0}$ and
$\mu_{1}$ is unique, (28) is convex along every generalized geodesics, but
this is often not true for singular base measures.

We will show that these functionals are geodesically convex with respect to
the metric $W_{\nu}$ (under the usual conditions, specified below).
Explicitly, geodesic convexity means that $\mathcal{F}(\mu_{t})$ is a convex
function of $t\in[0,1]$, where
$\mathcal{F}:\mathcal{P}(X)\rightarrow\mathbb{R}$ is any of (27), (28), (26)
or (25). We will restrict our attention to $W_{\nu}$ geodesics $\mu_{t}$ of
the form in Proposition 25; that is,
$\mu_{t}=(te_{0}+(1-t)e_{1})_{\\#}\gamma$, where $\gamma$ is optimal in (5),
under the assumption that each $\mu_{t}\in\mathcal{P}^{u}_{\nu}(X)$, since in
more general situations the existence of a minimizing $W_{\nu}$ geodesic in
the metric space $\mathcal{P}_{\nu}^{u}$ joining $\mu_{0}$ and $\mu_{1}$ is
not clear. We are particularly interested in the case when the endpoints
$\mu_{0}$ and $\mu_{1}$ and reference measure $\nu$ satisfy the assumptions in
Theorem 24, under which the existence of a unique geodesic follows from Lemma
26.

Since the geodesics we consider for $W_{\nu}$ are always generalized
geodesics, the following result follows immediately from Lemma 9.2.1 and
Propositions 9.3.2 and 9.3.5 [1].

######  Proposition 27.

The following functionals are convex along all minimizing $W_{\nu}$ geodesics
of the form in Proposition 25, under the corresponding conditions:

  1. 1.

(25) is geodesically 1-convex for any $\nu$.

  2. 2.

(26) is geodesically convex if $V$ is convex. It is geodesically strictly
convex if $V$ is strictly convex.

  3. 3.

(27) is geodesically convex if W is convex. It is geodesically strictly convex
along the subset of measures with the same barycenter if W is strictly convex.

The geodesic convexity of the internal energy is somewhat more involved; in
particular, as discussed above, unlike the other three forms, it does not hold
for all generalized geodesics. Our proof, under additional restrictions on
$\nu$, uses the structure of the transport map $G$ in a crucial way.

We assume that the reference measure $\nu$ is absolutely continuous with
respect to $n$-dimensional Lebesgue measure on the $n$-dimensional submanifold
$Y$ (using the convention in Remark 14) and consider only geodesics $\mu_{t}$
whose endpoints $\mu_{0}$ and $\mu_{1}$ are absolutely continuous with respect
to $m$-dimensional Lebesgue measure on $X$ with densities with respective
densities $\overline{\mu}_{0}$ and $\overline{\mu}_{1}$. Letting $G$ be the
optimal map in (5), guaranteed to exist by Theorem 24, we will use
$x_{t}=(1-t)x_{0}+tG(x_{0})$ to denote a point in the support of $\mu_{t}$.
Lemma 26 then yields uniqueness of the geodesic $\mu_{t}$, and we adopt
similar notation to Theorem 20 and Lemma 26: $v_{i}$ is the Kantorovich
potential for transport between $\mu_{i}$ and $\nu$, and
$v_{t}=(1-t)v_{0}+tv_{i}$ plays the same role between $\mu_{t}$ and $\nu$.
Letting $T_{t}$ be the optimal transport map sending $\mu_{t}$ to $\nu$, set
$JT^{y}_{t}(x_{t}):=\frac{\sqrt{\det(Df^{T}Df(y))}}{\det[-D^{2}v_{t}(y)-x_{t}\cdot
D^{2}f(y)]}$, and
$\overline{\mu}_{t}^{y}(x_{t})=\overline{\mu}_{t}(x_{t})/(JT^{y}_{t}(x_{t})\overline{\nu}(y))$
the density with respect to $(m-n)$-dimensional Hausdorff measure of the
conditional probability $\mu_{t}^{y}$ after disintegrating $\mu_{t}$ with
respect to $\nu$, using the map $T_{t}$; that is,
$\mu_{t}(x_{t}):=\mu_{t}^{y}(x_{t})\otimes\nu(y)$.

We recall that Lemma 26 imlies that $\mu_{t}^{y}$ is the displacement
interpolant between $\mu_{0}$ and $\mu_{1}$ and that the Brenier map between
$\mu_{0}^{y}$ and $\mu_{t}^{y}$ is then given by
$\nabla\varphi^{y}_{t}=(1-t)I+t\nabla\varphi^{y}$, where
$\nabla\varphi^{y}:T_{0}^{-1}(y)\rightarrow T_{1}^{-1}(y)$ is the Brenier map
between $\mu_{0}^{y}$ and $\mu_{1}^{y}$.

######  Lemma 28.

Assume that the reference measure $\nu$ is absolutely continuous with respect
to $n$-dimensional Hausdorff measure on a smooth $n$-dimensional submanifold
$Y$ and that $\mu_{0}$ and $\mu_{1}$ are absolutely continuous with respect to
Lebesgue measure on $X$. The internal energy at the interpolant is given by

$\begin{split}&\int_{X}U(\overline{\mu}_{t}(x))dx=\\\
&\int_{Y}\frac{1}{\overline{\nu}(y)}\int_{T_{0}^{-1}(y)}U\Big{(}\frac{\overline{\mu}_{0}^{y}(x_{0})\overline{\nu}(y)JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))}{\det(D^{2}\varphi^{y}_{t}(x_{0}))}\Big{)}\frac{1}{JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))}\det(D^{2}\varphi_{t}^{y}(x_{0}))d\mathcal{H}^{m-n}(x_{0})dy\end{split}$
(29)

###### Proof.

Similarly to (18), we can write the internal energy as

$\int_{X}U(\overline{\mu}_{t}(x_{t}))dx_{t}=\int_{Y}\frac{1}{\overline{\nu}(y)}\int_{T_{t}^{-1}(y)\cap
X(v_{t}^{c})}U(\overline{\mu}_{t}^{y}(x_{t})\overline{\nu}(y)JT^{y}_{t}(x_{t}))\frac{1}{JT^{y}_{t}(x_{t})}d\mathcal{H}^{m-n}(x_{t})dy.$

The remainder of the proof is then a matter of rewriting the inner integral as
an integral over $T_{0}^{-1}(y)$, which is standard. For fixed $y$, standard
optimal transport theory applied to the parallel affine subspaces
$X_{1}^{c}(y,Dv_{i}(y))$ implies that the optimal map $\nabla\varphi^{y}$ is
differentiable $\mathcal{H}^{m-n}$ almost everywhere and the Monge-Ampere
equation is satisfied for $\mathcal{H}^{m-n}$ almost every $x_{0}$:

$\overline{\mu}_{0}^{y}(x_{0})=\overline{\mu}_{1}^{y}(\nabla\varphi^{y}(x_{0}))\det
D^{2}\varphi^{y}(x_{0})$

and similarly note that since
$\nabla\varphi^{y}_{t}=(1-t)I+t\nabla\varphi^{y}:T_{0}^{-1}(y)\rightarrow
T_{t}^{-1}(y)$ pushes $\mu_{0}^{y}$ forward to $\mu_{y}^{t}$ and is optimal,
we have

$\overline{\mu}_{0}^{y}(x_{0})=\overline{\mu}_{t}^{y}(\nabla\varphi^{y}_{t}(x_{0}))\det
D^{2}\varphi^{y}_{t}(x_{0})=\overline{\mu}_{t}^{y}(\nabla\varphi^{y}_{t}(x_{0}))\det((1-t)I_{m-n}+tD^{2}\varphi^{y}(x_{0})).$

The result then follows by using the standard optimal transport change of
variables formula on $X_{1}(y,Dv_{0}(y))$, using the change of variables
$x_{t}=\nabla\varphi^{y}_{t}(x_{0})=(1-t)x_{0}+t\nabla\varphi^{y}(x_{0})$ ∎

######  Remark 29.

It is natural to note that the factor
$\det\Big{(}D^{2}\varphi^{y}_{t}(x_{0})\Big{)}/JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))$
appearing in (29) is the determinant of the Jacobian matrix $DG_{t}(x_{0})$
for the optimal mapping $G_{t}$ in Theorem 24 between $\mu_{0}$ and $\mu_{t}$.
It may be helpful to note that the block diagonal matrix $M_{t}$ introduced in
the proof of the following result is _not_ equal to $DG_{t}(x_{0})$.
$DG_{t}(x_{0})$ is in fact block upper triangular, with the same diagonal
blocks are $M_{t}$. The key point in the proof is the observation that
$DG_{t}(x_{0})$ and $M_{t}$ have the same determinant; it is then more
convenient to think of
$\det\Big{(}D^{2}\varphi^{y}_{t}(x_{0})\Big{)}/JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))$
as the determinant of $M_{t}$, since this matrix is positive definite and we
can apply Minkowski’s determinant inequality to it.

######  Corollary 30.

Under the assumption in the preceding Lemma, the internal energy (28) is
geodesically convex assuming $U(0)=0$ and $r\mapsto r^{m}U(r^{-m})$ is convex
and non-increasing.

###### Proof.

Note that
$\det\Big{(}D^{2}\varphi^{y}_{t}(x_{0})\Big{)}/JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))$
is in fact the determinant of the $m\times m$ block diagonal matrix $M_{t}$
with an upper $(m-n)\times(m-n)$ block
$D^{2}\varphi^{y}_{t}(x_{0})=(1-t)I_{m-n}+tD^{2}\varphi^{y}(x_{0})$ and a
lower $n\times n$ block
$\frac{1}{|\det(Df^{T}Df(y))|^{1/2n}}[-D^{2}v_{t}(y)-x_{t}\cdot D^{2}f(y)]$
whose determinant is
$\frac{1}{JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0})}=\frac{1}{|\det(Df^{T}Df(y))|^{1/2}}\det[-D^{2}v_{t}(y)-x_{t}\cdot
D^{2}f(y)]$. Noting that $x_{t}=\nabla\varphi^{y}_{t}(x_{0})$ interpolates
linearly between $x_{0}$ and $x_{1}=\nabla\varphi^{y}_{t}(x_{0})$, and the
potential $v_{t}=(1-t)v_{0}+tv_{1}$ for optimal transport between $\mu_{t}$
and $\nu$ interpolates linearly between $v_{0}$ and $v_{1}$, $M_{t}$ is affine
in $t$.

Now, the first block $D^{2}\varphi^{y}_{t}(x_{0})$ of $M_{t}$ is clearly non-
negative definite by convexity of $\varphi^{y}$. Note that since $v_{t}$ is
the Kantorovich potential for transport between $\mu_{t}$ and $\nu$, we have
for $y=T_{t}(x_{t})$, $D^{2}v_{t}(y)\leq D^{2}_{yy}c(x_{t},y)=x_{t}\cdot
D^{2}f(y)$; therefore, the second block
$\frac{1}{{(\det(Df^{T}Df(y)))^{1/{2n}}}}[-D^{2}v_{t}(y)-x_{t}\cdot
D^{2}f(y)]$ of $M_{t}$ is also non-negative definite. It follows that $M_{t}$
is as well, and Minkowski’s determinant inequality implies that $(\det
M_{t})^{1/m}$ is concave as a function of $t$; the convexity of the integrand
now follows by a standard argument. Indeed, the integrand is the composition
of the concave mapping
$t\mapsto[\det((1-t)I_{m-n}+tD^{2}\varphi^{y}(x_{0}))/JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))]^{1/m}=(\det[M_{t}])^{1/m}$
and the convex, non-increasing mapping $r\mapsto
U(\frac{\overline{\mu}_{0}^{y}(x_{0})\overline{\nu}(y)}{r^{m}})r^{m}$ and
therefore convex. ∎

######  Remark 31.

An important special case occurs when the function $f$ is affine, in which
case $c(x,y)=-x\cdot f(y)$ becomes an index cost. As shown in Proposition 16,
when $Y\subseteq\mathbb{R}$ is one dimensional, the metric $W_{\nu}$ becomes
the layerwise Wasserstein metric from [12], and Corollary 30 generalizes
Corollary 4.2 there (which asserts convexity of the Shannon entropy along
layerwise-Wasserstein geodesics).

######  Remark 32.

In the case where $f$ is affine, so that $Df(y)$ is constant, slightly
improved convexity results can be obtained when we restrict our interpolations
to the class $\mathcal{P}_{\nu,v}(X)$ of probability measures on $X$ whose
Kantorovich potential corresponding to optimal transport to $\nu$ is a fixed
$v$ (up to addition of a constant). (It is worth noting that in our context,
although the potential $v$ does not uniquely determine the measure $\mu$,
which would make $\mathcal{P}_{\nu,v}(X)$ a singleton, it is easy to see that
$\mathcal{P}_{\nu,v}(X)$ is geodesically convex).

In this case, since $v_{t}=v$ is constant, $X_{1}(y,Dv(y))=\\{x:x\cdot
Df(y)=Dv(y)\\}$ on which $\mu^{y}_{t}$ is supported is constant as well. The
curve $\nabla\varphi_{t}^{y}(x_{0})=(1-t)x_{0}+t\nabla\varphi^{y}(x_{0})$ then
moves along $X_{1}(y,Dv(y))$, so that
$JT^{y}_{t}(\nabla\varphi^{y}_{t}(x_{0}))$ is constant as a function of $t$,
and so we can use concavity of $\det^{m-n}$ on the set of positive definite
$(m-n)\times(m-n)$ dimensional matrices to obtain convexity of (28) as soon at
$r\mapsto r^{m-n}U(r^{n-m})$ is convex and nonincreasing, a slight improvement
over the classical condition.

The set $\mathcal{P}_{\nu,v}(X)$ is potentially relevant in the root
comparison applications in [12]. In these applications, the main objective is
to interpolate between the shapes, and as part of the analysis they are first
rescaled so that they have uniform marginals in one (the vertical) direction;
that is, one compares measures $\tilde{\mu}_{0}$ and $\tilde{\mu}_{1}$ on
$[0,1]\times\mathbb{R}^{m-1}$, whose first marginals are Lebesgue. In this
case, if we set $\nu$ to be Lebesgue measure on the line segment
$[0,1]\times\\{0\\}$, then optimal transport between $\mu_{i}$ and $\nu$ is
given by the projection map $x\mapsto x^{1}$ and the Kantorovich potential on
the $y$ side are $v_{i}(y)=y^{2}/2$ for both $i=0,1$.

Therefore, interpolating between these rescaled versions corresponds to
working in $\mathcal{P}_{\nu,v}(X)$, where $\nu$ is uniform measure on
$\\{0\\}\times[0,1]$ and $v(y)=y^{2}/2$, and the slightly improved convexity
results described above apply.

###  5.2 Geodesic convexity of the set of nested sources

Assuming the $\nu$ concentrates on a smooth $n$-dimensional submanifold $Y$,
we now turn our attention to the structure of the set of measures
$\mu\in\mathcal{P}^{u}_{\mu}(X)$ such that optimal transport with quadratic
cost between $\mu$ and $\nu$ satisfies (a strengthening of) the generalized
nested condition. We will show that this set is $W_{\nu}$ convex.

We adopt the convention in Remark 14; the cost is $c(x,y)=-x\cdot f(y)$, where
$f:Y\rightarrow\mathbb{R}^{m}$ for some $Y\subset\mathbb{R}^{n}$. Note that
this cost naturally extends to all $x\in\mathbb{R}^{m}$ using the same
formula. Our strengthening of the nestedness condition requries some
additional notation. For each $y\in Y$, decompose $x\in\mathbb{R}^{m}$ into
$x=x^{y}_{||}+x^{y}_{\perp}$ with $x^{y}_{\perp}\cdot Df(y)=0$ and
$x^{y}_{||}$ orthogonal to the null space of $Df(y)$.

We define the _enhancement of $X$ by $y\in Y$_ as

$X^{y}=\\{x=x^{y}_{\perp}+x^{y}_{||}:x^{y}_{\perp}+\tilde{x}^{y}_{||},\tilde{x}^{y}_{\perp}+x^{y}_{||}\in
X\text{ for some
}\tilde{x}^{y}_{||}\in[null(Df(y))]^{\perp},\tilde{x}^{y}_{\perp}\in
null(Df(y))\\}$

We say that $(c,\mu,\nu)$ satisfies the _enhanced generalized nestedness
condition_ at $y$ if

$X_{1}^{y}(y,Dv(y))=\partial^{c}v(y):=\\{x\in X^{y}:-x\cdot
f(y)-v(y)\leq-x\cdot f(\tilde{y})-v(\tilde{y})\;\forall\tilde{y}\in Y\\},$

where $v$ is the Kantorovich potential. We say that $(c,\mu,\nu)$ satisfies
the _enhanced generalized nestedness condition_ if it satisfies this condition
at almost every $y\in Y$. Since $X\subseteq X^{y}$ for each $y$,
$X_{1}(y,Dv(y))\subseteq X_{1}^{y}(y,Dv(y))$, and so the enhanced generalized
nestedness condition implies the generalized nestedness condition
$X_{1}(y,Dv(y))=\partial^{c}v(y)$ introduced in [16].

######  Proposition 33.

Let $\nu$ be absolutely continuous with respect to $n$-dimensional Hausdorff
measure on the $n$-dimensional submanifold $Y$. Then the set of $\mu$ such
that $(c,\mu,\nu)$ is enhanced generalized nested at $y$ is geodesically
convex with respect to the metric $W_{\nu}$.

###### Proof.

Given Kantorovich potentials $v_{0}$ and $v_{1}$ corresponding to $\mu_{0}$
and $\mu_{1}$, the potential $v_{t}:=(1-t)v_{0}+tv_{1}$ corresponds to the
interpolant $\mu_{t}$. Observe that, since $D_{y}c(x,y)=-x\cdot Df(y)$ is
affine in $x$, the enhanced level sets
$X_{1}^{y}(y,Dv_{t}(y))=(1-t)X_{1}^{y}(y,Dv_{0}(y))+tX_{1}^{y}(y,Dv_{1}(y))$
is the Minkowski sum of the two endpoint enhanced level sets. Letting
$x_{t}=(1-t)x_{0}+tx_{1}\in X_{1}^{y}(y,Dv_{t}(y))$, with each $x_{i}\in
X_{1}^{y}(y,Dv_{i}(y))$, we have by assumption that

$-x_{i}\cdot f(y)-v_{i}(y)\leq x_{i}\cdot f(\tilde{y})-v_{i}(\tilde{y})$

for all $\tilde{y}\in Y$. Taking the weighted average of these two
inequalities yields

$\displaystyle-(1-t)x_{0}\cdot f(y)-(1-t)v_{0}(y)-tx_{1}\cdot f(y)-tv_{1}(y)$
$\displaystyle\leq$ $\displaystyle-(1-t)x_{0}\cdot
f(\tilde{y})-(1-t)v_{i}(\tilde{y})$ $\displaystyle-tx_{1}\cdot
f(\tilde{y})-tv_{1}(\tilde{y})$ $\displaystyle-x_{t}\cdot f(y)-v_{t}(y)$
$\displaystyle\leq$ $\displaystyle x_{t}\cdot f(\tilde{y})-v_{t}(\tilde{y})$

for all $\tilde{y}\in Y$. Thus, $x_{t}\in\partial^{c}v_{t}(y)$ as desired.

∎

##  6 Fixed point characterization of solutions to variational problems

In this section, we consider a fixed measure $\mu$ on the bounded domain
$X\subseteq\mathbb{R}^{m}$, absolutely continuous with respect to Lebesgue
measure with density $\overline{\mu}$, bounded above and below, and a fixed
domain $Y:=(\underline{y},\overline{y})\subset\mathbb{R}$. We are interested
in the minimization problem (22). We recall that this problem belongs to a
class arising in certain game theory problems, introduced in a series of
papers by Blanchet-Carlier [3, 4, 2], in which the fixed measure $\mu$
represents a distribution of players and $Y$ a space of strategies; minimizing
measures $\nu$ in (22) represent equilibrium distributions of strategies. In
general, the dimensions of $m$ and $n$ of the spaces of players and strategies
represent the number of charateristics used to distinguish between them. The
case $m>n$ (including the case $n=1$ treated here) are of particular interest,
since it is often the case that players are highly homogeneous, whereas the
strategies available to them are less varied.

When $m=1$ (so that both players and strategy spaces are one dimensional),
Blanchet-Carlier introduced a characterization of minimizers as fixed points
of a certain mapping. They then iterated that mapping as a way to compute
solutions [3]; however, they did not prove convergence of this scheme.

Here we introduce a similar fixed point characterization for $m\geq 1$.
Furthermore, we prove for any $m$, under certain assumptions, that the mapping
is a contraction with respect to a strategically chosen metric, implying
convergence of the iterative scheme; even for $m=1$, this is a new result. The
key to the proof is choosing a suitable metric; our choice is a slight variant
of the dual metric $W^{*}_{\mu,\mathcal{L},c,1}$ introduced in Section 2.3.

Choose $\underline{d}=\min_{x\in\overline{X},y\in\overline{Y}}\frac{\partial
c}{\partial
y}(x,y),\overline{d}=\max_{x\in\overline{X},y\in\overline{Y}}\frac{\partial
c}{\partial y}(x,y)$.

Let $k\in
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$,
the set of $L^{1}$ functions on $(\underline{y},\overline{y})$ taking values
in $[\underline{d},\overline{d}]$, and set
$v_{k}(y):=\int_{\underline{y}}^{y}k(s)ds$. Note that
$L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$
is a complete metric space. Let

$\overline{\nu}_{k}(y):=\frac{e^{-v_{k}(y)}}{\int_{\underline{y}}^{\overline{y}}e^{-v_{k}(s)}ds}.$
(30)

This is a probability density on $(\underline{y},\overline{y})$; we denote the
corresponding measure by $\nu_{k}(y)$. Note that (30) then defines a mapping,
$L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}\rightarrow\mathcal{P}^{ac}((\underline{y},\overline{y}))$,
where $\mathcal{P}^{ac}((\underline{y},\overline{y}))$ is the set of
absolutely continuous probability measures on $(\underline{y},\overline{y})$:

$k\mapsto\nu_{k}$ (31)

We note that, for any $k\in
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$,
we have

$\displaystyle\nu_{k}(\underline{y},y)$ $\displaystyle=$
$\displaystyle\int_{\underline{y}}^{y}\overline{\nu}_{k}(s)ds$ (32)
$\displaystyle\geq$
$\displaystyle\int_{\underline{y}}^{y}\frac{\underline{d}e^{-\overline{d}(s-\underline{y})}}{1-e^{-\underline{d}(\overline{y}-\underline{y})}}ds$
$\displaystyle=$
$\displaystyle\frac{\underline{d}(1-e^{-\overline{d}(y-\underline{y})})}{\overline{d}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}.$

Similarly,

$\nu_{k}(y,\overline{y})\geq\frac{\underline{d}(e^{-\overline{d}(y-\underline{y})}-e^{-\overline{d}(\overline{y}-\underline{y})})}{\overline{d}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}.$
(33)

We then note that, for a given
$\nu\in\mathcal{P}^{ac}((\underline{y},\overline{y}))$ the mass splitting
property (21) selects a unique $k=k(y)\in[\underline{d},\overline{d}]$ for
each $y\in(\underline{y},\overline{y})$. The resulting function $k(y)$ is then
bounded and so clearly in
$L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$.
We can then think of this process as defining a mapping
$\mathcal{P}^{ac}((\underline{y},\overline{y}))\rightarrow
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$,
$\nu\mapsto k(\cdot)$. Composing this mapping with (31) then yields a
$F:L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}\rightarrow
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$.
Explicitly, defining $\tilde{k}:=F[k]$, we have

$\nu_{k}(\underline{y},y):=\mu(X_{\geq}(y,\tilde{k}(y))).$ (34)

######  Lemma 34.

Let $\nu$ be a minimizer of (22) such that $(c,\mu,\nu)$ is nested. Then
$k(y)=v^{\prime}(y)$ is a fixed point of $F$, where $v$ is the corresponding
Kantorovich potential.

###### Proof.

The first order conditions corresponding to the variational problem are

$v(y)+\log(\overline{\nu}(y))=C$

for some constant $C$, $\nu$ almost everywhere (see, for example, Section 7.4
in [19]), where $\overline{\nu}$ is the density of minimizer $\overline{\nu}$
and $v$ the corresponding Kantorovich potential. This implies that that
$\nu=\nu_{k}$.

Since $(c,\mu,\nu)$ is nested, the $\tilde{k}=F[K]$ defined by (34) coincides
with the derivative of the Kantorovich potential for optimal transport between
$\mu$ and $\nu_{k}=\nu$, which is exactly $k$. ∎

We will prove that, under certain conditions, $F$ is a contraction. The Banach
fixed point theorem will then imply that $F$ has a unique fixed point. Under
conditions ensuring nestedness of the minimizer, Lemma 34, will then ensure
that that fixed point is the minimizer of (22).

We need the following conditions on $X$, $c$ and $\mu$ to ensure $F$ is a
contraction:

  * •

$A:=\max|D_{x}c_{y}(x,y)|<\infty$,

  * •

$B:=\min\overline{\mu}(x)>0$,

  * •

There is a $C>0$ such that, for all $y\in Y$, $x\in X$, using $c_{y}(x,y)$ as
a shorthand for $\frac{\partial c}{\partial y}(x,y)$,

$\mathcal{H}^{m-1}(X_{1}^{c}(y,c_{y}(x,y)))\geq
C\min\big{\\{}\mu(X_{\geq}^{c}(y,c_{y}(x,y))),\mu(X_{\leq}^{c}(y,c_{y}(x,y)))\Big{\\}}.$
(35)

Let us discuss briefly the third condition above. For any $x,y$, setting
$p=c_{y}(x,y)$, the level set $X_{1}^{c}(y,p)$ is an $m-1$ dimensional
submanifold, dividing the region $X$ into the sub and super level sets
$X_{\geq}^{c}(y,p)$ and $X_{\leq}^{c}(y,p)$. The condition implies that if
$X_{1}^{c}(y,p)$ is small, then at least one of $\mu(X_{\geq}^{c}(y,p))$ or
$\mu(X_{\leq}^{c}(y,p))$ must also be (quantitatively) small.

In addition, we set
$H(y)=\max\\{\frac{|e^{(\overline{d}-2\underline{d})(y-\underline{y})}-1|}{|1-e^{-\overline{d}(y-\underline{y})}|},\frac{|e^{(\overline{d}-2\underline{d})(\overline{y}-\underline{y})}-e^{(\overline{d}-2\underline{d})(y-\underline{y}}|}{|(e^{-\overline{d}(y-\underline{y})}-e^{-\overline{d}(\overline{y}-\underline{y})}|}\\}$.

######  Theorem 35.

Assume the three conditions above, and that

$\frac{2A\overline{d}^{3}(1-e^{-\underline{d}(\overline{y}-\underline{y})})^{2}}{BC\underline{d}^{2}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}|\overline{d}-2\underline{d}|}\int_{\underline{y}}^{\overline{y}}H(y)dy<1.$

Then $F$ is a contraction.

######  Remark 36.

The condition appearing in the statement of the theorem looks complicated;
however, all quantities except for $B$ and $C$ can be computed using the cost
function alone ($B$ involves the reference marginal $\mu$ while $C$ involves
both the cost and $\mu$). Since the factor in front of the integral and the
function $H(y)$ are bounded, the limit as
$\overline{y}-\underline{y}\rightarrow 0$ of the left hand side above is $0$;
therefore, the condition will always hold for sufficiently small intervals. We
illustrate these points in a simple example below, where we compute each of
these quantites explicly.

######  Example 37.

Let $X=[-1,1]^{2}\subset\mathbb{R}^{2}$,
$Y=[0,\overline{y}]\subset\mathbb{R}$, and $c(x,y)=-x_{1}y$. We take $\mu$ to
be uniform measure, normalized to have total mass $1$, so that the density is
$\overline{\mu}(x)=1/4$; clearly this means $B=1/4$. We then have
$c_{y}(x,y)=-x_{1}$ so that $\overline{d}=1$, $\underline{d}=-1$, and
$D_{x}c_{y}(x,y)=-(1,0)$, so that $A=1$. We also have that each
$X_{1}^{c}(y,p)=\\{x:x_{1}=-p,\text{ }-1<x_{2}<1\\}$ is a vertical line and so
$\mathcal{H}^{m-1}(X_{1}^{c}(y,c_{y}(x,y)))=\mathcal{H}^{1}(\\{x:x_{1}=-p,\text{
}-1<x_{2}<1\\})=2$. Since
$\mu(X_{\geq}^{c}(y,c_{y}(x,y)))+\mu(X_{\leq}^{c}(y,c_{y}(x,y))=1$, the
minimum of the two values is at most $1/2$, so we can take $C=4$.

It is easy to check that
$\frac{|e^{(\overline{d}-2\underline{d})(y-\underline{y})}-1|}{|1-e^{-\overline{d}(y-\underline{y})}|}=\frac{e^{3y}-1}{1-e^{-y}}$
is increasing and so is bounded above by its value
$\frac{e^{3\overline{y}}-1}{1-e^{-\overline{y}}}$ at the endpoint
$\overline{y}$. Similarly,
$\frac{|e^{(\overline{d}-2\underline{d})(\overline{y}-\underline{y})}-e^{(\overline{d}-2\underline{d})(y-\underline{y}}|}{|(e^{-\overline{d}(y-\underline{y})}-e^{-\overline{d}(\overline{y}-\underline{y})}|}=\frac{e^{3\overline{y}}-e^{3y}}{e^{-y}-e^{-\overline{y}}}$
is decreasing provided $\overline{y}$ is small enough, so it is bounded above
by its value $\frac{e^{3\overline{y}}-1}{1-e^{-\overline{y}}}$ at $y=0$.
Therefore, $H(y)\leq\frac{e^{3\overline{y}}-1}{1-e^{-\overline{y}}}$ and we
have, for sufficiently small $\overline{y}$,

$\displaystyle\frac{2A\overline{d}^{3}(1-e^{-\underline{d}(\overline{y}-\underline{y})})^{2}}{BC\underline{d}^{2}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}|\overline{d}-2\underline{d}|}\int_{\underline{y}}^{\overline{y}}H(y)dy$
$\displaystyle=$
$\displaystyle\frac{2(1-e^{\overline{y}})^{2}}{\frac{1}{4}4(1-e^{-\overline{y}})^{2}3}\int_{0}^{\overline{y}}H(y)dy$
$\displaystyle\leq$
$\displaystyle\frac{2(1-e^{\overline{y}})^{2}}{3(1-e^{-\overline{y}})^{2}}\overline{y}\frac{e^{3\overline{y}}-1}{1-e^{-\overline{y}}}$

This tends to $0$ as $\overline{y}$ does, since
$\frac{(1-e^{\overline{y}})^{2}}{(1-e^{-\overline{y}})^{2}}\rightarrow 1$ and
$\frac{e^{3\overline{y}}-1}{1-e^{-\overline{y}}}\rightarrow 3$, so that for
sufficiently small $\overline{y}$, the condition in Theorem 35 holds.

######  Remark 38 (Relationship to dual metrics).

We show that $F$ is a contraction with respect to the $L^{1}$ metric. Noting
that the mapping $\nu\mapsto k$, where $k$ is defined by the mass splitting
condition $\nu(\underline{y},y)=\mu(X_{\geq}(y,k(y)))$ is a bijection on the
set of non-atomic measures $\nu\in\mathcal{P}(Y)$ (and in particular on the
set $\mathcal{P}^{ac}(Y)$ of measures which are absolutely continuous with
respect to Lebesgue measure $\mathcal{L}$), we can consider the $L^{1}$ metric
to be a metric on $\mathcal{P}^{ac}(Y)$. If $(c,\mu,\nu)$ is nested, then
$k(y)=v^{\prime}(y)$ where $v$ is the Kantorovich dual potential. In this
case, this metric is exactly the dual metric $W^{*}_{\mu,\mathcal{L},c,1}$
from Section 2.3.

###### Proof.

Let $k_{0},k_{1}\in
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$.
Then note that, setting $v_{i}(y):=v_{k_{i}}(y)$,

$\displaystyle|\overline{\nu}_{0}(y)-\overline{\nu}_{1}(y)|$ $\displaystyle=$
$\displaystyle\frac{e^{-v_{0}(y)}}{\int_{\underline{y}}^{\overline{y}}e^{-v_{0}(s)}ds}-\frac{e^{-v_{1}(y)}}{\int_{\underline{y}}^{\overline{y}}e^{-v_{1}(s)}ds}$
(36) $\displaystyle=$
$\displaystyle\Big{|}\frac{1}{\int_{\underline{y}}^{\overline{y}}e^{v_{0}(y)-v_{0}(s)}ds}-\frac{1}{\int_{\underline{y}}^{\overline{y}}e^{v_{1}(y)-v_{1}(s)}ds}\Big{|}$
$\displaystyle=$
$\displaystyle\frac{|\int_{\underline{y}}^{\overline{y}}[e^{v_{1}(y)-v_{1}(s)}-e^{v_{0}(y)-v_{0}(s)}]ds|}{\int_{\underline{y}}^{\overline{y}}e^{v_{0}(y)-v_{0}(s)}ds\int_{\underline{y}}^{\overline{y}}e^{v_{1}(y)-v_{1}(s)}ds}$
$\displaystyle\leq$
$\displaystyle\frac{\int_{\underline{y}}^{\overline{y}}|e^{v_{1}(y)-v_{1}(s)}-e^{v_{0}(y)-v_{0}(s)}|ds}{[e^{\underline{d}(y-\underline{y})}\int_{\underline{y}}^{\overline{y}}e^{-\overline{d}(s-\underline{y})}ds]^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{\overline{d}^{2}\int_{\underline{y}}^{\overline{y}}e^{\overline{d}(y-\overline{y})-\underline{d}(s-\overline{y})}[|v_{0}(y)-v_{1}(y)|+|v_{0}(s)-v_{1}(s)|]ds}{[e^{\underline{d}(y-\underline{y})}(1-e^{-\overline{d}(\overline{y}-\underline{y})})]^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{2\overline{d}^{2}||v_{0}-v_{1}||_{L^{\infty}}e^{\overline{d}(y-\overline{y})}\int_{\underline{y}}^{\overline{y}}e^{-\underline{d}(s-\overline{y})}ds}{[e^{\underline{d}(y-\underline{y})}(1-e^{-\overline{d}(\overline{y}-\underline{y})})]^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{2\overline{d}^{2}||v_{0}-v_{1}||_{L^{\infty}}e^{(\overline{d}-2\underline{d})(y-\overline{y})}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{\underline{d}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{2\overline{d}^{2}||k_{0}-k_{1}||_{L^{1}}e^{(\overline{d}-2\underline{d})(y-\overline{y})}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{\underline{d}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}}.$

Now, from the mass splitting definition of $\tilde{k}$, assuming without loss
of generality that $\tilde{k}_{0}(y)\geq\tilde{k}_{1}(y)$, we compute, using
the co-area formula

$\displaystyle\int_{\underline{y}}^{y}[\overline{\nu}_{1}(s)-\overline{\nu}_{0}(s)]ds=\mu\\{x:\tilde{k}_{0}(y)\geq
c_{y}(x,y)\geq\tilde{k}_{1}(y)\\}$ (37)
$\displaystyle=\int_{\\{x:\tilde{k}_{0}(y)\geq
c_{y}(x,y)\geq\tilde{k}_{1}(y)\\}}\overline{\mu}(x)dx$ (38)
$\displaystyle=\int_{\tilde{k}_{1}(y)}^{\tilde{k}_{0}(y)}\big{(}\int_{X_{=}(y,k)}\frac{1}{|D_{x}c_{y}(x,y)|}\overline{\mu}(x)d\mathcal{H}^{m-1}(x)\big{)}dk$
(39)
$\displaystyle\geq|\tilde{k}_{0}(y)-\tilde{k}_{1}(y)|\frac{1}{\max|D_{x}c_{y}(x,y)|}[\min\overline{\mu}(x)][\min_{\tilde{k}_{1}(y)\leq
k\leq\tilde{k}_{0}(y)}\mathcal{H}^{m-1}(X_{=}(y,k))].$

Now, suppose the minimum of $\mathcal{H}^{m-1}(X_{=}(y,k))$ over
$k\in[\tilde{k}_{1}(y),\tilde{k}_{0}(y)]$ is attained at some $k$; by
assumption (35), either

$\mathcal{H}^{m-1}(X_{=}(y,k))\geq C\mu(X_{\leq}(y,k))$ (40)

or

$\mathcal{H}^{m-1}(X_{=}(y,k))\geq C\mu(X_{\geq}(y,k)).$ (41)

We assume the second case (the proof in the first case is similar), in which
case, we have

$\mathcal{H}^{m-1}(X_{=}(y,k))\geq C\mu(X_{\geq}(y,k))\geq
C\mu(X_{\geq}(y,\tilde{k}_{1}(y))).$

Therefore,

$\displaystyle|\tilde{k}_{1}(y)-\tilde{k}_{0}(y)|\leq\frac{2A\overline{d}^{2}||k_{0}-k_{1}||_{L^{1}}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{BC\underline{d}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}\mu[X_{\geq}(y,\tilde{k}_{1}(y))]}\int_{\underline{y}}^{y}e^{(\overline{d}-2\underline{d})(s-\overline{y})}ds$
$\displaystyle=\frac{2A\overline{d}^{2}||k_{0}-k_{1}||_{L^{1}}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{BC\underline{d}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}\mu[X_{\geq}(y,\tilde{k}_{1}(y))]}\frac{(e^{(\overline{d}-2\underline{d})(y-\overline{y})}-1)}{\overline{d}-2\underline{d}}$
$\displaystyle=\frac{2A\overline{d}^{2}||k_{0}-k_{1}||_{L^{1}}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{BC\underline{d}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}\nu_{k_{1}}(\underline{y},y)}\frac{(e^{(\overline{d}-2\underline{d})(y-\overline{y})}-1)}{\overline{d}-2\underline{d}}$
$\displaystyle\leq\frac{2A\overline{d}^{3}||k_{0}-k_{1}||_{L^{1}}(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{BC\underline{d}^{2}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}}\frac{(e^{(\overline{d}-2\underline{d})(y-\overline{y})}-1)}{\overline{d}-2\underline{d}}\frac{(1-e^{-\underline{d}(\overline{y}-\underline{y})})}{(1-e^{-\overline{d}(y-\underline{y})})}.$

where we have used (32) in the last line. If instead of (41) we have (40), a
very similar argument holds, in which $\mu[X_{\geq}(y,\tilde{k}_{1}(y))]$ and
$\nu_{k_{1}}(\underline{y},y)$ are replaced by
$\mu[X_{\leq}(y,\tilde{k}_{0}(y))]$ and $\nu_{k_{0}}(y,\overline{y})$, the
domain of integration in (37) is replaced by $[y,\overline{y}]$, and we use
(33) instead of (32). In this case, we obtain

$|\tilde{k}_{1}(y)-\tilde{k}_{0}(y)|\leq\frac{2A\overline{d}^{3}||k_{0}-k_{1}||_{L^{1}}(1-e^{-\underline{d}(\overline{y}-\underline{y})^{2}})}{BC\underline{d}^{2}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}}\frac{(e^{(\overline{d}-2\underline{d})(\overline{y}-\underline{y})}-e^{(\overline{d}-2\underline{d})(y-\underline{y})})}{\overline{d}-2\underline{d}}\frac{1}{(e^{-\overline{d}(y-\underline{y})}-e^{-\overline{d}(\overline{y}-\underline{y})})}.$

Therefore, for every $y\in(\underline{y},\overline{y})$, we have

$|\tilde{k}_{1}(y)-\tilde{k}_{0}(y)|\leq\frac{2A\overline{d}^{3}||k_{0}-k_{1}||_{L^{1}}[1-e^{-\underline{d}(\overline{y}-\underline{y})}]^{2}}{BC\underline{d}^{2}[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}|\overline{d}-2\underline{d}|}H(y).$

Integrating yields:

$||\tilde{k}_{1}-\tilde{k}_{0}||_{L^{1}}\leq\Big{(}\frac{2A\overline{d}^{3}[1-e^{-\underline{d}(\overline{y}-\underline{y})}]^{2}}{BC\underline{d}^{2}|\overline{d}-2\underline{d}|[1-e^{-\overline{d}(\overline{y}-\underline{y})}]^{2}}\int_{\underline{y}}^{\overline{y}}H(y)dy\Big{)}||k_{0}-k_{1}||_{L^{1}}$

which is the desired result. ∎

As discussed above, together with the Lemma 34, condition (23) ensuring
nestedness of the solution, and the Banach Fixed Point Theorem, this yields
convergence of a simple iterative algorithm to compute the solution.

######  Corollary 39.

Under the assumptions in Theorem 35, and as well as assumption (23), for any
$k\in
L^{1}\Big{(}(\underline{y},\overline{y});[\underline{d},\overline{d}]\Big{)}$,
the sequence $F^{n}[k]$ converges to a function $k_{fixed}$ whose anti-
derivative is the Kantorovich potential corresponding to the unique minimizer
$\nu$ of (22).

##  Appendix A Hierarchical metrics with multiple reference measures

The $\nu$-based Wasserstein metric can be extended to align with several
different probability measures in a hierarchical way. Given
$\nu_{1},\dots,\nu_{k}\in\mathcal{P}(X)$, we define iteratively
$\Pi^{1}_{opt}=\Pi_{opt}(\nu_{1},\mu_{i})$ and
$\Pi^{j}_{opt}(\nu_{1},...,\nu_{j},\mu_{i})\subseteq\mathcal{\mathcal{missing}}\mathcal{P}(X^{j+1})$
by

$\Pi^{j}_{opt}(\nu_{1},...,\nu_{j},\mu_{i})=\operatorname{argmin}_{\begin{subarray}{c}\gamma_{y_{1},...y_{j-1}x_{i}}\in\Pi^{j-1}_{opt}(\nu_{1},...,\nu_{j-1},\mu_{i})\\\
\gamma_{y_{j}}=\nu_{j}\end{subarray}}\int_{X^{j+1}}|x_{i}-y_{j}|^{2}d\gamma(y_{1},....,y_{j},x_{i}).$

A natural analogue of $W_{\nu}$ is then defined by:

$W^{2}_{\nu_{1},...\nu_{k}}(\mu_{0},\mu_{1})=\inf_{\gamma_{y_{1}...y_{k}x_{i}}\in\Pi^{k}_{opt}(\nu_{1},...,\nu_{k},\mu_{i}),i=0,1}\int_{X^{k+2}}|x_{0}-x_{1}|^{2}d\gamma(y_{1},....,y_{k},x_{0},x_{1}).$
(43)

As before, optimal couplings can be recovered as limits of multi-marginal
problems, where the weights on the interaction terms reflect the hierarchy of
the measures $\nu_{1},...,\nu_{k}$ in the definition of
$W_{\nu_{1},...\nu_{k}}$:

######  Proposition 40.

Let $\nu_{1},....,\nu_{k},\mu_{0},\mu_{1}$ be probability measures on $X$.
Consider the multi-marginal optimal transport problem:

$\int_{X^{k+2}}c_{\varepsilon}(x_{0},x_{1},y_{1},y_{2},...y_{k})d\gamma$ (44)

where
$c_{\varepsilon}=\varepsilon^{n-1}|x_{0}-x_{1}|^{2}+\varepsilon^{n-2}(|x_{0}-y_{n-1}|^{2}+|x_{1}-y_{n-1}|^{2})+\varepsilon^{n-3}(|x_{0}-y_{n-2}|^{2}+|x_{1}-y_{n-2}|^{2})+....+\varepsilon(|x_{0}-y_{2}|^{2}+|x_{1}-y_{2}|^{2})+(|x_{0}-y_{1}|^{2}+|x_{1}-y_{1}|^{2})$.
Then any weak limit $\overline{\gamma}$ of solutions $\gamma_{\varepsilon}$ is
optimal in (43)

###### Proof.

The proof is similar to the proof of the second part of Theorem 12. Letting
$\gamma\in\Pi^{k}_{opt}(\nu_{1},...,\nu_{k},\mu_{i})$ for $i=0,1$, optimality
of $\gamma_{\varepsilon}$ in (44) implies

$\int_{X^{k+2}}c_{\varepsilon}(x_{0},x_{1},y_{1},y_{2},...y_{k})d\gamma_{\varepsilon}\leq\int_{X^{k+2}}c_{\varepsilon}(x_{0},x_{1},y_{1},y_{2},...y_{k})d\gamma.$
(45)

Passing to the limit implies that
$\overline{\gamma}\in\Pi_{opt}^{1}(\mu_{i},\nu)$. Now, combining the fact that
$\gamma\in\Pi_{opt}^{1}(\mu_{i},\nu)$ with (45) implies

$\begin{split}&\int_{X^{k+2}}c_{\varepsilon}(x_{0},x_{1},y_{1},y_{2},...y_{k})-(|x_{0}-y_{1}|^{2}+|x_{1}-y_{1}|^{2})d\overline{\gamma}_{\varepsilon}\\\
&\leq\int_{X^{k+2}}c_{\varepsilon}(x_{0},x_{1},y_{1},y_{2},...y_{k})-(|x_{0}-y_{1}|^{2}+|x_{1}-y_{1}|^{2})d\gamma.\end{split}$

Dividing by $\varepsilon$ and taking the limit then implies that
$\overline{\gamma}\in\Pi_{opt}(\nu_{1},\nu_{2},\mu_{i})$ for $i=0,2$.
Continuing inductively in this way yields the desired result. ∎

As a consequence, we easily obtain the following result, which is similar to
the main result in [6].

######  Corollary 41.

Let $k=n-1$, and $\nu_{1},....\mu_{n-1}$ be probability measures concentrated
on mutually orthogonal line segments, each absolutely continuous with respect
to one dimensional Hausdorff measure. Then solutions $\gamma_{\varepsilon}$ to
the multi-marginal optimal transport problem (44) converge weakly to $\gamma$,
whose $1,2$ marginal is $(Id,G)_{\\#}\mu_{0}$, where $G$ is the Knothe-
Rosenblatt transport from $\mu_{0}$ to $\mu_{1}$.

## References

  * [1] L. Ambrosio, N. Gigli, and G. Savaré.  Gradient Flows in Metric Spaces and in the Space of Probability Measures.  Lectures in Mathematics. Birkhäuser Boston, 2nd edition, 2004.
  * [2] Adrien Blanchet and Guillaume Carlier.  From Nash to Cournot-Nash equilibria via the Monge-Kantorovich problem.  Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 372(2028):20130398, 11, 2014.
  * [3] Adrien Blanchet and Guillaume Carlier.  Remarks on existence and uniqueness of cournot–nash equilibria in the non-potential case.  Mathematics and Financial Economics, 8(4):417–433, 2014.
  * [4] Adrien Blanchet and Guillaume Carlier.  Optimal transport and Cournot-Nash equilibria.  Math. Oper. Res., 41(1):125–145, 2016.
  * [5] Yann Brenier.  Polar factorization and monotone rearrangement of vector-valued functions.  Communications on pure and applied mathematics, 44(4):375–417, 1991\.
  * [6] G. Carlier, A. Galichon, and F. Santambrogio.  From Knothe’s transport to Brenier’s map and a continuation method for optimal transport.  SIAM J. Math. Anal., 41(6):2554–2576, 2009/10.
  * [7] Pierre-André Chiappori, Robert McCann, and Brendan Pass.  Transition to nestedness in multi- to one-dimensional optimal transport.  European J. Appl. Math., 30(6):1220–1228, 2019.
  * [8] Pierre-Andre Chiappori, Robert J McCann, and Brendan Pass.  Multidimensional matching.  Preprint at arXiv:1604.05771.
  * [9] Pierre-André Chiappori, Robert J. McCann, and Brendan Pass.  Multi- to one-dimensional optimal transport.  Comm. Pure Appl. Math., 70(12):2405–2444, 2017.
  * [10] Lawrence C. Evans and Ronald F. Gariepy.  Measure theory and fine properties of functions.  Textbooks in Mathematics. CRC Press, Boca Raton, FL, revised edition, 2015\.
  * [11] Claus Griessler.  $C$-cyclical monotonicity as a sufficient criterion for optimality in the multimarginal Monge-Kantorovich problem.  Proc. Amer. Math. Soc., 146(11):4735–4740, 2018.
  * [12] Young-Heon Kim, Brendan Pass, and David J Schneider.  Optimal transport and barycenters for dendritic measures.  Pure and Applied Analysis, 2(3):581–601, 2020.
  * [13] Herbert Knothe.  Contributions to the theory of convex bodies.  Michigan Math. J., 4:39–52, 1957.
  * [14] R. J. McCann.  A convexity principle for interacting gases.  Advances in Mathematics, 128(1):153–179, 1997.
  * [15] Robert J. McCann.  Polar factorization of maps on Riemannian manifolds.  Geom. Funct. Anal., 11(3):589–608, 2001.
  * [16] Robert J. McCann and Brendan Pass.  Optimal transportation between unequal dimensions.  Arch. Ration. Mech. Anal., 238(3):1475–1520, 2020.
  * [17] Luca Nenna and Brendan Pass.  Variational problems involving unequal dimensional optimal transport.  Journal de Mathématiques Pures et Appliquées, 139:83–108, 2020.
  * [18] Murray Rosenblatt.  Remarks on a multivariate transformation.  Ann. Math. Statistics, 23:470–472, 1952.
  * [19] Filippo Santambrogio.  Optimal transport for applied mathematicians.  Progress in Nonlinear Differential Equations and their Applications, 87\. Birkhäuser/Springer, Cham, 2015.  Calculus of variations, PDEs, and modeling.
  * [20] C. Villani.  Topics in Optimal Transportation, volume 58 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, 2003.
  * [21] C. Villani.  Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften.  Springer, 2009.
  * [22] Wei Wang, Dejan Slepčev, Saurav Basu, John A. Ozolek, and Gustavo K. Rohde.  A linear optimal transportation framework for quantifying and visualizing variations in sets of images.  Int. J. Comput. Vis., 101(2):254–269, 2013.