# Linear optimal partial transport embedding

Yikun Bai<EMAIL_ADDRESS>Ivan Medri
<EMAIL_ADDRESS>Rocio Diaz Martin
<EMAIL_ADDRESS>Rana Muhammad Shahroz Khan
<EMAIL_ADDRESS>Soheil Kolouri<EMAIL_ADDRESS>
###### Abstract

Optimal transport (OT) has gained popularity due to its various applications
in fields such as machine learning, statistics, and signal processing.
However, the balanced mass requirement limits its performance in practical
problems. To address these limitations, variants of the OT problem, including
unbalanced OT, Optimal partial transport (OPT), and Hellinger Kantorovich
(HK), have been proposed. In this paper, we propose the Linear optimal partial
transport (LOPT) embedding, which extends the (local) linearization technique
on OT and HK to the OPT problem. The proposed embedding allows for faster
computation of OPT distance between pairs of positive measures. Besides our
theoretical contributions, we demonstrate the LOPT embedding technique in
point-cloud interpolation and PCA analysis.

##  1 Introduction

The Optimal Transport (OT) problem has found numerous applications in machine
learning (ML), computer vision, and graphics. The probability metrics and
dissimilarity measures emerging from the OT theory, e.g., Wasserstein
distances and their variations, are used in diverse applications, including
training generative models [3, 24, 33], domain adaptation [16, 15], bayesian
inference [28], regression [26], clustering [42], learning from graphs [29]
and point sets [35, 36], to name a few. These metrics define a powerful
geometry for comparing probability measures with numerous desirable
properties, for instance, parameterized geodesics [2], barycenters [18], and a
weak Riemannian structure [40].

In large-scale machine learning applications, optimal transport approaches
face two main challenges. First, the OT problem is computationally expensive.
This has motivated many approximations that lead to significant speedups [17,
13, 39]. Second, while OT is designed for comparing probability measures, many
ML problems require comparing non-negative measures with varying total amounts
of mass. This has led to the recent advances in unbalanced optimal transport
[14, 12, 32] and optimal partial transport [8, 20, 21]. Such
unbalanced/partial optimal transport formulations have been recently used to
improve minibatch optimal transport [37] and for point-cloud registration [4].

Comparing $K$ (probability) measures requires the pairwise calculation of
transport-based distances, which, despite the significant recent computational
speed-ups, remains to be relatively expensive. To address this problem, [41]
proposed the Linear Optimal Transport (LOT) framework, which linearizes the
2-Wasserstein distance utilizing its weak Riemannian structure. In short, the
probability measures are embedded into the tangent space at a fixed reference
measure (e.g., the measures’ Wasserstein barycenter) through a logarithmic
map. The Euclidean distances between the embedded measures then approximate
the 2-Wasserstein distance between the probability measures. The LOT framework
is computationally attractive as it only requires the computation of one
optimal transport problem per input measure, reducing the otherwise quadratic
cost to linear. Moreover, the framework provides theoretical guarantees on
convexifying certain sets of probability measures [34, 1], which is critical
in supervised and unsupervised learning from sets of probability measures. The
LOT embedding has recently found diverse applications, from comparing collider
events in physics [9] and comparing medical images [5, 30] to permutation
invariant pooling for comparing graphs [29] and point sets [35].

Many applications in ML involve comparing non-negative measures (often
empirical measures) with varying total amounts of mass, e.g., domain
adaptation [19]. Moreover, OT distances (or dissimilarity measures) are often
not robust against outliers and noise, resulting in potentially high
transportation costs for outliers. Many recent publications have focused on
variants of the OT problem that allow for comparing non-negative measures with
unequal mass. For instance, the optimal partial transport (OPT) problem [8,
20, 21], Kantorovich–Rubinstein norm [25, 31], and the Hellinger–Kantorovich
distance [11, 32]. These methods fall under the broad category of “unbalanced
optimal transport” [12, 32]. The existing solvers for “unbalanced optimal
transport” problems are generally as expensive or more expensive than the OT
solvers. Hence, computation time remains a main bottleneck of these
approaches.

To reduce the computational burden for comparing unbalanced measures, [10]
proposed a clever extension for the LOT framework to unbalanced nonnegative
measures by linearizing the Hellinger-Kantorovich, denoted as Linearized
Hellinger-Kantorovich (LHK), distance, with many desirable theoretical
properties. However, an unintuitive caveat about HK and LHK formulation is
that the geodesic for the transported portion of the mass does not resemble
the OT geodesic. In particular, the transported mass does not maintain a
constant mass as it is transported (please see Figure 1). In contrast, OPT
behaves exactly like OT for the transported mass with the trade-off of losing
the Riemannian structure of HK.

Contributions: In this paper, inspired by OT geodesics, we provide an OPT
interpolation technique using its dynamic formulation and explain how to
compute it for empirical distributions using barycentric projections. We use
this interpolation to embed the space of measures in a euclidean space using
optimal partial transport concerning a reference measure. This allows us to
extend the LOT framework to LOPT, a linearized version of OPT. Thus, we reduce
the computational burden of OPT while maintaining the decoupling properties
between noise (created and destroyed mass) and signal (transported mass) of
OPT. We propose a LOPT discrepancy measure and a LOPT interpolating curve and
contrast them with their OPT counterparts. Finally, we demonstrate
applications of the new framework in point cloud interpolation and PCA
analysis, showing that the new technique is more robust to noise.

Organization: In section 2, we review Optimal Transport Theory and the Linear
Optimal Transport framework to set the basis and intuitions on which we build
our new techniques. In Section 3 we review Optimal Partial Transport Theory
and present an explicit solution to its Dynamic formulation that we use to
introduce the Linear Optimal Partial Transport framework (LOPT). We define
LOPT Embedding, LOPT Discrepancy, LOPT interpolation and give explicit ways to
work with empirical data. In Section 4, we show applications of the LOPT
framework to approximate OPT distances, to interpolate between point cloud
datasets, and to preprocess data for PCA analysis. In the appendix, we provide
proofs for all the results, new or old, for which we could not find a proof in
the literature.

Figure 1: The depiction of the HK and OPT geodesics between two measures, at
$t\in\\{0,0.25,0.5,0.75,1\\}$. Mass decreases and then increases while being
transported for HK, while it remains constant for OPT.

##  2 Background: OT and LOT

###  2.1 Static Formulation of Optimal Transport

Let $\mathcal{P}(\Omega)$ be the set of Borel probability measures defined in
a convex compact subset $\Omega$ of $\mathbb{R}^{d}$, and consider
$\mu^{0},\mu^{j}\in\mathcal{P}(\Omega)$. The Optimal Transport (OT) problem
between $\mu^{0}$ and $\mu^{j}$ is that of finding the cheapest way to
transport all the mass distributed according to the reference measure
$\mu^{0}$ onto a new distribution of mass determined by the target measure
$\mu^{j}$. Mathematically, it was stated by Kantorovich as the minimization
problem

$\displaystyle
OT(\mu^{0},\mu^{j}):=\inf_{\gamma\in\Gamma(\mu^{0},\mu^{j})}C(\gamma;\mu^{0},\mu^{j})$
(1) $\displaystyle\text{for }\quad
C(\gamma;\mu^{0},\mu^{j}):=\int_{\Omega^{2}}\|x^{0}-x^{j}\|^{2}d\gamma(x^{0},x^{j}),$
(2)

where $\Gamma(\mu^{0},\mu^{j})$ is the set of all joint probability measures
in $\Omega^{2}$ with marginals $\mu^{0}$ and $\mu^{j}$. A measure
$\gamma\in\Gamma(\mu^{0},\mu^{j})$ is called a transportation plan, and given
measurable sets $A,B\in\Omega$, the coupling $\gamma(A\times B)$ describes how
much mass originally in the set $A$ is transported into the set $B$. The
squared of the Euclidean distance111More general cost functions might be used,
but they are beyond the scope of this article. $\|x^{0}-x^{j}\|^{2}$ is
interpreted as the cost of transporting a unit mass located at $x^{0}$ to
$x^{j}$. Therefore, $C(\gamma;\mu^{0},\mu^{j})$ represents the total cost of
moving $\mu^{0}$ to $\mu^{j}$ according to $\gamma$. Finally, we will denote
the set of all plans that achieve the infimum in (1), which is non-empty [40],
as $\Gamma^{*}(\mu^{0},\mu^{j})$.

Under certain conditions (e.g. when $\mu^{0}$ has continuous density), an
optimal plan $\gamma$ can be induced by a rule/map $T$ that takes all the mass
at each position $x$ to a unique point $T(x)$. If that is the case, we say
that $\gamma$ does not split mass and that it is induced by a map T. In fact,
it is concentrated on the graph of $T$ in the sense that for all measurable
sets $A,B\subseteq\Omega$, $\,\gamma(A\times B)=\mu^{0}(\\{x\in A:\,T(x)\in
B\\})$, and we will write it as the pushforward $\gamma=(\mathrm{id}\times
T)_{\\#}\mu^{0}$. Hence, (1) reads as

$OT(\mu^{0},\mu^{j})=\int_{\Omega}\|x-T(x)\|^{2}d\mu^{0}(x)$ (3)

The function $T:\Omega\to\Omega$ is called a Monge map, and when $\mu^{0}$ is
absolutely continuous it is unique [7].

Finally, the square root of the optimal value $OT(\cdot,\cdot)$ is exactly the
so-called Wasserstein distance, $W_{2}$, in $\mathcal{P}(\Omega)$ [40,
Th.7.3], and we will call it also as OT squared distance. In addition, with
this distance, $\mathcal{P}(\Omega)$ is not only a metric space but also a
Riemannian manifold [40]. In particular, the tangent space of any
$\mu\in\mathcal{P}(\Omega)$ is $\mathcal{T}_{\mu}\subseteq
L^{2}(\Omega;\mathbb{R}^{d},\mu)=\\{u:\Omega\to\mathbb{R}^{d}:\|u\|_{\mu}^{2}<\infty\\}$,
where

$\|u\|_{\mu}^{2}:=\int_{\Omega}\|u(x)\|^{2}d\mu(x).$ (4)

###  2.2 Dynamic Formulation of Optimal Transport

To understand the framework of Linear Optimal Transport (LOT) we will use the
dynamic formulation of the OT problem. Optimal plans and maps can be viewed as
a static way of matching two distributions. They tell us where each mass in
the initial distribution should end, but they do not tell the full story of
how the system evolves from initial to final configurations.

In the dynamic formulation, we consider
$\rho\in\mathcal{P}([0,1]\times\Omega)$ a curve of measures parametrized in
time that describes the distribution of mass
$\rho_{t}:=\rho(t,\cdot)\in\mathcal{P}(\Omega)$ at each instant $0\leq t\leq
1$. We will require the curve to be sufficiently smooth, to have boundary
conditions $\rho_{0}=\mu^{0}$, $\rho_{1}=\mu^{j}$, and to satisfy the
conservation of mass law. Then, it is well known that there exists a velocity
vector field $v_{t}$ such that $\rho_{t}$ satisfies the continuity
equation222The continuity equation is satisfied weakly or in the sense of
distributions. See [40, 38]. with boundary conditions

$\partial_{t}\rho+\nabla\cdot\rho
v=0,\qquad\rho_{0}=\mu^{0},\quad\rho_{1}=\mu^{j}.$ (5)

The length333Precisely, the length of the curve $\rho$, with respect to the
Wasserstein distance, should be $\int_{0}^{1}\|v_{t}\|_{\rho_{t}}dt$, but this
will make no difference in the solutions of (6) since they are constant speed
geodesics. See [38].  of the curve can be stated as
$\int_{[0,1]\times\Omega}\|v\|^{2}d\rho:=\int_{0}^{1}\|v_{t}\|_{\rho_{t}}^{2}dt$,
for $\|\cdot\|_{\rho_{t}}$ as in (4), and $OT(\mu^{0},\mu^{j})$ coincides with
the length of shortest curve between $\mu^{0}$ and $\mu^{j}$ [6]. Hence, the
dynamical formulation of the OT problem (1) reads as

$\displaystyle
OT(\mu^{0},\mu^{j})=\inf_{(\rho,v)\in\mathcal{CE}(\mu^{0},\mu^{j})}\int_{[0,1]\times\Omega}\|v\|^{2}d\rho,$
(6)

where $\mathcal{CE}(\mu^{0},\mu^{j})$ is the set of pairs $(\rho,v)$, where
$\rho\in\mathcal{P}([0,1]\times\Omega)$, and
$v:[0,1]\times\Omega\to\mathbb{R}^{d}$, satisfying (5).

Under the assumption of existence of an optimal Monge map $T$, an optimal
solution for (6) can be given explicitly and is pretty intuitive. If a
particle starts at position $x$ and finishes at position $T(x)$, then for
$0<t<1$ it will be at the point

$T_{t}(x):=(1-t)x+tT(x).$ (7)

Then, varying both the time $t$ and $x\in\Omega$, the mapping (7) can be
interpreted as a flow whose time velocity444For each
$(t,x)\in(0,1)\times\Omega$, the vector $v_{t}(x)$ is well defined as $T_{t}$
is invertible. See [38, Lemma 5.29]. is

$v_{t}(x)=T(x_{0})-x_{0},\qquad\text{ for }x=T_{t}(x_{0}).$ (8)

To obtain the curve of probability measures $\rho_{t}$, one can evolve
$\mu^{0}$ through the flow $T_{t}$ using the formula
$\rho_{t}(A)=\mu_{0}(T_{t}^{-1}(A))$ for any measurable set $A$. That is,
$\rho_{t}$ is the push-forward of $\mu^{0}$ by $T_{t}$

$\rho_{t}=(T_{t})_{\\#}\mu^{0},\qquad 0\leq t\leq 1.$ (9)

The pair $(\rho,v)$ defined by (9) and (8) satisfies the continuity equation
(5) and solves (6). Moreover, the curve $\rho_{t}$ is a constant speed
geodesic in $\mathcal{P}(\Omega)$ between $\mu^{0}$ and $\mu^{j}$ [22], i.e.,
it satisfies that for all $0\leq s\leq t\leq 1$

$\sqrt{OT(\rho_{s},\rho_{t})}=(t-s)\sqrt{OT(\rho_{0},\rho_{1})}.$ (10)

A confirmation of this comes from comparing the OT cost (3) with (8) obtaining

$\displaystyle OT(\mu^{0},\mu^{j})$
$\displaystyle=\int_{\Omega}\|v_{0}(x)\|^{2}d\mu^{0}(x)$ (11)

which tells us that we only need the speed at the initial time to compute the
total length of the curve. Moreover, $OT(\mu^{0},\mu^{j})$ coincides with the
squared norm of the tangent vector $v_{0}$ in the tangent space
$\mathcal{T}_{\mu^{0}}$ of $\mathcal{P}(\Omega)$ at $\mu^{0}$.

###  2.3 Linear Optimal Transport Embedding

Inspired by the induced Riemannian geometry of the $OT$ squared distance, [41]
proposed the so-called Linear Optimal Transportation (LOT) framework. Given
two target measures $\mu^{i},\mu^{j}$, the main idea relies on considering a
reference measure $\mu^{0}$ and embed these target measures into the tangent
space $\mathcal{T}_{\mu^{0}}$. This is done by identifying each measure
$\mu^{j}$ with the curve (9) minimizing $OT(\mu^{0},\mu^{j})$ and computing
its velocity (tangent vector) at $t=0$ using (8).

Formally, let us fix a continuous probability reference measure $\mu^{0}$.
Then, the LOT embedding [34] is defined as

$\displaystyle\mu^{j}\mapsto u^{j}:=T^{j}-\mathrm{id}\qquad\forall\
\mu^{j}\in\mathcal{P}(\Omega)$ (12)

where $T^{j}$ is the optimal Monge map between $\mu^{0}$ and $\mu^{j}$. Notice
that by (3), (4) and (11) we have

$\|u^{j}\|^{2}_{\mu^{0}}=OT(\mu^{0},\mu^{j}).$ (13)

After this embedding, one can use the distance in $\mathcal{T}_{\mu^{0}}$
between the projected measures to define a new distance in
$\mathcal{P}(\Omega)$ that can be used to approximate $OT(\mu^{i},\mu^{j})$.
The LOT squared distance is defined as

$\displaystyle LOT_{\mu^{0}}(\mu^{i},\mu^{j}):=\|u^{i}-u^{j}\|_{\mu^{0}}^{2}.$
(14)

###  2.4 LOT in the Discrete Setting

For discrete probability measures $\mu^{0},\mu^{j}$ of the form

$\mu^{0}=\sum_{n=1}^{N_{0}}p^{0}_{n}\delta_{x^{0}_{n}},\qquad\mu^{j}=\sum_{n=1}^{N_{j}}p^{j}_{n}\delta_{x^{j}_{n}},$
(15)

a Monge map $T^{j}$ for $OT(\mu^{0},\mu^{j})$ may not exist. Following [41],
in this setting, the target measure $\mu^{j}$ can be replaced by a new measure
$\hat{\mu}^{j}$ for which an optimal transport Monge map exists. For that,
given an optimal plan $\gamma^{j}\in\Gamma^{*}(\mu^{0},\mu^{j})$, it can be
viewed as a $N_{0}\times N_{i}$ matrix whose value at position $(n,m)$
represents how much mass from $x^{0}_{n}$ should be taken to $x^{j}_{m}$.
Then, we define the OT barycentric projection555We refer to [2] for the
rigorous definition. of $\mu^{j}$ with respect to $\mu^{0}$ as

$\hat{\mu}^{j}:=\sum_{n=1}^{N_{0}}p^{0}_{n}\delta_{\hat{x}_{n}^{j}},\,\text{where}\quad\hat{x}_{n}^{j}:=\frac{1}{p_{n}^{0}}\sum_{m=1}^{N_{j}}\gamma^{j}_{n,m}x_{m}^{j}.$
(16)

The new measure $\hat{\mu}^{j}$ is regarded as an $N_{0}$-point representation
of the target measure $\mu^{j}$. The following lemma guarantees the existence
of a Monge map between $\mu^{0}$ and $\hat{\mu}^{j}$.

######  Lemma 2.1.

Let $\mu^{0}$ and $\mu^{j}$ be two discrete probability measures as in (15),
and consider an OT barycentric projection $\hat{\mu}^{j}$ of $\mu^{j}$ with
respect to $\mu^{0}$ as in (16). Then, the map
$x_{n}^{0}\mapsto\hat{x}_{n}^{j}$ given by (16) solves the OT problem
$OT(\mu^{0},\hat{\mu}^{j})$.

It is easy to show that if the optimal transport plan $\gamma^{j}$ is induced
by a Monge map, then $\hat{\mu}^{j}=\mu^{j}$. As a consequence, the OT
barycentric projection is an actual projection in the sense that it is
idempotent.

Similar to the continuous case (12), given a discrete reference measure
$\mu^{0}$, we can define the LOT embedding for a discrete measure $\mu^{j}$ as
the rule

$\mu^{j}\mapsto
u^{j}:=[(\hat{x}_{1}^{j}-x^{0}_{1}),\ldots,(\hat{x}_{N_{0}}^{j}-x^{0}_{N_{0}})].$
(17)

The range $\mathcal{T}_{\mu_{0}}$ of this application is identified with
$\mathbb{R}^{d\times N_{0}}$ with the norm
$\|u\|_{\mu^{0}}:=\sum_{n=1}^{N_{0}}\|u(n)\|^{2}p_{n}^{0}$, where
$u(n)\in\mathbb{R}^{d}$ denotes the $n$th entry of $u$. We call
$(\mathbb{R}^{d\times N_{0}},\|\cdot\|_{\mu^{0}})$ the embedding space.

By the discussion above, if the optimal plan $\gamma^{j}$ for problem
$\text{OT}(\mu^{0},\mu^{j})$ is induced by a Monge map, then the discrete
embedding is consistent with (13) in the sense that

$\displaystyle\|u^{j}\|_{\mu^{0}}^{2}=OT(\mu^{0},\hat{\mu}^{j})=OT(\mu^{0},\mu^{j}).$
(18)

Hence, as in section 2.3, we can use the distance between embedded measures in
($\mathbb{R}^{d\times{N_{0}}},\|\cdot\|_{\mu_{0}})$ to define a discrepancy in
the space of discrete probabilities that can be used to approximate
$OT(\mu^{i},\mu^{j})$. The LOT discrepancy777In [41], LOT is defined by the
infimum over all possible optimal pairs $(\gamma^{i},\gamma^{j})$. We do not
distinguish these two formulations for convenience in this paper.
Additionally, (19) is determined by the choice of $(\gamma^{i},\gamma^{j})$.
is defined as

$\displaystyle LOT_{\mu^{0}}(\mu^{i},\mu^{j}):=\|u^{i}-u^{j}\|_{\mu^{0}}^{2}.$
(19)

We call it a discrepancy because it is not a squared metric between discrete
measures. It does not necessarily satisfy that $LOT(\mu^{i},\mu^{j})=0$ for
every distinct $\mu^{i},\mu^{j}$. Nevertheless, $\|u^{i}-u^{j}\|_{\mu^{0}}$ is
a metric in the embedding space.

###  2.5 OT and LOT Geodesics in Discrete Settings

Let $\mu^{i}$, $\mu^{j}$ be discrete probability measures as in (15) (with
‘$i$’ in place of $0$). If an optimal Monge map $T$ for $OT(\mu^{i},\mu^{j})$
exists, a constant speed geodesic $\rho_{t}$ between $\mu^{i}$ and $\mu^{j}$,
for the OT squared distance, can be found by mimicking (9). Explicitly, with
$T_{t}$ as in (7),

$\rho_{t}=(T_{t})_{\\#}\mu^{i}=\sum_{n=1}^{N_{i}}p_{n}^{i}\delta_{(1-t)x_{n}^{i}+tT(x_{n}^{i})}.$
(20)

In practice, one replaces $\mu^{j}$ by its OT barycentric projection with
respect to $\mu^{i}$ (and so, the existence of an optimal Monge map is
guaranteed by Lemma 2.1).

Now, given a discrete reference $\mu^{0}$, the LOT discrepancy provides a new
structure to the space of discrete probability densities. Therefore, we can
provide a substitute for the OT geodesic (20) between $\mu^{i}$ and $\mu^{j}$.
Assume we have the embeddings $\mu^{i}\mapsto u^{i}$, $\mu^{j}\mapsto u^{j}$
as in (17). The geodesic between $u^{i}$ and $u^{j}$ in the LOT embedding
space $\mathbb{R}^{d\times N_{0}}$ has the simple form
$u_{t}=(1-t)u^{i}+tu^{j}$. This correlates with the curve $\hat{\rho}_{t}$ in
$\mathcal{P}(\Omega)$ induced by the map
$\hat{T}:\hat{x}_{n}^{i}\mapsto\hat{x}_{n}^{j}$ 888This map can be understood
as the one that transports $\hat{\mu}^{i}$ onto $\hat{\mu}^{j}$ pivoting on
the reference: $\hat{\mu}^{i}\mapsto\mu^{0}\mapsto\hat{\mu}^{j}$. as

$\hat{\rho}_{t}:=(\hat{T}_{t})_{\\#}\hat{\mu}^{i}=\sum_{n=1}^{N_{0}}p_{n}^{0}\delta_{{x}_{n}^{0}+u_{t}(n)}.$
(21)

By abuse of notation, we call this curve the LOT geodesic between $\mu^{i}$
and $\mu^{j}$. Nevertheless, it is a geodesic between their barycentric
projections since it satisfies the following.

######  Proposition 2.2.

Let $\hat{\rho}_{t}$ be defined as (21), and
$\hat{\rho}_{0}=\hat{\mu}^{i},\hat{\rho}_{1}=\hat{\mu}^{j}$, then for all
$0\leq s\leq t\leq 1$

$\sqrt{LOT_{\mu^{0}}(\hat{\rho}_{s},\hat{\rho}_{t})}=(t-s)\sqrt{LOT_{\mu^{0}}(\hat{\rho}_{0},\hat{\rho}_{1})}.$
(22)

##  3 Linear Optimal Partial Transport Embedding

###  3.1 Static Formulation of Optimal Partial Transport

In addition to mass transportation, the OPT problem allows mass destruction at
the source and mass creation at the target. Let $\mathcal{M}_{+}(\Omega)$
denote the set of all positive finite Borel measures defined on $\Omega$. For
$\lambda\geq 0$ the OPT problem between
$\mu^{0},\mu^{j}\in\mathcal{M}_{+}(\Omega)$ can be formulated as

$\displaystyle
OPT_{\lambda}(\mu^{0},\mu^{j}):=\inf_{\gamma\in\Gamma_{\leq}(\mu^{0},\mu^{j})}C(\gamma;\mu^{0},\mu^{j},\lambda)$
(23) $\displaystyle\text{for}\quad
C(\gamma;\mu^{0},\mu^{j},\lambda):=\int_{\Omega^{2}}\|x^{0}-x^{j}\|^{2}d\gamma(x^{0},x^{j})$
$\displaystyle\qquad\,\,\,\qquad\qquad\qquad+\lambda(|\mu^{0}-\gamma_{0}|+|\mu^{j}-\gamma_{1}|)$
(24)

where $|\mu^{0}-\gamma_{0}|$ is the total mass of $\mu^{0}-\gamma_{0}$ (resp.
$|\mu^{j}-\gamma_{i}|$), and $\Gamma_{\leq}(\mu^{0},\mu^{j})$ denotes the set
of all measures in $\Omega^{2}$ with marginals $\gamma_{0}$ and $\gamma_{1}$
satisfying $\gamma_{0}\leq\mu^{0}$ (i.e., $\gamma_{0}(E)\leq\mu^{0}(E)$ for
all measurable set $E$), and $\gamma_{1}\leq\mu^{j}$. Here, the mass
destruction and creation penalty is linear, parametrized by $\lambda$. The set
of minimizers $\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$ of (23) is non-empty [20].
One can further restrict $\Gamma_{\leq}(\mu^{0},\mu^{j})$ to the set of
partial transport plans $\gamma$ such that $\|x^{0}-x^{j}\|^{2}<2\lambda$ for
all $(x^{0},x^{j})\in\operatorname{supp}(\gamma)$ [4, Lemma 3.2]. This means
that if the usual transportation cost is greater than $2\lambda$, it is better
to create/destroy mass.

###  3.2 Dynamic Formulation of Optimal Partial Transport

Adding a forcing term $\zeta$ to the continuity equation (6), one can take
into account curves that allow creation and destruction of mass. That is,
those who break the conservation of mass law. Thus, it is natural that the
minimization problem (23) can be rewritten [12, Th. 5.2] into a dynamic
formulation as

$OPT_{\lambda}(\mu^{0},\mu^{j})=\inf_{(\rho,v,\zeta)\in\mathcal{FCE}(\mu^{0},\mu^{j})}\int_{[0,1]\times\Omega}\|v\|^{2}d\rho+\lambda|\zeta|$
(25)

where $\mathcal{FCE}(\mu^{0},\mu^{j})$ is the set of tuples $(\rho,v,\zeta)$,
where $\rho,\zeta\in\mathcal{M}_{+}([0,1]\times\Omega)$,
$v:[0,1]\times\Omega\to\mathbb{R}^{d}$, satisfying

$\partial_{t}\rho+\nabla\cdot\rho
v=\zeta,\qquad\rho_{0}=\mu^{0},\quad\rho_{1}=\mu^{j}.$ (26)

As in the case of OT, under certain conditions on the minimizers $\gamma$ of
(23), one curve $\rho_{t}$ that minimizes the dynamic formulation (25) is
quite intuitive. We show in the next proposition that it consists of three
parts $\gamma_{t}$, $(1-t)\nu_{0}$ and $t\nu^{j}$ (see (27), (28), and (29)
below). The first is a curve that only transports mass, and the second and
third destroy and create mass at constant rates $|\nu_{0}|$, $|\nu^{j}|$,
respectively.

######  Proposition 3.1.

Let $\gamma^{*}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$ be of the form
$\gamma^{*}=(\mathrm{id}\times T)_{\\#}\gamma_{0}^{*}\,$ for
$T:\Omega\to\Omega$ a (measurable) map. Let

$\displaystyle\nu_{0}:=\mu^{0}-\gamma_{0}^{*},\quad\nu^{j}:=\mu^{j}-\gamma_{1}^{*},$
(27) $\displaystyle
T_{t}(x):=(1-t)x+tT(x),\quad\gamma_{t}:=(T_{t})_{\\#}\gamma_{0}^{*}.$ (28)

Then, an optimal solution $(\rho,v,\zeta)$ for (25) is given by

$\displaystyle\rho_{t}:=\gamma_{t}+(1-t)\nu_{0}+t\nu^{j},$ (29) $\displaystyle
v_{t}(x):=T(x_{0})-x_{0},\qquad\text{ if }x=T_{t}(x_{0}).$ (30)
$\displaystyle\zeta_{t}:=\nu^{j}-\nu_{0}$ (31)

Moreover, plugging in $(\rho,v,\zeta)$ into (25), it holds that

${OPT}_{\lambda}(\mu^{0},\mu^{j})=\|v_{0}\|^{2}_{\gamma_{0}^{*},2\lambda}+\lambda(|\nu_{0}|+|\nu^{j}|),$
(32)

where $v_{0}(x)=T(x)-x$ (i.e., $v_{t}$ at time $t=0$), and

$\|v\|_{\mu,2\lambda}^{2}:=\int_{\Omega}\min(\|v\|^{2},2\lambda)d\mu,\qquad\text{for
}v:\Omega\to\mathbb{R}^{d}.$

In analogy to the OT squared distance, we also call the optimal partial cost
(32) as the OPT squared distance.

###  3.3 Linear Optimal Partial Transport Embedding

######  Definition 3.2.

Let $\mu^{0}$, $\mu^{j}\in\mathcal{M}_{+}(\Omega)$ such that
$OPT_{\lambda}(\mu^{0},\mu^{j})$ is solved by a plan induced by a map. The
LOPT embedding of $\mu^{j}$ with respect to $\mu^{0}$ is defined as

$\mu^{j}\mapsto(u^{j},\bar{\mu}^{j},\nu^{j}):=(v_{0},\gamma_{0},\nu^{j})$ (33)

where $v_{0},\gamma_{0},\nu^{j}$ are defined as in Proposition 3.1.

Let us compare the LOPT (33) and LOT (12) embeddings. The first component
$v_{0}$ represents the tangent of the curve that transports mass from the
reference to the target. This is exactly the same as the LOT embedding. In
contrast to LOT, the second component $\gamma_{0}$ is necessary since we need
to specify what part of the reference is being transported. The third
component $\nu^{j}$ can be thought of as the tangent vector of the part that
creates mass. There is no need to save the destroyed mass because it can be
inferred from the other quantities.

Now, let $\mu^{0}\wedge\mu^{j}$ be the minimum measure999Formally,
${\mu}^{0}\wedge{\mu}^{j}(B):=\inf\left\\{{\mu}^{0}\left(B_{1}\right)+{\mu}^{j}\left(B_{2}\right)\right\\}$
for every Borel set $B$, where the infimum is taken over all partitions of
$B$., i.e. $B=B_{1}\cup B_{2}$, $B_{1}\cap B_{2}=\emptyset$, given by Borel
sets $B_{1}$, $B_{2}$. between $\mu^{0}$ and $\mu^{j}$. By the above
definition, $\mu^{0}\mapsto(u^{0},\bar{\mu}^{0},\nu^{0})=(0,\mu^{0},0)$.
Therefore, (32) can be rewritten

$\displaystyle OPT_{\lambda}(\mu^{0},\mu^{j})$
$\displaystyle=\|u^{0}-u^{j}\|^{2}_{\bar{\mu}^{0}\wedge\bar{\mu}^{j},2\lambda}$
$\displaystyle\quad+\lambda(|\bar{\mu}^{0}-\bar{\mu}^{j}|+|\nu_{0}-\nu^{j}|)$
(34)

This motivates the definition of the LOPT discrepancy.101010$LOPT_{\lambda}$
is not a rigorous metric.

######  Definition 3.3.

Consider a reference $\mu^{0}\in\mathcal{M}_{+}(\Omega)$ and target measures
$\mu^{i},\mu^{j}\in\mathcal{M}_{+}(\Omega)$ such that
$OPT_{\lambda}(\mu^{0},\mu^{i})$ and $OPT_{\lambda}(\mu^{0},\mu^{j})$ can be
solved by plans induced by mappings as in the hypothesis of Proposition 3.1.
Let $(u^{i},\bar{\mu}^{i},\nu^{i})$ and $(u^{j},\bar{\mu}^{j},\nu^{j})$ be the
LOPT embeddings of $\mu^{i}$ and $\mu^{j}$ with respect to $\mu^{0}$. The LOPT
discrepancy between $\mu^{i}$ and $\mu^{j}$ with respect to $\mu^{0}$ is
defined as

$\displaystyle LOPT_{\mu^{0},\lambda}(\mu^{i},\mu^{j})$
$\displaystyle:=\|u^{i}-u^{j}\|^{2}_{\bar{\mu}^{i}\wedge\bar{\mu}^{j},2\lambda}$
$\displaystyle\quad+\lambda(|\bar{\mu}^{i}-\bar{\mu}^{j}|+|\nu^{i}-\nu^{j}|)$
(35)

Similar to the LOT framework, by equation (34), LOPT can recover OPT when
$\mu^{i}=\mu^{0}$. That is,

$LOPT_{\mu^{0},\lambda}(\mu^{0},\mu^{j})=OPT_{\lambda}(\mu^{0},\mu^{j}).$

###  3.4 LOPT in the Discrete Setting

If $\mu^{0},\mu^{j}$ are $N_{0},N_{j}-$size discrete non-negative measures as
in (15) (but not necessarily with total mass 1), the OPT problem (23) can be
written as

$\min_{\gamma\in\Gamma_{\leq}(\mu^{0},\mu^{j})}\sum_{n,m}\|x_{n}^{0}-x_{m}^{j}\|^{2}\gamma_{n,m}+\lambda(|p^{0}|+|p^{j}|-2|\gamma|)$

where the set $\Gamma_{\leq}(\mu^{0},\mu^{j})$ can be viewed as the subset of
$N_{0}\times N_{j}$ matrices with non-negative entries

$\Gamma_{\leq}(\mu^{0},\mu^{j}):=\\{\gamma\in\mathbb{R}_{+}^{N_{0}\times{N_{j}}}:\gamma
1_{N_{j}}\leq p^{0},\gamma^{T}1_{N_{0}}\leq p^{j}\\},$

where $1_{N_{0}}$ denotes the $N_{0}\times 1$ vector whose entries are $1$
(resp. $1_{N_{j}}$), $p^{0}=[p_{1}^{0},\ldots,p_{N_{0}}^{0}]$ is the vector of
weights of $\mu^{0}$ (resp. $p^{j}$), $\gamma 1_{N_{j}}\leq p^{0}$ means that
component-wise holds the ‘$\leq$’ (resp. $\gamma^{T}1_{N_{0}}\leq p^{j}$,
where $\gamma^{T}$ is the transpose of $\gamma$), and
$|p^{0}|=\sum_{n=1}^{N_{0}}|p^{0}_{n}|$ is the total mass of $\mu^{0}$ (resp.
$|p^{j}|,|\gamma|$). The marginals are $\gamma_{0}:=\gamma 1_{N_{j}}$, and
$\gamma_{1}:=\gamma^{T}1_{N_{0}}$.

Similar to OT, when an optimal plan $\gamma^{j}$ for
$OPT_{\lambda}(\mu^{0},\hat{\mu}^{j})$ is not induced by a map, we can replace
the target measure $\mu^{j}$ by an OPT barycentric projection $\hat{\mu}^{j}$
for which a map exists. Therefore, allowing us to apply the LOPT embedding
(see (33) and (40) below).

######  Definition 3.4.

Let $\mu^{0}$ and $\mu^{j}$ be positive discrete measures, and
$\gamma^{j}\in\Gamma^{*}_{\leq}(\mu^{0},\mu^{j})$. The OPT barycentric
projection111111Notice that in (16) we had
$p_{n}^{0}=\sum_{m=1}^{N_{j}}\gamma^{j}_{n,m}$. This leads to introducing
$\hat{p}_{n}^{j}$ as in (37). That is, $\hat{p}_{n}^{j}$ plays the role of
$p_{n}^{0}$ in the OPT framework. However, here $\hat{p}_{n}^{j}$ depends on
$\gamma^{j}$ (on its first marginal $\gamma_{0}^{j}$) and not only on
$\mu^{0}$, and so we add a superscript ‘$j$’. of $\mu^{j}$ with respect to
$\mu^{0}$ is defined as

$\displaystyle\hat{\mu}^{j}:=\sum_{n=1}^{N_{0}}\hat{p}_{n}^{j}\delta_{\hat{x}^{j}_{n}},\qquad\text{
where}$ (36)
$\displaystyle\hat{p}_{n}^{j}:=\sum_{m=1}^{N_{j}}\gamma^{j}_{n,m},\qquad 1\leq
n\leq N_{0},$ (37)
$\displaystyle\hat{x}_{n}^{j}:=\begin{cases}\frac{1}{\hat{p}_{n}^{j}}\sum_{m=1}^{N_{j}}\gamma^{j}_{n,m}x_{m}^{j}&\text{if
}\,{\hat{p}_{n}^{j}}>0\\\ x_{n}^{0}&\text{if
}\,{\hat{p}_{n}^{j}}=0.\end{cases}$ (38)

######  Theorem 3.5.

In the same setting of Definition 3.4, the map
$x_{n}^{0}\mapsto\hat{x}_{n}^{j}$ given by (38) solves the problem
$OPT_{\lambda}(\mu^{0},\hat{\mu}^{j}),$ in the sense that induces the partial
optimal plan
$\hat{\gamma}^{j}=\operatorname{diag}(\hat{p}_{1}^{j},\ldots,\hat{p}_{N_{0}}^{j})$.

It is worth noting that when we take a barycentric projection of a measure,
some information is lost. Specifically, the information about the part of
$\mu^{j}$ that is not transported from the reference $\mu^{0}$. This has some
minor consequences.

First, unlike (18), the optimal partial transport cost
$OPT_{\lambda}(\mu^{0},\mu^{j})$ changes when we replace $\mu^{j}$ by
$\hat{\mu}^{j}$. Nevertheless, the following relation holds.

######  Theorem 3.6.

In the same setting of Definition 3.4, if $\gamma^{j}$ is induced by a map,
then

$\displaystyle
OPT_{\lambda}(\mu^{0},\mu^{j})=OPT_{\lambda}(\mu^{0},\hat{\mu}^{j})+\lambda(|\mu^{j}|-|\hat{\mu}^{j}|)$
(39)

The second consequence121212This is indeed an advantage since it allows the
range of the embedding to always have the same dimension $N_{0}\times(d+1)$.
is that the LOPT embedding of $\hat{\mu}^{j}$ will always have a null third
component. That is,

$\hat{\mu}^{j}\mapsto([\hat{x}_{1}^{j}-x_{1}^{0},\ldots,\hat{x}_{N_{0}}^{j}-x_{N_{0}}^{0}],\,\sum_{n=1}^{N_{0}}\hat{p}_{n}^{j}\delta_{x_{n}^{0}},\,0).$
(40)

Therefore, we represent this embedding as
$\hat{\mu}^{j}\mapsto(u^{j},\hat{p}^{j})$, for
$u^{j}=[\hat{x}_{1}^{j}-x_{1}^{0},\ldots,\hat{x}_{N_{0}}^{j}-x_{N_{0}}^{0}]$
and $\hat{p}^{j}=[\hat{p}^{j}_{1},\ldots,\hat{p}^{j}_{N_{0}}]$. The last
consequence is given in the next result.

######  Proposition 3.7.

If $\mu^{0},\mu^{i},\mu^{j}$ are discrete and satisfy the conditions of
Definition 3.3, then

$LOPT_{\mu^{0},\lambda}(\mu^{i},\mu^{j})=LOPT_{\mu^{0},\lambda}(\hat{\mu}^{i},\hat{\mu}^{j})+\lambda
C_{i,j}$ (41)

where $C_{i,j}=|\mu^{i}|-|\hat{\mu}^{i}|+|\mu^{j}|-|\hat{\mu}^{j}|$.

As a byproduct we can define the LOPT discrepancy for any pair of discrete
measures $\mu^{i},\mu^{j}$ as the right-hand side of (41). In practice, unless
to approximate $OPT_{\lambda}(\mu^{i},\mu^{j})$, we set $C_{i,j}=0$ in (41).
That is,

$LOPT_{\mu^{0},\lambda}(\mu^{i},\mu^{j}):=LOPT_{\mu^{0},\lambda}(\hat{\mu}^{i},\hat{\mu}^{j}).$
(42)

Figure 2: The average relative error between $OPT_{\lambda}$ and
$LOPT_{\lambda,\mu_{0}}$ between all pairs of discrete measures $\mu^{i}$ and
$\mu^{j}$.

###  3.5 OPT and LOPT Interpolation

Inspired by OT and LOT geodesics as defined in section 2.5, but lacking the
Riemannian structure provided by the OT squared norm, we propose an OPT
interpolation curve and its LOPT approximation.

For the OPT interpolation between two measures $\mu^{i}$, $\mu^{j}$ for which
exists $\gamma\in\Gamma_{\leq}^{*}(\mu^{i},\mu^{j})$ of the form
$\gamma=(\mathrm{id}\times T)_{\\#}\gamma_{0}\,$, a natural candidate is the
solution $\rho_{t}$ of the dynamic formulation of
$OPT_{\lambda}(\mu^{i},\mu^{j})$. The exact expression is given by Proposition
3.1. When working with general discrete measures $\mu^{i}$, $\mu^{j}$ (as in
(15), with ‘$i$’ in place of $0$) such $\gamma$ is not guaranteed to exist.
Then, we replace the latter with its OPT barycentric projection with respect
to $\mu^{i}$. And by Theorem 3.5 the map $T:x_{n}^{i}\mapsto\hat{x}_{n}^{j}$
solves $OPT_{\lambda}(\mu^{i},\hat{\mu}^{j})$ and the OPT interpolating curve
is131313$\hat{p}_{n}^{j}$ are the coefficients of $\hat{\mu}^{j}$ with respect
to $\mu^{i}$ analogous to (36).

$t\mapsto\sum_{n=1}^{N_{i}}\hat{p}_{n}^{j}\delta_{(1-t)x_{n}^{i}+tT(x_{n}^{i})}+(1-t)\sum_{n=1}^{N_{i}}(p_{n}^{i}-\hat{p}_{n}^{j})\delta_{x_{n}^{i}}.$

When working with a multitude of measures, it is convenient to consider a
reference $\mu^{0}$ and embed the measures in $\mathbb{R}^{(d+1)\times N_{0}}$
using LOPT. Hence, doing computations in a simpler space. Below we provide the
LOPT interpolation.

######  Definition 3.8.

Given discrete measures $\mu^{0},\mu^{i},\mu^{j}$, with $\mu^{0}$ as the
reference, let $(u^{i},\hat{p}^{i}),(u^{j},\hat{p}^{i})$ be the LOPT
embeddings of $\mu^{i},\mu^{j}$. Let
$\hat{p}^{ij}:=\hat{p}^{i}\wedge\hat{p}^{j}$, and $u_{t}:=(1-t)u^{i}+tu^{j}$.
We define the LOPT interpolating curve between $\mu^{i}$ and $\mu^{j}$ by

$\displaystyle t\mapsto$ $\displaystyle\sum_{k\in
D_{T}}\hat{p}^{ij}_{k}\delta_{x_{k}^{0}+u_{t}(k)}+(1-t)\sum_{k\in
D_{D}}(\hat{p}_{k}^{i}-\hat{p}^{ij}_{k})\delta_{x_{k}^{0}+u_{k}^{i}}$
$\displaystyle\qquad\quad\qquad\qquad\qquad+t\sum_{k\in
D_{C}}(\hat{p}_{k}^{j}-\hat{p}_{k}^{ij})\delta_{x^{0}_{k}+u_{k}^{j}}$

where $D_{T}=\\{k:\hat{p}_{k}^{ij}>0\\}$,
$D_{D}=\\{k:\hat{p}_{k}^{i}>\hat{p}_{k}^{ij})\\}$ and
$D_{C}=\\{k:\hat{p}_{k}^{ij}<\hat{p}_{k}^{j})\\}$ are respectively the sets
where we transport, destroy and create mass.

##  4 Applications

Figure 3: Wall-clock time between OPT and LOPT. The LP solver in PythonOT [23]
is applied to each individual OPT problem, with $100N$ maximum number of
iterations. Figure 4: We demonstrate the OT geodesic, OPT interpolation, LOT
geodesic, and LOPT interpolation in MNIST. In LOT geodesic and LOPT
interpolation, we use the same reference measure. The percentage of noise
$\eta$ is set to $0.5$. In OPT interpolation, we set $\lambda=20$, and in LOPT
interpolation we set, $\lambda=30$.

Approximation of OPT Distance: Similar to LOT [41], and Linear Hellinger
Kantorovich (LHK) [10], we test the approximation performance of OPT using
LOPT. Given $K$ empirical measures $\\{\mu^{i}\\}_{i=1}^{K}$, for each pair
$(\mu^{i},\mu^{j})$, we compute $OPT_{\lambda}(\mu^{i},\mu^{j})$ and
$LOPT_{\mu^{0},\lambda}(\mu^{i},\mu^{j})$ and report the relative error as

$\frac{1}{\binom{K}{2}}\sum_{i,j\in[1:K],i\neq
j}\frac{|OPT_{\lambda}(\mu^{i},\mu^{j})-LOPT_{\mu^{0},\lambda}(\mu^{i},\mu^{j})|}{OPT_{\lambda}(\mu^{i},\mu^{j})}.$

Similar to LOT and LHK, the choice of $\mu^{0}$ is critical for the accurate
approximation of OPT. If $\mu^{0}$ is far away from $\\{\mu^{i}\\}_{i=1}^{K}$,
the linearization is a poor approximation because the mass in $\mu^{i}$ and
$\mu^{0}$ would only be destroyed or created. In practice, one candidate for
$\mu^{0}$ is the barycenter of the set of measures $\\{\mu^{i}\\}$. The OPT
can be converted into OT problem [8], and one can use OT barycenter [18] to
find $\mu^{0}$.

For our experiments, we created $K$ point sets of size $N$ for $K$ different
Gaussian distributions in $\mathbb{R}^{2}$. In particular,
$\mu^{i}\sim\mathcal{N}(m^{i},I)$, with $\|m^{i}\|=\sqrt{3}$ for $i=1,..,K$.
For the reference, we picked an $N$ point representation of
$\mu^{0}\sim\mathcal{N}(\overline{m},I)$ with $\overline{m}=\sum m^{i}/K$. We
test for $N=50,100,...,1000$ and $K=2,4$. For each $(N,K)$, we repeated each
experiment $10$ times. The relative errors are shown in Figure 2. For large
$\lambda$, most mass is transported and $OT(\mu^{i},\mu^{j})\approx
OPT_{\lambda}(\mu^{i},\mu^{j})$, the performance of LOPT is close to that of
LOT, and the relative error is small. For small $\lambda$, almost no mass is
transported,
$OPT_{\lambda}(\mu^{i},\mu^{j})\approx\lambda(|\mu^{i}|+|\mu^{j}|)\approx\lambda(|\mu^{i}|-|\hat{\mu}^{i}|+|\mu^{j}|-|\hat{\mu}^{j}|)\approx{LOPT}_{\mu^{0},\lambda}(\mu^{i},\mu^{j})$,
and we still have a small error. In between, e.g., $\lambda=5.0$, we have the
largest relative error. Similar results were obtained by setting the reference
as the OT barycenter.

In Figure 3 we report wall clock times of OPT vs LOPT for $\lambda=5$. We use
linear programming [27] to solve each OPT problem with a cost of
$\mathcal{O}(N^{3}\text{log}(N))$ each. Thus, computing the OPT distance pair-
wisely for $\\{\mu^{i}\\}_{i=1}^{K}$ requires
$\mathcal{O}(K^{2}N^{3}\text{log}(N))$. In contrast, to compute $LOPT$, we
only need to solve $K$ optimal partial transport problems for the embeddings
(see (33) or (40)). Computing LOPT discrepancies after the embeddings is
linear. Thus, the total computational cost is
$\mathcal{O}(KN^{3}\text{log}(N)+K^{2}N)$. The experiment was conducted on a
Linux computer with AMD EPYC 7702P CPU with 64 cores and 256GB DDR4 RAM.

Point Cloud Interpolation:  We test OT geodesic, LOT geodesic, OPT
interpolation, and LOPT interpolation on the point cloud MNIST dataset. We
compute different transport curves between point sets of the digits $0$ and
$9$. Each digit is a weighted point set
$\\{x_{n}^{j},p_{n}^{j}\\}_{n=1}^{N_{j}}$, $j=1,2$, that we consider as a
discrete measure of the form
$\mu^{j}=\sum_{n=1}^{N_{j}}p_{n}^{j}\delta_{x^{j}_{n}}+1/N_{j}\sum_{m=1}^{\eta
N_{j}}\delta_{y_{m}^{j}}$, where the first sum corresponds to the clean data
normalized to have total mass 1, and the second sum is constructed with
samples from a uniform distribution acting as noise with total mass $\eta$.
For OPT and LOPT, we use the distributions $\mu^{j}$ without re-normalization,
while for OT and LOT, we re-normalize them. The reference in LOT and LOPT is
taken as the OT barycenter of a sample of the digits 0, 1, and 9 not including
the ones used for interpolation, and normalized to have unit total mass. We
test for $\eta=0,0.5,0.75$, and the results for $\eta=0.5$ are shown in Figure
4. We can see that OT and LOT do not eliminate noise points. OPT still retains
much of the noise because interpolation is essentially between $\mu^{1}$ and
$\hat{\mu}^{2}$ (with respect to $\mu^{1}$). So $\mu^{1}$ acts as a reference
that still has a lot of noise. In LOPT, by selecting the same reference as LOT
we see that the noise significantly decreases.

Figure 5: We plot the first two principal components of each $u^{j}$ based on
LOT and LOPT. For $LOPT$, we set $\lambda=20.0$.

PCA analysis: We compare the results of performing PCA on the embedding space
of $LOT$ and $LOPT$ for point cloud MNIST. We take 900 digits from the dataset
corresponding to digits $0,1$ and $3$ in equal proportions. Each element is a
point set $\\{x^{j}_{n}\\}_{n=1}^{N_{j}}$ that we consider as a discrete
measure with added noise,
$\mu^{j}=\sum_{n=1}^{N_{j}}\delta_{x_{n}^{j}}/N_{j}+\sum_{m=1}^{\eta
N_{j}}\delta_{y_{m}^{j}}/N_{j}$ as before. The reference, $\mu^{0}$, is set to
the OT barycenter of 30 samples from the clean data. For LOT we re-normalize
each $\mu^{j}$ to have a total mass of 1, while we do not re-normalize for
LOPT. Let $S_{\eta}:=\\{\mu^{j}:\text{noise level}=\eta\\}_{j=1}^{900}$. We
embed $S_{\eta}$ using LOT and LOPT and apply PCA on the embedded vectors
$\\{u^{j}\\}$. In Figure 5 we show the first two principal components of the
set of embedded vectors based on LOT and LOPT for noise levels $\eta=0,0.75$.
It can be seen that when there is no noise, the PCA dimension reduction
technique works well for both LOT and LOPT. When $\eta=0.75$, the method fails
for LOT embedding, but the dimension-reduced data is still separable for LOPT.

##  5 Summary

We proposed a Linear Optimal Partial Transport (LOPT) technique that allows us
to embed distributions with different masses into a fixed dimensional space in
which several calculations are significantly simplified. We show how to
implement this for real data distributions allowing us to reduce the
computational cost in applications that would benefit from the use of optimal
(partial) transport. We finally provide comparisons with previous techniques
and show some concrete applications. In particular, we show that LOPT is more
robust in the presence of noise than other methods. We leave the comparison
between LOPT and LHK for future work.

##  6 Acknowledgment

This work was partially supported by the Defense Advanced Research Projects
Agency (DARPA) under Contracts No. HR00112190132 and No. HR00112190135. Any
opinions, findings, conclusions, or recommendations expressed in this material
are those of the authors and do not necessarily reflect the views of the
United States Air Force, DARPA, or other funding agencies.

## References

  * [1] Akram Aldroubi, Shiying Li, and Gustavo K Rohde.  Partitioning signal classes using transport transforms for data analysis and machine learning.  Sampling Theory, Signal Processing, and Data Analysis, 19(1):1–25, 2021.
  * [2] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré.  Gradient flows: in metric spaces and in the space of probability measures.  Springer Science & Business Media, 2005.
  * [3] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International conference on machine learning, pages 214–223. PMLR, 2017.
  * [4] Yikun Bai, Bernard Schmitzer, Mathew Thorpe, and Soheil Kolouri.  Sliced optimal partial transport.  arXiv preprint arXiv:2212.08049, 2022.
  * [5] Saurav Basu, Soheil Kolouri, and Gustavo K Rohde.  Detecting and visualizing cell phenotype differences from microscopy images using transport-based morphometry.  Proceedings of the National Academy of Sciences, 111(9):3448–3453, 2014.
  * [6] Jean-David Benamou and Yann Brenier.  A computational fluid mechanics solution to the monge-kantorovich mass transfer problem.  Numerische Mathematik, 84(3):375–393, 2000.
  * [7] Yann Brenier.  Polar factorization and monotone rearrangement of vector-valued functions.  Communications on pure and applied mathematics, 44(4):375–417, 1991\.
  * [8] Luis A Caffarelli and Robert J McCann.  Free boundaries in optimal transport and monge-ampere obstacle problems.  Annals of mathematics, pages 673–730, 2010.
  * [9] Tianji Cai, Junyi Cheng, Nathaniel Craig, and Katy Craig.  Linearized optimal transport for collider events.  Physical Review D, 102(11):116019, 2020.
  * [10] Tianji Cai, Junyi Cheng, Bernhard Schmitzer, and Matthew Thorpe.  The linearized hellinger–kantorovich distance.  SIAM Journal on Imaging Sciences, 15(1):45–83, 2022.
  * [11] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  An interpolating distance between optimal transport and fisher–rao metrics.  Foundations of Computational Mathematics, 18(1):1–44, 2018.
  * [12] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Unbalanced optimal transport: Dynamic and kantorovich formulations.  Journal of Functional Analysis, 274(11):3090–3123, 2018.
  * [13] Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré.  Faster wasserstein distance estimation with the sinkhorn divergence.  Advances in Neural Information Processing Systems, 33:2257–2269, 2020.
  * [14] Lenaic Chizat, Bernhard Schmitzer, Gabriel Peyre, and Francois-Xavier Vialard.  An interpolating distance between optimal transport and fisher-rao.  arXiv:1506.06430 [math], 2015.
  * [15] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy.  Joint distribution optimal transportation for domain adaptation.  Advances in Neural Information Processing Systems, 30, 2017.
  * [16] Nicolas Courty, Rémi Flamary, and Devis Tuia.  Domain adaptation with regularized optimal transport.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 274–289. Springer, 2014.
  * [17] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [18] Marco Cuturi and Arnaud Doucet.  Fast computation of wasserstein barycenters.  In International conference on machine learning, pages 685–693. PMLR, 2014.
  * [19] Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty.  Unbalanced minibatch optimal transport; applications to domain adaptation.  In International Conference on Machine Learning, pages 3186–3197. PMLR, 2021.
  * [20] Alessio Figalli.  The optimal partial transport problem.  Archive for rational mechanics and analysis, 195(2):533–560, 2010\.
  * [21] Alessio Figalli and Nicola Gigli.  A new transportation distance between non-negative measures, with applications to gradients flows with dirichlet boundary conditions.  Journal de mathématiques pures et appliquées, 94(2):107–130, 2010.
  * [22] Alessio Figalli and Federico Glaudo.  An Invitation to Optimal Transport, Wasserstein Distances, and Gradient Flows.  2021\.
  * [23] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  Pot: Python optimal transport.  Journal of Machine Learning Research, 22(78):1–8, 2021.
  * [24] Aude Genevay, Gabriel Peyré, and Marco Cuturi.  Gan and vae from an optimal transport point of view.  arXiv preprint arXiv:1706.01807, 2017.
  * [25] Kevin Guittet.  Extended Kantorovich norms: a tool for optimization.  PhD thesis, INRIA, 2002.
  * [26] Hicham Janati, Marco Cuturi, and Alexandre Gramfort.  Wasserstein regularization for sparse multi-task regression.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1407–1416. PMLR, 2019.
  * [27] Narendra Karmarkar.  A new polynomial-time algorithm for linear programming.  In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984.
  * [28] Sanggyun Kim, Rui Ma, Diego Mesa, and Todd P Coleman.  Efficient bayesian inference methods via convex optimization and optimal transport.  In 2013 IEEE International Symposium on Information Theory, pages 2259–2263. IEEE, 2013.
  * [29] Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann.  Wasserstein embedding for graph learning.  In International Conference on Learning Representations, 2020.
  * [30] Shinjini Kundu, Soheil Kolouri, Kirk I Erickson, Arthur F Kramer, Edward McAuley, and Gustavo K Rohde.  Discovery and visualization of structural biomarkers from mri using transport-based morphometry.  NeuroImage, 167:256–275, 2018.
  * [31] Jan Lellmann, Dirk A Lorenz, Carola Schonlieb, and Tuomo Valkonen.  Imaging with kantorovich–rubinstein discrepancy.  SIAM Journal on Imaging Sciences, 7(4):2833–2859, 2014.
  * [32] Matthias Liero, Alexander Mielke, and Giuseppe Savare.  Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures.  Inventiones mathematicae, 211(3):969–1117, 2018.
  * [33] Huidong Liu, Xianfeng Gu, and Dimitris Samaras.  Wasserstein gan with quadratic transport cost.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 4832–4841, 2019.
  * [34] Caroline Moosmüller and Alexander Cloninger.  Linear optimal transport embedding: Provable wasserstein classification for certain rigid transformations and perturbations.  arXiv preprint arXiv:2008.09165, 2020.
  * [35] Navid Naderializadeh, Joseph F Comer, Reed Andrews, Heiko Hoffmann, and Soheil Kolouri.  Pooling by sliced-wasserstein embedding.  Advances in Neural Information Processing Systems, 34:3389–3400, 2021.
  * [36] Khai Nguyen, Dang Nguyen, and Nhat Ho.  Self-attention amortized distributional projection optimization for sliced wasserstein point-cloud reconstruction.  arXiv preprint arXiv:2301.04791, 2023.
  * [37] Khai Nguyen, Dang Nguyen, Tung Pham, Nhat Ho, et al.  Improving mini-batch optimal transport via partial transportation.  In International Conference on Machine Learning, pages 16656–16690. PMLR, 2022.
  * [38] F. Santambrogio.  Optimal Transport for Applied Mathematicians. Calculus of Variations, PDEs and Modeling.  Birkhäuser, 2015.
  * [39] Meyer Scetbon and marco cuturi.  Low-rank optimal transport: Approximation, statistics and debiasing.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [40] Cedric Villani.  Topics in Optimal Transportation, volume 58.  American Mathematical Society, 2003.
  * [41] 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.  International journal of computer vision, 101(2):254–269, 2013\.
  * [42] Jianbo Ye, Panruo Wu, James Z Wang, and Jia Li.  Fast discrete distribution clustering using wasserstein barycenter with sparse support.  IEEE Transactions on Signal Processing, 65(9):2317–2332, 2017.

Appendix

We refer to the main text for references.

##  Appendix A Notation

  * •

$(\mathbb{R}^{d},\|\cdot\|)$, $d$-dimensional Euclidean space endowed with the
standard Euclidean norm $\|x\|=\sqrt{\sum_{k=1}^{d}|x(k)^{2}|}$.
$d(\cdot,\cdot)$ is the associated distance, i.e., $d(x,y)=\|x-y\|$.

  * •

$x\cdot y$ canonical inner product in $\mathbb{R}^{d}$.

  * •

$1_{N}$, column vector of size $N\times 1$ with all entries equal to 1.

  * •

$\operatorname{diag}(p_{1},\ldots,p_{N})$, diagonal matrix.

  * •

$w^{T}$, transpose of a matrix $w$.

  * •

$\mathbb{R}_{+}$, non-negative real numbers.

  * •

$\Omega$, convex and compact subset of $\mathbb{R}^{d}$.
$\Omega^{2}=\Omega\times\Omega$.

  * •

$\mathcal{P}(\Omega)$, set of probability Borel measures defined in $\Omega$.

  * •

$\mathcal{M}_{+}(\Omega)$, set of positive finite Borel measures defined in
$\Omega$.

  * •

$\pi_{0}:\Omega^{2}\to\Omega$, $\pi_{0}(x^{0},x^{1}):=x^{0}$;
$\pi_{1}:\Omega^{2}\to\Omega$, $\pi_{1}(x^{0},x^{1}):=x^{1}$, standard
projections.

  * •

$F_{\\#}\mu$, push-forward of the measure $\mu$ by the function.
$F_{\\#}\mu(B)=\mu(F^{-1}(B))$ for all measurable set $B$, where
$F^{-1}(B)=\\{x:\,F(x)\in B\\}$.

  * •

$\delta_{x}$, Dirac measure concentrated on $x$.

  * •

$\mu=\sum_{n=1}^{N}p_{n}\delta_{x_{n}}$, discrete measure ($x_{n}\in\Omega$,
$p_{n}\in\mathbb{R}_{+}$). The coefficients $p_{n}$ are called the weights of
$\mu$.

  * •

$\operatorname{supp}(\mu)$, support of the measure $\mu$.

  * •

$\mu^{i}\wedge\mu^{j}$ minimum measure between $\mu^{i}$ and $\mu^{j}$;
$p^{i}\wedge p^{j}$ vector having at each $n$ entry the minimum value
$p^{i}_{n}$ and $p^{j}_{n}$.

  * •

$\mu^{0}$ reference measure. $\mu^{i},\mu^{j}$ target measures. In the OT
framework, they are in $\mathcal{P}(\Omega)$. In the OPT framework, they are
in $\mathcal{M}_{+}(\Omega)$.

  * •

$\Gamma(\mu^{0},\mu^{j})=\\{\gamma\in\mathcal{P}(\Omega^{2}):\,\pi_{0\\#}\gamma=\mu^{0},\,\pi_{1\\#}\gamma=\mu^{j}\\}$,
set of Kantorovich transport plans.

  * •

$C(\gamma;\mu^{0},\mu^{j})=\int_{\Omega^{2}}\|x^{0}-x^{j}\|^{2}d\gamma(x^{0},x^{j})$,
Kantorovich cost given by the transportation plan $\gamma$ between $\mu^{0}$
and $\mu^{j}$.

  * •

$\Gamma^{*}(\mu^{0},\mu^{j})$, set of optimal Kantorovich transport plans.

  * •

$T$, optimal transport Monge map.

  * •

$\mathrm{id}$, identity map $\mathrm{id}(x)=x$.

  * •

$T_{t}(x)=(1-t)x+tT(x)$ for $T:\Omega\to\Omega$. Viewed as a function of
$(t,x)$, it is a flow.

  * •

In section 2: $\rho\in\mathcal{P}([0,1]\times\Omega)$ curve of measures. At
each $0\leq t\leq$, $\rho_{t}\in\mathcal{P}(\Omega)$. In section 3: analogous,
replacing $\mathcal{P}$ by $\mathcal{M}_{+}$.

  * •

$v:[0,1]\times\Omega\to\mathbb{R}^{d}$. at each time
$v_{t}:\Omega\to\mathbb{R}^{d}$ is a vector field. $v_{0}$, initial velocity.

  * •

$\nabla\cdot V$, divergence of the vector field $V$ with respect to the
spatial variable $x$.

  * •

$\partial_{t}\rho+\nabla\cdot\rho v=0$, continuity equation.

  * •

$\mathcal{CE}(\mu^{0},\mu^{j})$, set of solutions of the continuity equation
with boundary conditions $\mu^{0}$ and $\mu^{j}$.

  * •

$\partial_{t}\rho+\nabla\cdot\rho v=\zeta$, continuity equation with forcing
term $\zeta$.

  * •

$\mathcal{FCE}(\mu^{0},\mu^{j})$, set solutions $(\rho,v,\zeta)$ of the
continuity equation with forcing term with boundary conditions $\mu^{0}$ and
$\mu^{j}$.

  * •

$OT(\mu^{0},\mu^{j})$, optimal transport minimization problem. See (1) for the
Kantorovich formulation, and (6) for the dynamic formulation.

  * •

$W_{2}(\mu^{0},\mu^{j})=\sqrt{OT(\mu^{0},\mu^{j})}$, $2$-Wasserstein distance.

  * •

$\mathcal{T}_{\mu}=L^{2}(\Omega;\mathbb{R}^{d},\mu)$, where
$\|u\|_{\mu}^{2}=\int_{\Omega}\|u(x)\|^{2}d\mu(x)$ (if $\mu$ is discrete,
$\mathcal{T}_{\mu}$ is identified with $\mathbb{R}^{d\times N}$ and
$\|u\|_{\mu}^{2}=\sum_{n=1}^{N}\|u(n)\|^{2}p_{n}$).

  * •

$LOT_{\mu^{0}}(\mu^{i},\mu^{j})$, see (14) for continuous densities, and (19)
for discrete measures.

  * •

$\lambda>0$, penalization in OPT.

  * •

$\mu\leq\nu$ if $\mu(B)\leq\nu(E)$ for all measurable set $E$ and we say that
$\mu$ is dominated by $\nu$.

  * •

$\Gamma_{\leq}(\mu^{0},\mu^{j})=\\{\gamma\in\mathcal{M}_{+}(\Omega^{2}):\,\pi_{0\\#}\gamma\leq\mu^{0},\,\pi_{1\\#}\gamma\leq\mu^{j}\\}$,
set of partial transport plans.

  * •

$\gamma_{0}:=\pi_{0\\#}\gamma$, $\gamma_{1}:=\pi_{1\\#}\gamma$, marginals of
$\gamma\in\mathcal{M}_{+}(\Omega^{2})$.

  * •

$\nu_{0}=\mu^{0}-\gamma_{0}$ (for the reference $\mu^{0}$),
$\nu^{j}=\mu^{j}-\gamma_{1}$ (for the target $\mu^{j}$).

  * •

$C(\gamma;\mu^{0},\mu^{j},\lambda)=\int\|x^{0}-x^{j}\|^{2}d\gamma(x^{0},x^{j})+\lambda(|\mu^{0}-\gamma_{0}|+|\mu^{j}-\gamma_{1}|)$,
partial transport cost given by the partial transportation plan $\gamma$
between $\mu^{0}$ and $\mu^{j}$ with penalization $\lambda$.

  * •

$\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$, set of optimal partial transport plans.

  * •

$OPT(\mu^{0},\mu^{j})$, partial optimal transport minimization problem between
$\mu^{0}$ and $\mu^{j}$. See (23) for the static formulation, and (25) for the
dynamic formulation.

  * •

$\|v\|_{\mu,2\lambda}^{2}:=\int_{\Omega}\min(\|v\|^{2},2\lambda)d\mu$

  * •

$LOPT_{\lambda}(\mu^{i},\mu^{j})$, see (35), and (42) and the discussion
above.

  * •

$\mu^{j}\mapsto u^{j}$, LOT embedding (fixing first a reference
$\mu^{0}\in\mathcal{P}(\Omega)$). If $\mu^{0}$ has continuous density,
$u^{j}:=v_{0}^{j}=T^{j}-\mathrm{id}$, and so it is a map from measures
$\mu^{j}\in\mathcal{P}(\Omega)$ to vector fields $u^{i}$ defined in $\Omega$,
see (12). For discrete measures ($\mu^{0}$, $\mu^{j}$ discrete), LOT embedding
is needed first, and in this case, the embedding is a map from discrete
probability to $\mathbb{R}^{d\times N_{0}}$, see (17).

  * •

$\mu$, OT and OPT barycentric projection of $\mu$ with respect to a reference
$\mu^{0}$ (in $\mathcal{P}$ or $\mathcal{M}_{+}$, resp.), see (16) and (36),
respectively. $\hat{x}_{n}$ denote the new locations where $\hat{\mu}$ is
concentrated. $p_{n}^{0}$ and $\hat{p}_{n}$ denote the wights of $\hat{\mu}$
for OT and OPT, respectively.

  * •

$u_{t}=(1-t)u^{i}+tu^{j}$, geodesic in LOT embedding space.

  * •

$\hat{\rho}_{t}$, LOT geodesic.

  * •

LOPT embeding, see (33), and (40).

  * •

OPT interpolating curve, and LOPT interpolating curve are defined in section
3.5.

##  Appendix B Proof of lemma 2.1

###### Proof.

We fix $\gamma^{*}\in\Gamma^{*}(\mu^{0},\mu^{j})$141414Although in subsection
2.4 we use the notation $\gamma^{j}\in\Gamma^{*}(\mu^{0},\mu^{j})$, here we
use the notation $\gamma^{*}$ to emphasize that we are fixing an optimal
plan., and then we compute the map $x_{n}^{0}\mapsto\hat{x}_{n}^{j}$ according
to (16). This map induces a transportation plan
$\hat{\gamma}^{*}:=\operatorname{diag}({p}_{1}^{0},\ldots,p_{N_{0}}^{0})\in\mathbb{R}_{+}^{N_{0}\times
N_{0}}$. We will prove that
$\hat{\gamma}^{*}\in\Gamma^{*}(\mu^{0},\hat{\mu}^{j})$. By definition, it is
easy to see that its marginals are $\mu^{0}$ and $\hat{\mu}^{j}$. The
complicated part is to prove optimality. Let
$\hat{\gamma}\in\Gamma(\mu^{0},\hat{\mu}^{j})$ be an arbitrary transportation
plan between $\mu^{0}$ and $\mu^{j}$ (i.e. $\gamma
1_{N_{0}}=\gamma^{T}1_{N_{0}}=p^{0}$). We need to show

$\displaystyle C(\hat{\gamma}^{*};\mu^{0},\hat{\mu}^{j})\leq
C(\hat{\gamma};\mu^{0},\hat{\mu}^{j}).$ (43)

Since $\hat{\gamma}^{*}$ is a diagonal matrix with positive diagonal, its
inverse matrix is
$(\gamma^{*})^{-1}=\operatorname{diag}(1/p_{1}^{0},\ldots,1/p_{N_{0}}^{0})$.
We define

$\gamma:=\hat{\gamma}(\gamma^{*})^{-1}\gamma^{*}\in\mathbb{R}_{+}^{N_{0}\times
N_{j}}.$

We claim $\gamma\in\Gamma(\mu^{0},\mu^{j})$. Indeed,

$\displaystyle\gamma 1_{N_{j}}$
$\displaystyle=\hat{\gamma}(\gamma^{*})^{-1}\gamma^{*}1_{N_{j}}=\hat{\gamma}(\gamma^{*})^{-1}p^{0}=\hat{\gamma}1_{N_{0}}=p^{0}$
(44) $\displaystyle\gamma^{T}1_{N_{0}}$
$\displaystyle=(\gamma^{*})^{T}(\gamma^{*})^{-1}\hat{\gamma}^{T}1_{N_{0}}=(\gamma^{*})^{T}(\gamma^{*})^{-1}p^{0}=(\gamma^{*})^{T}1_{N_{0}}=p^{j},$
(45)

where the second equality in (44) and the third equality in (45) follow from
the fact $\gamma^{*}\in\Gamma(\mu^{0},\mu^{1})$, and the fourth equality in
(44) and the second equality in (45) hold since
$\hat{\gamma}\in\Gamma(\mu^{0},\hat{\mu}^{j})$.

Since $\gamma^{*}$ is optimal for $OT(\mu,\mu^{j})$,we have
$C(\gamma^{*};\mu^{0},\mu^{j})\leq C(\gamma;\mu^{0},\mu^{j})$ to denote the
transportation cost for $\gamma^{*}$ and $\gamma$, respectively. We write

$\displaystyle C(\gamma^{*};\mu^{0},\mu^{j})$
$\displaystyle=\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}\|x_{n}^{0}-x_{m}^{j}\|^{2}\gamma^{*}_{n,m}$
$\displaystyle=\sum_{n=1}^{N_{0}}\|x_{n}^{0}\|^{2}p_{n}^{0}+\sum_{m=1}^{N_{j}}\|x_{m}^{j}\|^{2}p_{m}^{j}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}x_{n}\cdot
x_{m}^{j}\,\gamma_{n,m}^{*}$
$\displaystyle=K_{1}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}\hat{x}_{n}\cdot
x_{m}^{j}\,\gamma_{n,m}^{*},$

where $K_{1}$ is a constant (which only depends on $\mu^{0},\mu^{j}$).
Similarly,

$\displaystyle C(\gamma;\mu^{0},\mu^{j})$
$\displaystyle=K_{1}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}x_{n}^{0}\cdot
x_{m}^{j}\,\gamma_{n,m}$
$\displaystyle=K_{1}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}\sum_{\ell=1}^{N_{0}}\frac{\hat{\gamma}_{n,\ell}\gamma^{*}_{\ell,m}}{p^{0}_{\ell}}\,x_{n}^{0}\cdot
x_{m}^{j}$

Analogously, we have

$\displaystyle C(\hat{\gamma}^{*};\mu^{0},\hat{\mu}^{j})$
$\displaystyle=\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{0}}\|\hat{x}_{n}-\hat{x}_{m}^{j}\|^{2}\hat{\gamma}_{n,m}^{*}$
$\displaystyle=\sum_{n=1}^{N_{0}}\|x_{n}^{0}\|^{2}p_{n}^{0}+\sum_{m=1}^{N_{0}}\|\hat{x}_{m}^{j}\|^{2}p_{m}^{0}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{0}}x_{n}^{0}\cdot\hat{x}_{m}^{j}\,\hat{\gamma}^{*}_{n,m}$
$\displaystyle=K_{2}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}x^{0}_{n}\cdot
x_{m}^{j}\,\gamma_{n,m}^{*}$
$\displaystyle=K_{2}-K_{1}+C(\gamma^{*};\mu^{0},\mu^{j})$ (46)

where $K_{2}$ is constant (which only depends on $\mu^{0}$ and
$\hat{\mu}^{j}$) and similarly

$\displaystyle C(\hat{\gamma};\mu^{0},\hat{\mu}^{j})$
$\displaystyle=K_{2}-2\sum_{n=1}^{N_{0}}\sum_{m=1}^{N_{j}}\sum_{\ell=1}^{N_{0}}\frac{\hat{\gamma}_{n,\ell}\gamma^{*}_{\ell,m}}{p^{0}_{\ell}}\,x_{n}^{0}\cdot
x_{m}^{j}$ $\displaystyle=K_{2}-K_{1}+C(\gamma;\mu^{0},\mu^{1})$ (47)

Therefore, by (46) and (47), we have that $C(\gamma^{*};\mu^{0},\mu^{j})\leq
C(\gamma;\mu^{0},\mu^{j})$ if and only if
$C(\hat{\gamma}^{*};\mu^{0},\hat{\mu}^{j})\leq
C(\hat{\gamma};\mu^{0},\hat{\mu}^{j})$. So, we conclude the proof by the fact
$\gamma^{*}$ is optimal for $OT(\mu_{0},\mu^{j})$. ∎

##  Appendix C Proof of Proposition 2.2

######  Lemma C.1.

Given discrete measures
$\mu^{0}=\sum_{k=1}^{N_{0}}p^{0}_{k}\delta_{x^{0}_{k}},\mu^{1}=\sum_{k=1}^{N_{0}}p^{0}_{k}\delta_{x^{1}_{k}},\mu^{2}=\sum_{k=1}^{N_{0}}p^{0}_{k}\delta_{x^{2}_{k}}$,
suppose that the maps $x_{k}^{0}\mapsto x_{k}^{1}$ and $x^{0}_{k}\mapsto
x_{k}^{2}$ solve $OT(\mu^{0},\mu^{1})$ and $OT(\mu^{0},\mu^{2})$,
respectively. For $t\in[0,1]$, define
$\mu_{t}:=\sum_{k=1}^{N_{0}}p_{k}^{0}\delta_{(1-t)x_{k}^{1}+tx_{k}^{2}}$.
Then, the mapping $T_{t}:x_{k}^{0}\mapsto(1-t)x_{k}^{1}+tx_{k}^{2}$ solves the
problem $OT(\mu^{0},\mu_{t})$.

###### Proof.

Let $\gamma^{*}=\operatorname{diag}(p_{1}^{0},\ldots,p_{N_{0}}^{0})$ be the
corresponding transportation plan induced by $T_{t}$. Consider an arbitrary
$\gamma\in\mathbb{R}_{+}^{N_{0}\times N_{0}}$ such that
$\gamma\in\Gamma(\mu^{0},\mu_{t})$. We need to show

$C(\gamma^{*};\mu^{0},\mu_{t})\leq C(\gamma;\mu^{0},\mu_{t}).$

We have

$\displaystyle C(\gamma^{*};\mu^{0},\mu_{t})$
$\displaystyle=\sum_{k,k^{\prime}=1}^{N_{0}}\|x^{0}_{k}-(1-t)x^{1}_{k^{\prime}}-tx_{k^{\prime}}^{2}\|^{2}\,\gamma^{*}_{k,k^{\prime}}$
$\displaystyle=\sum_{k=1}^{N_{0}}\|x_{k}^{0}\|^{2}p_{k}^{0}+\sum_{k=1}^{N_{0}}\|(1-t)x_{k^{\prime}}^{1}+tx_{k^{\prime}}^{2}\|^{2}p_{k}^{0}-2\sum_{k,k^{\prime}=1}^{N_{0}}x_{k}^{0}\cdot((1-t)x_{k^{\prime}}^{1}+tx_{k^{\prime}}^{2})$
$\displaystyle=K-2\left[(1-t)\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{1}\,\gamma_{k,k^{\prime}}^{*}+t\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{2}\,\gamma_{k,k^{\prime}}^{*}\right],$ (48)

where in third equation, $K$ is a constant which only depends on the marginals
$\mu^{0},\mu_{t}$. Similarly,

$\displaystyle C(\gamma;\mu^{0},\mu_{t})$
$\displaystyle=K-2\left[(1-t)\sum_{k,k^{\prime}=1}^{N_{0}}\,\hat{x}_{k}\cdot
x_{k^{\prime}}^{1}\gamma_{k,k^{\prime}}+t\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{2}\,\gamma_{k,k^{\prime}}\right].$ (49)

By the fact that
$\gamma,\gamma^{*}\in\Gamma(\hat{\mu},\mu_{t})=\Gamma(\mu^{0},\mu^{1})=\Gamma(\mu^{0},\mu^{2})$,
and that $\gamma^{*}$ is optimal for
$OT(\hat{\mu},\mu^{1}),OT(\hat{\mu},\mu^{2})$, we have

$\displaystyle\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{1}\,\gamma_{k,k^{\prime}}^{*}\geq\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{1}\,\gamma_{k,k^{\prime}}\qquad\text{ and
}\qquad\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{2}\,\gamma_{k,k^{\prime}}^{*}\geq\sum_{k,k^{\prime}=1}^{N_{0}}\hat{x}_{k}\cdot
x_{k^{\prime}}^{2}\,\gamma_{k,k^{\prime}}.$

Thus, by (48) and (49), we have $C(\gamma^{*};\hat{\mu},\mu_{t})\leq
C(\gamma;\hat{\mu},\mu_{t})$, and this completes the proof. ∎

###### Proof of Proposition 2.2.

Consider $0\leq s\leq t\leq 1$. By Lemma 2.1, the maps
$T^{i}:x^{0}_{k}\mapsto\hat{x}^{i}_{k}$,
$T^{j}:x^{0}_{k}\mapsto\hat{x}^{j}_{k}$ solve
$OT(\mu^{0},\hat{\mu}^{i}),OT(\mu^{0},\hat{\mu}^{j})$, respectively. Moreover,
by Lemma C.1 (under the appropriate renaming), we have the mapping

$x^{0}_{k}\mapsto(1-s)\hat{x}^{i}_{k}+s\hat{x}_{k}^{j}=x_{k}^{0}+(1-s)u^{i}_{k}+su^{j}_{k},\qquad
1\leq k\leq N_{0}$

solves $OT(\mu^{0},\hat{\rho}_{s})$, and similarly

$x^{0}_{k}\mapsto(1-t)\hat{x}^{i}_{k}+t\hat{x}_{k}^{j}=x_{k}^{0}+(1-t)u^{i}_{k}+tu^{j}_{k},\qquad
1\leq k\leq N_{0}$

solves $OT(\mu^{0},\hat{\rho}_{t})$.

Thus,

$\displaystyle LOT_{\mu^{0}}(\hat{\rho}_{s},\hat{\rho}_{t})$
$\displaystyle=\sum_{k=1}^{N_{0}}\|((1-s)\hat{x}^{i}_{k}+s\hat{x}_{k}^{j})-((1-t)\hat{x}^{i}_{k}+t\hat{x}_{k}^{j})\|^{2}\,p_{k}^{0}$
$\displaystyle=\sum_{k=1}^{N_{0}}(t-s)^{2}\|\hat{x}_{k}^{i}-\hat{x}_{k}^{j}\|^{2}\,p_{k}^{0}$
$\displaystyle=(t-s)^{2}LOT_{\mu^{0}}(\mu^{i},\mu^{j}),$

and this finishes the proof. ∎

##  Appendix D Proof of proposition 3.1

This result relies on the definition (29) of the curve $\rho_{t}$, which is
inspired by the fact that solutions of non-homogeneous equations are given by
solutions of the associated homogeneous equation plus a particular solution of
the non-homogeneous. We choose the first term of $\rho_{t}$ as a solution of a
(homogeneous) continuity equation ($\gamma_{t}$ defined in (28)), and the
second term ($\overline{\gamma}_{t}:=(1-t)\nu_{0}+t\nu^{j}$) as an appropriate
particular solution of the equation (26) with forcing term $\zeta$ defined in
(31). Moreover, the curve $\rho_{t}$ will become optimal for (25) since both
$\gamma_{t}$ and $\overline{\gamma}_{t}$ are ‘optimal’ in different senses. On
the one hand, $\gamma_{t}$ is optimal for a classical optimal transport
problem151515Here we will strongly use that the fixed partial optimal
transport plan $\gamma^{*}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$ in the
hypothesis of the proposition has the form $\gamma^{*}=(I\times
T)_{\\#}\gamma_{0}^{*}$, for a map $T:\Omega\to\Omega$. On the other hand,
$\overline{\gamma}_{t}$ is defined as a line interpolating the new part
introduced by the framework of partial transportation, ‘destruction and
creation of mass’.

Although this is the core idea behind the proposition, to prove it we need
several lemmas to deal with the details and subtleties.

First, we mention that, the push-forward measure $F_{\\#}\mu$ can be defined
satisfying the formula of change of variables

$\int_{A}g(x)\,dF_{\\#}\mu(x)=\int_{F^{-1}(A)}g(F(x))\,d\mu(x)$

for all measurable set $A$, and all measurable function $g$, where
$F^{-1}(A)=\\{x:\,F(x)\in A\\}$. This is a general fact, and as an immediate
consequence, we have conservation of mass

$|F_{\\#}\mu|=|\mu|.$

Then, in our case, the second term in the cost function (24) we can be written
as

$\lambda(|\mu^{0}-\gamma_{0}|+|\mu^{j}-\gamma_{1}|=\lambda(|\mu^{0}|+|\mu^{1}|-2|\gamma|)$

since $\gamma_{0}$ and $\gamma_{1}$ are dominated by $\mu^{0}$ and $\mu^{j}$,
respectively, in the sense that $\gamma_{0}\leq\mu^{0}$ and
$\gamma_{1}\leq\mu^{j}$.

Finally, we would like to point out that when we say that $(\rho,v,\zeta)$ is
a solution for equation (26), we mean that it is a weak solution or,
equivalently, it is a solution in the distributional sense [38, Section 4 4].
That is, for any test function $\psi:\Omega\to\mathbb{R}$ continuous
differentiable with compact support, $(\rho,v,\zeta)$ satisfies

$\displaystyle\partial_{t}\left(\int_{\Omega}\psi\,d\rho_{t}\right)-\int_{\Omega}\nabla\psi\cdot
v_{t}\,d\rho_{t}=\int_{\Omega}\psi\,d\zeta_{t},$

or, equivalently, for any test function $\phi:[0,1]\times\Omega\to\mathbb{R}$
continuous differentiable with compact support, $(\rho,v,\zeta)$ satisfies

$\displaystyle\int_{[0,1]\times\Omega}\partial_{t}\phi\,d\rho+\int_{[0,1]\times\Omega}\nabla\phi\cdot
v\,d\rho+\int_{[0,1]\times\Omega}\,d\zeta=\int_{\Omega}\phi(1,\cdot)\,d\mu^{j}-\int_{\Omega}\phi(0,\cdot)\,d\mu^{0}.$

######  Lemma D.1.

If $\gamma^{*}$ is optimal for $OPT_{\lambda}(\mu^{0},\mu^{1})$, and has
marginals $\gamma_{0}^{*}$ and $\gamma_{1}^{*}$, then $\gamma^{*}$ is optimal
for $OPT_{\lambda}(\mu^{0},\gamma_{1}^{*})$,
$OPT_{\lambda}(\gamma_{0}^{*},\mu^{1})$ and
$OT(\gamma_{0}^{*},\gamma_{1}^{*})$.

###### Proof.

Let $C(\gamma;\mu^{0},\mu^{1},\lambda)$ denote the objective function of the
minimization problem ${OPT}_{\lambda}(\mu^{0},\mu^{1})$, and similarly
consider
$C(\gamma;\gamma_{0}^{*},\mu^{1},\lambda),C(\gamma;\mu^{0},\gamma_{1}^{*},\lambda)$.
Also, let $C(\gamma,\gamma_{0}^{*},\gamma_{1}^{*})$ be the objective function
of ${OT}(\gamma_{0}^{*},\gamma_{1}^{*})$.

First, given an arbitrary plan
$\gamma\in\Gamma(\gamma_{0}^{*},\gamma_{1}^{*})\subset\Gamma_{\leq}(\mu^{0},\mu^{1})$,
we have

$\displaystyle C(\gamma;\mu^{0},\mu^{1},\lambda)$
$\displaystyle=\int_{\Omega^{2}}\|x^{0}-x^{1}\|^{2}d\gamma(x^{0},x^{1})+\lambda(|\mu^{0}-\gamma_{0}|+|\mu^{1}-\gamma_{1}|)$
$\displaystyle=C(\gamma;\gamma_{0}^{*},\gamma_{1}^{*})+\lambda(|\mu^{0}-\gamma_{0}|+|\mu^{1}-\gamma_{1}|).$

Since $C(\gamma^{*};\mu^{0},\mu^{1},\lambda)\leq
C(\gamma;\mu^{0},\mu^{1},\lambda)$, we have
$C(\gamma^{*};\gamma_{0}^{*},\gamma_{1}^{*})\leq
C(\gamma;\gamma_{0}^{*},\gamma_{1}^{*})$. Thus, $\gamma^{*}$ is optimal for
${OT}(\gamma_{0}^{*},\gamma_{1}^{*})$.

Similarly, for every $\gamma\in\Gamma_{\leq}(\gamma_{0}^{*},\mu^{1})$, we have
$C(\gamma;\mu^{0},\mu^{1},\lambda)=C(\gamma;\gamma_{0}^{*},\mu^{1})+\lambda|\mu^{0}-\gamma^{*}_{0}|$
and thus $\gamma^{*}$ is optimal for
${OPT}_{\lambda}(\gamma_{0}^{*},\mu^{1})$. Analogously, $\gamma^{*}$ is
optimal for ${OPT}_{\lambda}(\mu^{0},\gamma_{1}^{*})$. ∎

######  Lemma D.2.

If $\gamma^{*}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{1})$, then
$d\left({\operatorname{supp}}(\nu^{0}),{\operatorname{supp}}(\nu^{1})\right)\geq\sqrt{2\lambda}$,
where $\nu^{0}=\mu^{0}-\gamma_{0}$, $\nu^{1}=\mu^{1}-\gamma_{1}$, and $d$ is
the Euclidean distance in $\mathbb{R}^{d}$.

###### Proof.

We will proceed by contradiction. Assume that
$d\left(\operatorname{supp}(\nu^{0}),{\operatorname{supp}}(\nu^{1})\right)<\sqrt{2\lambda}$.
Then, there exist $\widetilde{x}^{0}\in{\operatorname{supp}}(\nu^{0})$ and
$\widetilde{x}^{1}\in{\operatorname{supp}}(\nu^{1})$ such that
$\|\widetilde{x}^{0}-\widetilde{x}^{1}\|<\sqrt{2\lambda}$. Moreover, we can
choose $\varepsilon>0$ such $\nu^{0}(B(\widetilde{x}^{0},\varepsilon))>0$ and
$\nu^{1}(B(\widetilde{x}^{1},\varepsilon))>0$, where
$B(\widetilde{x}^{i},\varepsilon)$ denotes the ball in $\mathbb{R}^{d}$ of
radius $\varepsilon$ centered at $\widetilde{x}^{i}$.

We will construct $\widetilde{\gamma}\in\Gamma_{\leq}(\mu^{0},\mu^{1})$ with
transportation cost strictly less than $OPT_{\lambda}(\mu^{0},\mu^{1})$,
leading to a contradiction. For $i=0,1$ we denote by $\widetilde{\nu}^{i}$ the
probability measure given by
$\frac{1}{\nu^{i}(B(\widetilde{x}^{i},\varepsilon))}\nu^{i}$ restricted to
$B(\widetilde{x}^{i},\varepsilon)$. Let
$\delta=\min\\{\nu^{0}(B(\widetilde{x}^{0},\varepsilon)),\nu^{1}(B(\widetilde{x}^{1},\varepsilon))\\}$.
Now, we consider

$\widetilde{\gamma}:=\gamma^{*}+\delta(\,\widetilde{\nu}^{0}\times\widetilde{\nu}^{1}).$

Then, $\widetilde{\gamma}\in\Gamma_{\leq}(\mu^{0},\mu^{1})$ because

$\pi_{i\\#}\widetilde{\gamma}=\gamma_{i}+\delta\widetilde{\nu}^{i}\leq\gamma_{i}+\nu^{i}=\mu^{i}\qquad\text{
for }i=0,1.$

The partial transport cost of $\widetilde{\gamma}$ is

$\displaystyle C(\widetilde{\gamma},\mu^{0},\mu^{1},\lambda)$
$\displaystyle=\int_{\Omega^{2}}\|x^{0}-x^{1}\|^{2}\,d\widetilde{\gamma}+\lambda(|\mu^{0}|+|\mu^{1}|-2|\widetilde{\gamma}|)$
$\displaystyle=\int_{\Omega^{2}}\|x^{0}-x^{1}\|^{2}\,d\gamma+\delta\int_{\Omega^{2}}\|x^{0}-x^{1}\|^{2}\,d(\widetilde{\nu}^{0}\times\widetilde{\nu}^{1})$
$\displaystyle\quad+\lambda(|\mu^{0}|+|\mu^{1}|-2|\gamma|-2\delta|\widetilde{\nu}^{0}\times\widetilde{\nu}^{1}|)$
$\displaystyle=OPT_{\lambda}(\mu^{0},\mu^{1})+\delta\int_{B(\widetilde{x}^{0},\varepsilon)\times
B(\widetilde{x}^{1},\varepsilon)}\|x^{0}-x^{1}\|^{2}\,d(\widetilde{\nu}^{0}\times\widetilde{\nu}^{1})-2\lambda\delta$
$\displaystyle<OPT_{\lambda}(\mu^{0},\mu^{1})+2\lambda\delta-2\lambda\delta=OPT_{\lambda}(\mu^{0},\mu^{1}),$

which is a contradiction.

∎

######  Lemma D.3.

Using the notation and hypothesis of Proposition 3.1, for $t\in(0,1)$ let
$D_{t}:=\\{x:v_{t}(x)\neq 0\\}$. Then,
$\gamma_{t}\wedge\nu_{0}\equiv\gamma_{t}\wedge\nu^{j}\equiv 0$ over $D_{t}$.

###### Proof.

We will prove this for $\gamma_{t}\wedge\nu_{0}$. The other case is analogous.
Suppose by contradiction that $\gamma_{t}\wedge\nu_{0}$ is not the null
measure. By Lemma D.1, we know that $\gamma^{*}$ is optimal for
$OT(\gamma_{0}^{*},\gamma_{1}^{*})$. Since we are also assuming that $\gamma$
is induced by a map $T$, i.e. $\gamma^{*}=(I\times T)_{\\#}\gamma_{0}^{*}$,
then $T$ is an optimal Monge map between $\gamma_{0}^{*}$ and
$\gamma_{1}^{*}$. Therefore, the map $T_{t}:\Omega\to\Omega$ is invertible
(see for example [38, Lemma 5.29]). For ease of notation we will denote
$\widetilde{\nu}^{0}:=\gamma_{t}\wedge\nu_{0}$ as a measure in $D_{t}$.

The idea of the proof is to exhibit a plan $\widetilde{\gamma}$ with smaller
$OPT_{\lambda}$ cost than $\gamma^{*}$, which will be a contradiction since
$\gamma^{*}\in\Gamma_{\leq}^{*}(\mu^{0}\mu^{j})$. Let us define

$\widetilde{\gamma}:=\gamma^{*}+(I,T\circ
T_{t}^{-1})_{\\#}\widetilde{\nu}^{0}-(I,T)_{\\#}(T_{t}^{-1})_{\\#}\widetilde{\nu}^{0}.$

Then, $\widetilde{\gamma}\in\Gamma_{\leq}(\mu^{0},\mu^{j})$ since

$\displaystyle\pi_{0\\#}\widetilde{\gamma}=\pi_{0\\#}\gamma^{*}+\widetilde{\nu}^{0}-(T_{t}^{-1})_{\\#}\widetilde{\nu}^{0}\leq\gamma_{0}^{*}+\widetilde{\nu}^{0}\leq\mu^{0},$
$\displaystyle\pi_{1\\#}\widetilde{\gamma}=\pi_{1\\#}\gamma^{*}+(T\circ
T_{t}^{-1})_{\\#}\widetilde{\nu}^{0}-(T\circ
T_{t}^{-1})_{\\#}\widetilde{\nu}^{0}=\gamma_{1}^{*}.\qquad(\text{and we know
}\gamma_{1}^{*}\leq\mu^{j}).$

From the last equation we can also conclude that
$|\widetilde{\gamma}|=|\gamma_{1}^{*}|=|\gamma^{*}|$. Therefore, the partial
transportation cost for $\widetilde{\gamma}$ is

$\displaystyle\int_{\Omega^{2}}\|x-y\|^{2}d\widetilde{\gamma}(x,y)+\lambda(|\mu^{0}|+|\mu^{j}|-2|\widetilde{\gamma}|)$
$\displaystyle\qquad=\underbrace{\int_{\Omega^{2}}\|x-y\|d\gamma^{*}(x,y)+\lambda(|\mu^{0}|+|\mu^{j}|-2|\gamma|)}_{OPT_{\lambda}(\mu^{0},\mu^{j})}$
$\displaystyle\qquad+\int_{D_{t}}\left(\|x-T(T_{t}^{-1}(x))\|^{2}-\|T_{t}^{-1}(x)-T(T_{t}^{-1}(x))\|^{2}\right)d\widetilde{\nu}^{0}(x)$
$\displaystyle\qquad<OPT_{\lambda}(\mu^{0},\mu^{1})$

where in the last inequality we used that if $y=T_{t}^{-1}(x)$ we have

$\|T_{t}(y)-T(y)\|=\|(1-t)y+tT(y)-T(y)\|=(1-t)\|y-T(y)\|<\|y-T(y)\|\qquad\text{for
}t\in(0,1).$

∎

######  Lemma D.4.

Using the notation and hypothesis of Proposition 3.1, for $t\in(0,1)$ the
vector-valued measures $v_{t}\cdot\nu_{0}$ and $v_{t}\cdot\nu^{j}$ are exactly
zero.

###### Proof.

We prove this for $v_{t}\cdot\nu_{0}$. The other case is analogous. We recall
that the measure $v_{t}\cdot\nu_{0}$ is determined by

$\int_{\Omega}\Phi(x)\cdot v_{t}(x)\,d\nu_{0}(x)$

for all measurable functions $\Phi:\Omega\to\mathbb{R}^{d}$, where
$\Phi(x)\cdot v_{t}(x)$ denotes the usual dot product in $\mathbb{R}^{d}$
between the vectors $\Phi(x)$ and $v_{t}(x)$.

From Lemma D.3 we know that $\gamma_{t}\wedge\nu_{0}\equiv 0$ over $D_{t}$.
Therefore, $\gamma_{t}$ and $\nu_{0}$ are mutually singular in that set. This
implies that we can decompose $D_{t}$ into two disjoint sets $D_{1}$, $D_{2}$
such that $\gamma_{t}(D_{1})=0=\nu_{0}(D_{2})$. Since $v_{t}$ is a function
defined $\gamma_{t}$–almost everywhere (up to sets of null measure with
respect to $\gamma_{t}$), we can assume without loss of generality that
$v_{t}\equiv 0$ on $D_{1}$.

Let $\Phi:\Omega\to\mathbb{R}^{d}$ be a measurable vector-valued function over
$\Omega$. Using that $v_{t}\equiv 0$ in $\Omega\setminus D_{t}$ and in
$D_{1}$, and that $\nu_{0}(D_{2})=0$, we obtain

$\displaystyle\int_{\Omega}\Phi(x)\cdot v_{t}(x)\,d\nu_{0}(x)$
$\displaystyle=\int_{\Omega\setminus D_{t}}\Phi(x)\cdot
v_{t}(x)\,d\nu_{0}(x)+\int_{D_{1}}\Phi(x)\cdot v_{t}(x)\,d\nu_{0}(x)$
$\displaystyle\quad+\int_{D_{2}}\Phi(x)\cdot v_{t}(x)\,d\nu_{0}(x)$
$\displaystyle=0.$

Since $\Phi$ was arbitrary, we can conclude that $v_{t}\cdot\nu_{0}\equiv 0$.
∎

######  Lemma D.5.

Using the notation and hypothesis of Proposition 3.1, the measure
$\overline{\gamma}_{t}=(1-t)\nu_{0}+t\nu^{1}$ satisfies the equation

$\begin{cases}\partial_{t}\overline{\gamma}+\nabla\cdot\overline{\gamma}v=\zeta\\\
\overline{\gamma}_{0}=\nu_{0},\quad\overline{\gamma}_{1}=\nu^{1}.\end{cases}$
(50)

###### Proof.

From Lemma D.4 we have that
$v_{t}\cdot\overline{\gamma}_{t}=(1-t)v_{t}\cdot\nu_{0}+tv_{t}\cdot\nu^{1}=0$,
then $\nabla\cdot\overline{\gamma}v=0$. It is easy to see that
$\overline{\gamma}$ satisfies the boundary conditions by replacing $t=0$ and
$t=1$ in its definition. Also,
$\partial_{t}\overline{\gamma}=\nu^{1}-\nu_{0}$. Then, since
$\zeta_{t}=\nu^{1}-\nu_{0}$ for every $t$, we get
$\partial_{t}\overline{\gamma}+\nabla\cdot\overline{\gamma}v=\nu^{1}-\nu_{0}+0=\zeta_{t}$.
∎

###### Proof of Proposition 3.1.

First, we address that the $v:[0,1]\times\Omega\to\mathbb{R}^{d}$ is well
defined. Indeed, by Lemma D.1, we have that $\gamma^{*}=(\mathrm{id}\times
T)_{\\#}\gamma_{0}^{*}$ is optimal for $OT(\gamma_{0}^{*},\gamma_{1}^{*})$.
Thus, for each $(t,x)\in[0,1]\times\Omega$, by so-called cyclical monotonicity
property of the support of classical optimal transport plans, there exists at
most one $x_{0}\in\operatorname{supp}(\gamma_{0}^{*})$ such that
$T_{t}(x_{0})=x$, see [38, Lemma 5.29]. So, $v_{t}(x)$ in (30) is well defined
by understanding its definition as

$v_{t}(x)=\begin{cases}T(x_{0})-x_{0}&\text{if }x=T_{t}(x_{0}),\quad\text{ for
}x_{0}\in\operatorname{supp}(\gamma_{0}^{*})\\\
0&\text{elsewhere}.\end{cases}$

Now, we check that $(\rho,v,\zeta)$ defined in (29), (30), (31) is a solution
for (26). In fact,

$\rho_{t}=\gamma_{t}+\overline{\gamma}_{t}$

where $\gamma_{t}$ is given by (28), and $\overline{\gamma}_{t}$ is as in
Lemma D.5. Then, from section 2.2, $(\gamma,v)$ solves the continuity equation
(5) since $\gamma^{*}=(I\times
T)_{\\#}\gamma_{0}^{*}\in\Gamma^{*}(\gamma_{0}^{*},\gamma_{1}^{*})$ (Lemma
D.1), and from its definition $\gamma_{t}=(T_{t})_{\\#}\gamma_{0}^{*}$
coincides with (9) in this context, as well as $v_{t}$ coincides with (8) (the
support of $v_{t}$ lies on the support of $\gamma_{0}^{*}$). On the other
hand, from Lemma D.5, $\overline{\gamma}_{t}$ solves (50). Therefore, by
linearity,

$\displaystyle\partial_{t}\rho_{t}+\nabla\cdot\rho_{t}v_{t}=\underbrace{\partial_{t}\gamma_{t}+\nabla\cdot\gamma_{t}v_{t}}_{0}+\underbrace{\partial_{t}\overline{\gamma}_{t}+\nabla\cdot\overline{\gamma}_{t}v_{t}}_{\zeta_{t}}=\zeta_{t}$

Finally, by plugging in $(\rho,v,\zeta)$ into the objective function in (25),
we have:

$\displaystyle\int_{[0,1]\times\Omega}\|v\|^{2}d\rho+\lambda|\zeta|$
$\displaystyle=\int_{[0,1]\times\Omega}\|v\|^{2}\,d\gamma_{t}\,dt+\lambda|\zeta|$
$\displaystyle=\int_{\Omega}\|T(x^{0})-x^{0}\|^{2}\,d\gamma_{0}^{*}(x^{0})+\lambda(|\nu_{0}|+|\nu^{1}|)$
$\displaystyle=\int_{\Omega^{2}}\|x^{0}-x^{j}\|^{2}\,d\gamma^{*}(x^{0},x^{j})+\lambda(|\mu^{0}-\gamma_{0}^{*}|+|\mu^{j}-\gamma_{1}^{*}|)$
$\displaystyle=OPT_{\lambda}(\mu^{0},\mu^{j})$

since $\gamma^{*}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$. So, this shows that
$(\rho,v,\zeta)$ is minimum for (25).

The ‘moreover’ part holds from the above identities, using that

$\displaystyle\int_{\Omega}\|v_{0}\|^{2}d\gamma_{0}^{*}(x_{0})+\lambda(|\nu_{0}|+|\nu^{1}|)=\int_{\Omega}\min(\|v_{0}\|^{2},2\lambda)d\gamma_{0}^{*}(x_{0})+\lambda(|\nu_{0}|+|\nu^{1}|)$
$\displaystyle\qquad\text{ for }v_{0}(x^{0})=T(x^{0})-x^{0},$

since $\gamma^{*}$ is such that $\|x^{0}-x^{j}\|^{2}<2\lambda$ for all
$(x^{0},x^{j})\in\operatorname{supp}(\gamma)$ [4, Lemma 3.2].

∎

##  Appendix E Proof of Theorem 3.5

The proof will be similar to that of Lemma 2.1.

###### Proof.

We fixed $\gamma^{j}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$. We will understand
the second marginal distribution $\pi_{1\\#}\gamma^{j}$ induced by
$\gamma^{j}$, either as the vector $\gamma^{j}_{1}:=(\gamma^{j})^{T}1_{N_{0}}$
or as the measure $\sum_{m=1}^{N_{j}}(\gamma^{j}_{1})_{m}\delta_{x_{m}^{j}}$,
and, by abuse of notation, we will write $\pi_{1\\#}\gamma^{j}=\gamma_{1}^{j}$
(analogously for $\pi_{0\\#}\gamma^{j}$).

Let
$\hat{\gamma}^{j}:=\operatorname{diag}(\hat{p}_{1}^{j},\ldots,\hat{p}_{N_{0}}^{j})$
denote the transportation plan induced by mapping
$x_{k}^{0}\mapsto\hat{x}_{k}^{j}$. Let $D:=\\{k\in\\{1,\dots
N_{0}\\}:\hat{p}_{k}^{j}>0\\}$.

Given any $\hat{\gamma}\in\Gamma_{\leq}(\mu^{0},\hat{\mu}^{j})$, we need to
show

$C(\hat{\gamma}^{j};\mu^{0},\hat{\mu}^{j},\lambda)\leq
C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda).$ (51)

We recall that we are denoting by $p^{0}$ the vector of weights of the
discrete measure $\mu^{0}$ (analogously, $p^{j}$ and $\hat{p}^{j}$ are the
vectors of weights of $\mu^{j}$ and $\hat{\mu}^{j}$, resp).

In general, if we consider any transportation plan
$\gamma^{\prime}\in\Gamma_{\leq}(\mu_{0},\gamma_{1}^{j})$, we have that

$\displaystyle C(\gamma^{\prime};\mu^{0},\gamma_{1}^{j},\lambda)$
$\displaystyle=\sum_{k=1}^{N_{0}}\sum_{i=1}^{N_{j}}\|x_{k}^{0}-x_{i}^{j}\|^{2}\gamma_{k,i}^{\prime}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{\prime}|)$
$\displaystyle=\sum_{k=1}^{N_{0}}\sum_{i=1}^{N_{j}}\|x_{k}^{0}-x_{i}^{j}\|^{2}\gamma^{\prime}_{k,i}+\lambda(|p^{0}|+|p^{j}|-2|\gamma^{\prime}|)+\lambda(-|p^{j}|-|\gamma_{1}^{j}|)$
$\displaystyle=C(\gamma^{\prime};\mu^{0},\mu^{j},\lambda)+\lambda(-|p^{j}|-|\gamma_{1}^{j}|).$

Similarly,

$\displaystyle
C(\gamma^{j};\mu^{0},\gamma_{1}^{j},\lambda)=C(\gamma^{j};\mu^{0},\mu^{j},\lambda)+\lambda(-|p^{j}|-|\gamma_{1}^{j}|)$

Since $\gamma^{j}$ is optimal for $OPT_{\lambda}(\mu^{0},\mu^{j})$, then
$C(\gamma^{j};\mu^{0},\mu^{j},\lambda)\leq
C(\gamma^{\prime};\mu^{0},\mu^{j},\lambda)$ and thus
$C(\gamma^{j};\mu^{0},\gamma_{1}^{j},\lambda)\leq
C(\gamma^{\prime};\mu^{0},\gamma_{1}^{j},\lambda)$.

However, we need to have more control over the bounds in order to compare
different costs. Therefore, as we did in Lemma 2.1, we will define a
particular plan $\gamma$ to use a pivot and obtain (51).

With a slight abuse of notation, we define

$\gamma:=\hat{\gamma}\frac{1}{\hat{\gamma}^{j}}\gamma^{j}$

where we mean that

$\left(\frac{1}{\hat{\gamma}^{j}}\gamma^{j}\right)_{ki}:=\begin{cases}\gamma^{j}_{k,i}/\hat{\gamma}^{j}_{k,k}&\text{if
}k\in D\\\ 0&\text{elsewhere}.\end{cases}$

First, we claim $\gamma\in\Gamma_{\leq}(\mu^{0},\gamma_{1}^{j})$. Indeed, we
have

$\displaystyle\gamma 1_{N_{j}}$
$\displaystyle=\hat{\gamma}\frac{1}{\hat{\gamma}^{j}}\gamma^{j}1_{N_{j}}=\hat{\gamma}\frac{1}{\hat{\gamma}^{j}}\hat{p}^{j}=\hat{\gamma}\beta\leq
p^{0}$ (52) $\displaystyle\gamma^{T}1_{N_{0}}$
$\displaystyle=(\gamma^{j})^{T}\frac{1}{\hat{\gamma}^{j}}\hat{\gamma}^{T}1_{N_{0}}\leq(\gamma^{j})^{T}\frac{1}{\hat{\gamma}^{j}}\hat{p}^{j}=(\gamma^{j})^{T}\beta=\gamma^{j}_{1},$
(53)

where $\beta\in\mathbb{R}^{N_{0}\times 1}$ is defined with $\beta_{k}=1$ if
$k\in D$ and $\beta_{k}=0$ elsewhere. In fact, in (52), the first inequality
follows from the fact each entry in the $N_{0}\times 1$ vector
$\frac{1}{\hat{\gamma}^{j}}\hat{p}^{j}$ is either 0 or 1; and the second
inequality holds since $\hat{\gamma}\in\Gamma_{\leq}(\mu^{0},\hat{\mu}^{j})$.
And in (53), the inequality follows from the fact
$\hat{\gamma}^{T}\in\Gamma_{\leq}(\mu^{0},\hat{\mu}^{j})$.

In addition, since $(\hat{\gamma}^{j})^{T}1_{N_{0}}\leq\hat{p}^{j}$, we have
$\hat{\gamma}_{k,k^{\prime}}=0,\forall k^{\prime}\notin
D,k\in\\{1,\ldots,N_{0}\\}$. Thus we have

$\gamma 1_{N_{j}}=\hat{\gamma}\beta=\hat{\gamma}1_{N_{0}}$

that is the first marginals of $\gamma$ and $\hat{\gamma}$ are same and thus
$|\gamma|=|\hat{\gamma}|$.

We compute the transportation costs induced by
$\gamma^{j},\gamma,\hat{\gamma}^{j},\hat{\gamma}$:

$\displaystyle C(\gamma^{j};\mu^{0},\gamma_{1}^{j},\lambda)$
$\displaystyle=\sum_{i=1}^{N_{j}}\sum_{k\in
D}\|x_{k}^{0}-x_{i}^{j}\|^{2}\gamma_{k,i}^{j}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{j}|)$
$\displaystyle=\sum_{k\in
D}\|x^{0}_{k}\|^{2}(\gamma_{0}^{j})_{k}+\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}(\gamma_{1}^{j})_{i}-2\sum_{k\in
D}\sum_{i=1}^{N_{j}}x_{k}^{0}\cdot
x_{i}^{j}\,\gamma_{k,i}^{j}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{j}|)$
$\displaystyle=\sum_{k\in
D}\|x^{0}_{k}\|^{2}\hat{p}_{k}^{j}+\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}(\gamma_{1}^{j})_{i}-2\sum_{k\in
D}\sum_{i=1}^{N_{j}}x_{k}^{0}\cdot
x_{i}^{j}\,\gamma_{k,i}^{j}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{j}|)$

Similarly,

$\displaystyle C(\hat{\gamma}^{j};\mu^{0},\hat{\mu}^{j},\lambda)$
$\displaystyle=\sum_{k\in
D}\|x^{0}_{k}\|^{2}(\hat{\gamma}_{0}^{j})_{k}+\sum_{k^{\prime}\in
D}\|\hat{x}_{k^{\prime}}^{j}\|^{2}\hat{p}_{k^{\prime}}^{j}-2\sum_{k\in
D}\sum_{k^{\prime}\in
D}x_{k}^{0}\cdot\hat{x}_{k^{\prime}}^{j}\,\hat{\gamma}_{k,k^{\prime}}^{j}+\lambda(|p^{0}|+|\hat{p}^{j}|-2|\hat{\gamma}^{j}|)$
$\displaystyle=\sum_{k\in
D}\|x_{k}^{0}\|^{2}\hat{p}^{j}_{k}+\sum_{k^{\prime}\in
D}\|\hat{x}_{k^{\prime}}^{j}\|^{2}\hat{p}_{k^{\prime}}^{j}-2\sum_{k\in
D}\sum_{k^{\prime}\in D}\sum_{i=1}^{N_{j}}x_{k}^{0}\cdot
x_{i}^{j}\,\gamma^{j}_{k^{\prime},i}\frac{\hat{\gamma}^{j}_{k,k^{\prime}}}{\hat{\gamma}^{j}_{k^{\prime},k^{\prime}}}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{j}|)$
$\displaystyle=\sum_{k\in
D}\|x_{k}^{0}\|^{2}\hat{p}_{k}^{j}+\sum_{k^{\prime}\in
D}\|\hat{x}_{k^{\prime}}^{j}\|^{2}\hat{p}_{k^{\prime}}^{j}-2\sum_{k\in
D}\sum_{i=1}^{N_{j}}x_{k}^{0}\cdot
x_{i}^{j}\,\gamma^{j}_{k,i}+\lambda(|p^{0}|+|\gamma_{1}^{j}|-2|\gamma^{j}|)$
$\displaystyle=C(\gamma^{j};\mu^{0},\gamma_{1}^{j},\lambda)-\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}(\gamma^{j}_{1})_{i}+\sum_{k^{\prime}\in
D}\|\hat{x}_{k^{\prime}}^{j}\|^{2}\hat{p}_{k^{\prime}}^{j}$ (54)

And also,

$\displaystyle C(\gamma;\mu^{0},\gamma_{1}^{j},\lambda)$
$\displaystyle=\sum_{k=1}^{N_{0}}\|x_{k}^{0}\|^{2}(\gamma_{0})_{k}+\sum_{i=1}^{N_{j}}\|x^{j}_{i}\|^{2}(\gamma_{1})_{i}-2\sum_{k=1}^{N_{0}}\sum_{i=1}^{N_{j}}\sum_{k^{\prime}\in
D}x_{k}^{0}\cdot
x_{i}^{j}\,\hat{\gamma}_{k,k^{\prime}}\frac{\gamma^{j}_{k^{\prime},i}}{\hat{\gamma}_{k^{\prime},k^{\prime}}^{j}}$
$\displaystyle\quad+\lambda(|p^{0}|+|\gamma^{j}_{1}|-2|\gamma|),$
$\displaystyle C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda)$
$\displaystyle=\sum_{k=1}^{N_{0}}\|x_{k}^{0}\|^{2}(\hat{\gamma}_{0})_{k}+\sum_{k^{\prime}\in
D}\|\hat{x}_{k^{\prime}}^{j}\|^{2}(\hat{\gamma}_{1})_{k^{\prime}}-2\sum_{k=1}^{N_{0}}\sum_{k^{\prime}\in
D}\sum_{i=1}^{N_{0}}x_{k}^{0}\cdot
x_{i}^{j}\,\hat{\gamma}_{k,k^{\prime}}^{j}\frac{\gamma^{j}_{k^{\prime},i}}{\hat{\gamma}^{j}_{k^{\prime},k^{\prime}}}$
(55) $\displaystyle\quad+\lambda(|p^{0}|+|\hat{p}^{j}|-2|\hat{\gamma}|)$
$\displaystyle=C(\gamma;\mu^{0},\gamma_{1}^{j},\lambda)-\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}(\gamma_{1})_{i}+\sum_{k^{\prime}\in
D}\|\hat{x}^{j}_{k^{\prime}}\|^{2}(\hat{\gamma}_{1})_{k^{\prime}}$ (56)

Let $\bar{p}:=\pi_{1\\#}\hat{\gamma}$ (vector of weights). We have
$\bar{p}\leq\hat{p}^{j}$. Combining with (54) and (56), we have

$\displaystyle
C(\hat{\gamma}^{j};\mu^{0},\hat{\mu}^{j},\lambda)-C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda)$
$\displaystyle=C(\gamma^{j};\mu^{0},\gamma^{j}_{1},\lambda)-C(\gamma;\mu^{0},\gamma^{j}_{1},\lambda)+\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}\sum_{k\in
D}(\frac{\bar{p}_{k}-\hat{p}_{k}^{j}}{\hat{p}_{k}^{j}})+\sum_{k^{\prime}=1}^{N_{0}}|\hat{x}_{k}^{j}|^{2}(\hat{p}_{k}^{j}-\bar{p})$
$\displaystyle\leq\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}\sum_{k\in
D}(\frac{\bar{p}_{k}-\hat{p}_{k}^{j}}{\hat{p}_{k}^{j}})+\sum_{k^{\prime}=1}^{N_{0}}|\hat{x}_{k}^{j}|^{2}(\hat{p}_{k}^{j}-\bar{p})$
(57)

where the inequality holds sine $\gamma^{j}$ is optimal for
$OPT_{\lambda}(\mu^{0},\gamma^{j}_{1})$.

Let

$F(\bar{p}):=\sum_{i=1}^{N_{j}}\|x_{i}^{j}\|^{2}\sum_{k\in
D}(\frac{\bar{p}_{k}-\hat{p}_{k}^{j}}{\hat{p}_{k}^{j}})+\sum_{k^{\prime}=1}^{N_{0}}|\hat{x}_{k}^{j}|^{2}(\hat{p}_{k}^{j}-\bar{p})$

Note that if $k\notin D$, then $\bar{p}_{k}=\hat{p}_{k}=0$; and for $k\in D$,
we have

$\displaystyle\frac{\partial}{\partial\bar{p}_{k}}F$
$\displaystyle=\sum_{i:\,\gamma^{j}_{k,i}>0}\|x_{i}^{j}\|^{2}\frac{\gamma_{k,i}^{j}}{\hat{p}_{k}^{j}}-\|\hat{x}^{j}_{k}\|^{2}\geq
0$

where the inequality holds by the fact
$\sum_{i:\,\gamma_{k,i}^{j}>0}\frac{\gamma_{k,i}^{j}}{\hat{p}_{k}^{j}}=1$ and
Jensen’s inequality (in particular,
$\mathbb{E}(\|X\|^{2})\geq\|\mathbb{E}[X]\|^{2}$ for a random vector $X$).
Combining with the fact $F(\bar{p})=0$ when $\bar{p}_{k}$ achieves its maximum
$\hat{p}^{j}_{k}$ for each $k$, we have

$F(\bar{p})\leq 0,\qquad\forall\,0\leq\bar{p}\leq p^{j}.$

Thus $C(\hat{\gamma}^{j};\mu^{0},\hat{\mu}^{j},\lambda)\leq
C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda)$ by (57), and we conclude the
proof. ∎

##  Appendix F Proof of Theorem 3.6

###### Proof.

Without loss of generality, we assume that
$\gamma^{j}\in\Gamma_{\leq}^{*}(\mu^{0},\mu^{j})$ is induced by a 1-1 map. We
can suppose this since the trick is that we will end up with an $N_{0}$-point
representation of $\mu^{j}$ when we get $\hat{\mu}^{j}$. For example, if two
$x_{n}^{0}$ and $x_{m}^{0}$ are mapped to the same point
$T(x_{n}^{0})=T(x_{m}^{0})$, when performing the barycentric, we can split
this into two different labels with corresponding labels. (The moral is that
the labels are important, rather than where the mass is located.) Therefore,
$\gamma^{j}\in\mathbb{R}^{N_{0}\times N_{j}}$ is such that in each row and
column there exists at most one positive entry, and all others are zero. Let
$\hat{\gamma}:=\operatorname{diag}(\hat{p}_{1}^{j},\ldots,\hat{p}_{N_{0}}^{j})$.
Then, by the definition of $\hat{\mu}^{j}$, we have
$C(\gamma^{j};\mu^{0},\mu^{j},\lambda)=C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda)$.
Thus,

$\displaystyle OPT_{\lambda}(\mu^{0},\mu^{j})$
$\displaystyle=C(\gamma^{j};\mu^{0},\mu^{j},\lambda)$
$\displaystyle=C(\gamma^{j};\mu^{0},\gamma^{j},\lambda)+\lambda(|\mu^{j}|-|\gamma_{1}^{j}|)$
$\displaystyle=C(\hat{\gamma};\mu^{0},\hat{\mu}^{j},\lambda)+\lambda(|\mu^{j}|-|\hat{\mu}^{j}|)$
$\displaystyle=OPT_{\lambda}(\mu^{0},\hat{\mu}^{j})+\lambda(|\mu^{j}|-|\hat{\mu}^{j}|),$

where the last equality holds from Theorem 3.5. This concludes the proof.

Moreover, from the above identities (for discrete measure) we can express

$OPT_{\lambda}(\mu^{0},\mu^{j})=\sum_{k=1}^{N_{0}}\hat{p}_{k}\|x_{k}^{0}-\hat{x}_{k}^{j}\|^{2}+\lambda|p^{0}-\hat{p}_{k}^{j}|+\lambda(|p^{j}|-|\hat{p}^{j}|).$

∎

##  Appendix G Proof of Proposition 3.7

###### Proof.

The result follows from (40) and (35). Indeed, we have

$\displaystyle
LOPT_{\lambda,\mu_{0}}(\hat{\mu}^{j},\hat{\mu}^{j})=\|u^{i}-u^{j}\|_{\hat{p}^{i}\wedge\hat{p}^{j},2\lambda}+\lambda(|\hat{p}^{i}-\hat{p}^{j}|)\qquad\text{and}$
$\displaystyle
LOPT_{\lambda,\mu_{0}}(\mu^{j},\mu^{j})=\|u^{i}-u^{j}\|_{\hat{p}^{i}\wedge\hat{p}^{j},2\lambda}+\lambda(|\hat{p}^{i}-\hat{p}^{j}|)+\lambda(|\nu^{i}-\nu^{j}|),$

since the LOPT barycentric projection of $\mu^{i}$ is basically $\mu^{i}$
without the mass that needs to be created from the reference (analogously for
$\mu^{j}$). ∎