Subspace Detours Meet Gromov–Wasserstein

Abstract

In the context of optimal transport (OT) methods, the subspace detour approach was recently proposed by Muzellec and Cuturi. It consists of first finding an optimal plan between the measures projected on a wisely chosen subspace and then completing it in a nearly optimal transport plan on the whole space. The contribution of this paper is to extend this category of methods to the Gromov–Wasserstein problem, which is a particular type of OT distance involving the specific geometry of each distribution. After deriving the associated formalism and properties, we give an experimental illustration on a shape matching problem. We also discuss a specific cost for which we can show connections with the Knothe–Rosenblatt rearrangement.

1. Introduction

Classical optimal transport (OT) has received lots of attention recently, in particular in Machine Learning for tasks such as generative networks [1] or domain adaptation [2] to name a few. It generally relies on the Wasserstein distance, which builds an optimal coupling between distributions given a notion of distance between their samples. Yet, this metric cannot be used directly whenever the distributions lie in different metric spaces and lacks from potentially important properties, such as translation or rotation invariance of the supports of the distributions, which can be useful when comparing shapes or meshes [3,4]. In order to alleviate those problems, custom solutions have been proposed, such as [5], in which invariances are enforced by optimizing over some class of transformations, or [6], in which distributions lying in different spaces are compared by optimizing over the Stiefel manifold to project or embed one of the measures.

Apart from these works, another meaningful OT distance to tackle these problems is the Gromov–Wasserstein (GW) distance, originally proposed in [3,7,8]. It is a distance between metric spaces and has several appealing properties such as geodesics or invariances [8]. Yet, the price to be paid lies in its computational complexity, which requires solving a nonconvex quadratic optimization problem with linear constraints. A recent line of work tends to compute approximations or relaxations of the original problem in order to spread its use in more data-intensive machine learning applications. For example, Peyré et al. [9] rely on entropic regularization and Sinkhorn iterations [10], while recent methods impose coupling with low-rank constraints [11] or rely on a sliced approach [12] or on mini-batch estimators [13] to approximate the Gromov–Wasserstein distance. In Chowdhury et al. [4], the authors propose to partition the space and to solve the optimal transport problem between a subset of points before finding a coupling between all the points.

In this work, we study the subspace detour approach for Gromov–Wasserstein. This class of method was first proposed for the Wasserstein setting in Muzellec and Cuturi [14] and consists of (1) projecting the measures onto a wisely chosen subspace and finding an optimal coupling between them (2) and then constructing a nearly optimal plan of the measures on the whole space using disintegration (see Section 2.2). Our main contribution is to generalize the subspace detours approach on different subspaces and to apply it for the GW distance. We derive some useful properties as well as closed-form solutions of this transport plan between Gaussians distributions. From a practical side, we provide a novel closed-form expression of the one-dimensional GW problem that allows us to efficiently compute the subspace detours transport plan when the subspaces are one-dimensional. Illustrations of the method are given on a shape matching problem where we show good results with a cheaper computational cost compared to other GW-based methods. Interestingly enough, we also propose a separable quadratic cost for the GW problem that can be related with a triangular coupling [15], hence bridging the gap with Knothe–Rosenblatt (KR) rearrangements [16,17].

2. Background

In this section, we introduce all the necessary material to describe the subspace detours approach for classical optimal transport and relate it to the Knothe–Rosenblatt rearrangement. We show how to find couplings via the gluing lemma and measure disintegration. Then, we introduce the Gromov–Wasserstein problem for which we will derive the subspace detour in the next sections.

2.1. Classical Optimal Transport

Let $\mu ,\nu \in \mathcal{P}\left({\mathbb{R}}^d\right)$ be two probability measures. The set of couplings between $\mu$ and $\nu$ is defined as:

$\mathsf{\Pi }(\mu ,\nu )=\{\gamma \in \mathcal{P}({\mathbb{R}}^d\times {\mathbb{R}}^d)|{\pi }_{\#}^1\gamma =\mu ,{\pi }_{\#}^2\gamma =\nu \}$

where ${\pi }^1$ and ${\pi }^2$ are the projections on the first and second coordinate (i.e., ${\pi }^1(x,y)=x$), respectively, and # is the push forward operator, defined such that:

$\forall A\in \mathcal{B}\left({\mathbb{R}}^d\right),T_{\#}\mu \left(A\right)=\mu \left(T^{-1}\left(A\right)\right).$

2.1.1. Kantorovitch Problem

There exists several types of coupling between probability measures for which a non-exhaustive list can be found in [18] (Chapter 1). Among them, the so called optimal coupling is the minimizer of the following Kantorovitch problem:

(1)$\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{inf}\int c(x,y)\mathrm{d}\gamma (x,y)$

with c being some cost function. The Kantorovitch problem (1) is known to admit a solution when c is non-negative and lower semi-continuous [19] (Theorem 1.7). When $c(x,y)={\parallel x-y\parallel }_2^2$, it defines the so-called Wasserstein distance:

(2)$W_2^2(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{inf}\int {\parallel x-y\parallel }_2^2\mathrm{d}\gamma (x,y).$

When the optimal coupling is of the form $\gamma ={(Id,T)}_{\#}\mu$ with T, some deterministic map such that $T_{\#}\mu =\nu$, T is called the Monge map.

In one dimension, with $\mu$ atomless, the solution to (2) is a deterministic coupling of the form [19] (Theorem 2.5):

(3)$T=F_{\nu }^{-1}\circ F_{\mu }$

where $F_{\mu }$ is the cumulative distribution function of $\mu$, and $F_{\nu }^{-1}$ is the quantile function of $\nu$. This map is also known as the increasing rearrangement map.

2.1.2. Knothe–Rosenblatt Rearrangement

Another interesting coupling is the Knothe–Rosenblatt (KR) rearrangement, which takes advantage of the increasing rearrangement in one dimension by iterating over the dimension and using the disintegration of the measures. Concatenating all the increasing rearrangements between the conditional probabilities, the KR rearrangement produces a nondecreasing triangular map (i.e., $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$, for all $x\in {\mathbb{R}}^d$, $T\left(x\right)=(T_1\left(x_1\right),\cdots ,T_j(x_1,\cdots ,x_j),\cdots ,T_d\left(x\right))$, and for all j, $T_j$ is nondecreasing with respect to $x_j$), and a deterministic coupling (i.e., $T_{\#}\mu =\nu$) [18,19,20].

Carlier et al. [21] made a connection between this coupling and optimal transport by showing that it can be obtained as the limit of optimal transport plans for a degenerated cost:

$c_t(x,y)=\sum _{i=1}^d{\lambda }_i\left(t\right){(x_i-y_i)}^2,$

where for all $i\in \{1,\cdots ,d\}$, $t>0$, ${\lambda }_i\left(t\right)>0$, and for all $i\ge 2$, $\frac{{\lambda }_i\left(t\right)}{{\lambda }_{i-1}\left(t\right)}\underset{t\to 0}{\to }0$. This cost can be recast as in [22] as $c_t(x,y)={(x-y)}^T{A}_t(x-y)$, where $A_t=\mathrm{diag}({\lambda }_1\left(t\right),\cdots ,{\lambda }_d\left(t\right))$. This formalizes into the following Theorem:

Theorem 1

([19,21]). Let μ and ν be two absolutely continuous measures on ${\mathbb{R}}^d$, with compact supports. Let ${\gamma }_t$ be an optimal transport plan for the cost $c_t$, let $T_K$ be the Knothe–Rosenblatt map between μ and ν, and ${\gamma }_K={(Id\times T_K)}_{\#}\mu$ the associated transport plan. Then, we have ${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\gamma }_K$. Moreover, if ${\gamma }_t$ are induced by transport maps $T_t$, then $T_t$ converges in $L^2\left(\mu \right)$ when t tends to zero to the Knothe–Rosenblatt rearrangement.

2.2. Subspace Detours and Disintegration

Muzellec and Cuturi [14] proposed another OT problem by optimizing over the couplings which share a measure on a subspace. More precisely, they defined subspace-optimal plans for which the shared measure is the OT plan between projected measures.

Definition 1

(Subspace-Optimal Plans [14] Definition 1). Let $\mu ,\nu \in {\mathcal{P}}_2\left({\mathbb{R}}^d\right)$ and let $E\subset {\mathbb{R}}^d$ be a k-dimensional subspace. Let ${\gamma }_E^{*}$ be an OT plan for the Wasserstein distance between ${\mu }_E={\pi }_{\#}^E\mu$ and ${\nu }_E={\pi }_{\#}^E\nu$ (with ${\pi }^E$ as the orthogonal projection on E). Then, the set of E-optimal plans between μ and ν is defined as ${\mathsf{\Pi }}_E(\mu ,\nu )=\{\gamma \in \mathsf{\Pi }(\mu ,\nu )|{({\pi }^E,{\pi }^E)}_{\#}\gamma ={\gamma }_E^{*}\}$.

In other words, the subspace OT plans are the transport plans of $\mu ,\nu$ that agree on the subspace E with the optimal transport plan ${\gamma }_E^{*}$ on this subspace. To construct such coupling $\gamma \in \mathsf{\Pi }(\mu ,\nu )$, one can rely on the Gluing lemma [18] or use the disintegration of the measure as described in the following section.

2.2.1. Disintegration

Let $(Y,\mathcal{Y})$ and $(Z,\mathcal{Z})$ be measurable spaces, and $(X,\mathcal{X})=(Y\times Z,\mathcal{Y}\otimes \mathcal{Z})$ the product measurable space. Then, for $\mu \in \mathcal{P}\left(X\right)$, we denote ${\mu }_Y={\pi }_{\#}^Y\mu$ and ${\mu }_Z={\pi }_{\#}^Z\mu$ as the marginals, where ${\pi }^Y$ (respectively ${\pi }^Z$) is the projection on Y (respectively Z). Then, a family ${\left(K(y,·)\right)}_{y\in \mathcal{Y}}$ is a disintegration of $\mu$ if for all $y\in Y$, $K(y,·)$ is a measure on Z, for all $A\in \mathcal{Z}$, $K(·,A)$ is measurable and:

$\forall \varphi \in C\left(X\right),{\int }_{Y\times Z}\varphi (y,z)\mathrm{d}\mu (y,z)={\int }_Y{\int }_Z\varphi (y,z)K(y,\mathrm{d}z)\mathrm{d}{\mu }_Y\left(y\right),$

where $C\left(X\right)$ is the set of continuous functions on X. We can note $\mu ={\mu }_Y\otimes K$. K is a probability kernel if for all $y\in Y$, $K(y,Z)=1$. The disintegration of a measure actually corresponds to conditional laws in the context of probabilities. This concept will allow us to obtain measures on the whole space from marginals on subspaces.

In the case where $X={\mathbb{R}}^d$, which is our setting of interest, we have existence and uniqueness of the disintegration (see Box 2.2 of [19] or Chapter 5 of [23] for the more general case).

2.2.2. Coupling on the Whole Space

Let us note ${\mu }_{E^{\perp }|E}$ and ${\nu }_{E^{\perp }|E}$ as the disintegrated measures on the orthogonal spaces (i.e., such that $\mu ={\mu }_E\otimes {\mu }_{E^{\perp }|E}$ and $\nu ={\nu }_E\otimes {\nu }_{E^{\perp }|E}$ (if we have densities, $p(x_E,x_{E^{\perp }})=p_E\left(x_E\right)p_{E^{\perp }|E}\left(x_{E^{\perp }}\right|x_E)$.)). Then, to obtain a transport plan between the two originals measures on the whole space, we can look for another coupling between disintegrated measures ${\mu }_{E^{\perp }|E}$ and ${\nu }_{E^{\perp }|E}$. In particular, two such couplings are proposed in [14], the Monge-Independent (MI) plan:

${\pi }_{\mathrm{MI}}={\gamma }_E^{*}\otimes ({\mu }_{E^{\perp }|E}\otimes {\nu }_{E^{\perp }|E})$

where we take the independent coupling between ${\mu }_{E^{\perp }|E}(x_E,·)$ and ${\nu }_{E^{\perp }|E}(y_E,·)$ for ${\gamma }_E^{*}$ almost every $(x_E,y_E)$, and the Monge-Knothe (MK) plan:

${\pi }_{\mathrm{MK}}={\gamma }_E^{*}\otimes {\gamma }_{E^{\perp }|E}^{*}$

where ${\gamma }_{E^{\perp }|E}^{*}\left((x_E,y_E),·\right)$ is an optimal plan between ${\mu }_{E^{\perp }|E}(x_E,·)$ and ${\nu }_{E^{\perp }|E}(y_E,·)$ for ${\gamma }_E^{*}$ almost every $(x_E,y_E)$. Muzellec and Cuturi [14] observed that MI is more adapted to noisy environments since it only computes the OT plan of the subspace. MK is more suited for applications where we want to prioritize some subspace but where all the directions still contain relevant information [14].

This subspace detour approach can be of much interest following the popular assumption that two distributions on ${\mathbb{R}}^d$ differ only in a low-dimensional subspace as in the Spiked transport model [24]. However, it is still required to find the adequate subspace. Muzellec and Cuturi [14] propose to either rely on a priori knowledge to select the subspace (by using, e.g., a reference dataset and a principal component analysis) or to optimize over the Stiefel manifold.

2.3. Gromov–Wasserstein

Formally, the Gromov–Wasserstein distance allows us to compare metric measure spaces (mm-space), triplets $(X,d_X,{\mu }_X)$ and $(Y,d_Y,{\mu }_Y)$, where $(X,d_X)$ and $(Y,d_Y)$ are complete separable metric spaces and ${\mu }_X$ and ${\mu }_Y$ are Borel probability measures on X and Y [8], respectively, by computing:

$GW(X,Y)=\underset{\gamma \in \mathsf{\Pi }({\mu }_X,{\mu }_Y)}{inf}\int \int L(d_X(x,x^{\prime }),d_Y(y,y^{\prime }))\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })$

where L is some loss on $\mathbb{R}$. It has actually been extended to other spaces by replacing the distances by cost functions $c_X$ and $c_Y$, as, e.g., in [25]. Furthermore, it has many appealing properties such as having invariances (which depend on the costs).

Vayer [26] notably studied this problem in the setting where X and Y are Euclidean spaces, with $L(x,y)={(x-y)}^2$ and $c(x,x^{\prime })=⟨x,x^{\prime }⟩$ or $c(x,x^{\prime })={\parallel x-x^{\prime }\parallel }_2^2$. In particular, let $\mu \in \mathcal{P}\left({\mathbb{R}}^p\right)$ and $\nu \in \mathcal{P}\left({\mathbb{R}}^q\right)$, and the inner-GW problem is defined as:

(4)$\mathrm{InnerGW}(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{inf}\int \int {({⟨x,x^{\prime }⟩}_p-{⟨y,y^{\prime }⟩}_q)}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }).$

For this problem, a closed form in one dimension can be found when one of the distributions admits a density w.r.t. the Lebesgue measure:

Theorem 2

([26] Theorem 4.2.4). Let $\mu ,\nu \in \mathcal{P}\left(\mathbb{R}\right)$, with μ being absolutely continuous with respect to the Lebesgue measure. Let $F_{\mu }^{\nearrow }\left(x\right):=F_{\mu }\left(x\right)=\mu \left(\right]-\infty ,x\left]\right)$ be the cumulative distribution function and $F_{\mu }^{\searrow }\left(x\right)=\mu \left(\right]-x,+\infty \left[\right)$ the anti-cumulative distribution function. Let $T_{asc}\left(x\right)=F_{\nu }^{-1}\left(F_{\mu }^{\nearrow }\left(x\right)\right)$ and $T_{desc}\left(x\right)=F_{\nu }^{-1}\left(F_{\mu }^{\searrow }(-x)\right)$. Then, an optimal solution of (4) is achieved either by $\gamma ={(Id\times T_{asc})}_{\#}\mu$ or by $\gamma ={(Id\times T_{desc})}_{\#}\mu$.

3. Subspace Detours for GW

In this section, we propose to extend subspace detours from Muzellec and Cuturi [14] with Gromov–Wasserstein costs. We show that we can even take subspaces of different dimensions and still obtain a coupling on the whole space using the Independent or the Monge–Knothe coupling. Then, we derive some properties analogously to Muzellec and Cuturi [14], as well as some closed-form solutions between Gaussians. We also provide a new closed-form expression of the inner-GW problem between one-dimensional discrete distributions and provide an illustration on a shape-matching problem.

3.1. Motivations

First, we adapt the definition of subspace optimal plans for different subspaces. Indeed, since the GW distance is adapted to distributions that have their own geometry, we argue that if we project on the same subspace, then it is likely that the resulting coupling would not be coherent with that of GW. To illustrate this point, we use as a source distribution $\mu$ one moon of the two moons dataset and obtain a target $\nu$ by rotating $\mu$ by an angle of $\frac{\pi }{2}$ (see Figure 1). As the GW with $c(x,x^{\prime })={\parallel x-x^{\prime }\parallel }_2^2$ is invariant with respect to isometries, the optimal coupling is diagonal, as recovered on the left side of the figure. However, when choosing one subspace to project both the source and target distributions, we completely lose the optimal coupling between them. Nonetheless, by choosing one subspace for each measure more wisely (using here the first component of the principal component analysis (PCA) decomposition), we recover the diagonal coupling. This simple illustration underlines that the choice of both subspaces is important. A way of choosing the subspaces could be to project on the subspace containing the more information for each dataset using, e.g., PCA independently on each distribution. Muzellec and Cuturi [14] proposed to optimize the optimal transport cost with respect to an orthonormal matrix with a projected gradient descent, which could be extended to an optimization over two orthonormal matrices in our context.

By allowing for different subspaces, we obtain the following definition of subspace optimal plans:

Definition 2.

Let $\mu \in {\mathcal{P}}_2\left({\mathbb{R}}^p\right)$, $\nu \in {\mathcal{P}}_2\left({\mathbb{R}}^q\right)$, E be a k-dimensional subspace of ${\mathbb{R}}^p$ and F a $k^{\prime }$-dimensional subspace of ${\mathbb{R}}^q$. Let ${\gamma }_{E\times F}^{*}$ be an optimal transport plan for $GW$ between ${\mu }_E={\pi }_{\#}^E\mu$ and ${\nu }_F={\pi }_{\#}^F\nu$ (with ${\pi }^E$ (resp. ${\pi }^F$) the orthogonal projection on E (resp. F)). Then, the set of $(E,F)$-optimal plans between μ and ν is defined as ${\mathsf{\Pi }}_{E,F}(\mu ,\nu )=\{\gamma \in \mathsf{\Pi }(\mu ,\nu )|{({\pi }^E,{\pi }^F)}_{\#}\gamma ={\gamma }_{E\times F}^{*}\}$.

Analogously to Muzellec and Cuturi [14] (Section 2.2), we can obtain from ${\gamma }_{E\times F}^{*}$ a coupling on the whole space by either defining the Monge–Independent plan ${\pi }_{\mathrm{MI}}={\gamma }_{E\times F}^{*}\otimes ({\mu }_{E^{\perp }|E}\otimes {\nu }_{F^{\perp }|F})$ or the Monge–Knothe plan ${\pi }_{\mathrm{MK}}={\gamma }_{E\times F}^{*}\otimes {\gamma }_{E^{\perp }\times F^{\perp }|E\times F}^{*}$ where OT plans are taken with some OT cost, e.g., $GW$.

3.2. Properties

Let $E\subset {\mathbb{R}}^p$ and $F\subset {\mathbb{R}}^q$ and denote:

(5)$G{W}_{E,F}(\mu ,\nu )=\underset{\gamma \in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )}{inf}\int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })$

the Gromov–Wasserstein problem restricted to subspace optimal plans (2). In the following, we show that Monge–Knothe couplings are optimal plans of this problem, which is a direct transposition of Proposition 1 in [14].

Proposition 1.

Let $\mu \in \mathcal{P}\left({\mathbb{R}}^p\right)$ and $\nu \in \mathcal{P}\left({\mathbb{R}}^q\right)$, $E\subset {\mathbb{R}}^p$, $F\subset {\mathbb{R}}^q$, ${\pi }_{\mathrm{MK}}={\gamma }_{E\times F}^{*}\otimes {\gamma }_{E^{\perp }\times F^{\perp }|E\times F}^{*}$, where ${\gamma }_{E\times F}^{*}$ is an optimal coupling between ${\mu }_E$ and ${\nu }_F$, and for ${\gamma }_{E\times F}^{*}$, almost every $(x_E,y_F)$, ${\gamma }_{E^{\perp }\times F^{\perp }|E\times F}^{*}\left((x_E,y_F),·\right)$ is an optimal coupling between ${\mu }_{E^{\perp }|E}(x_E,·)$ and ${\nu }_{F^{\perp }|F}(y_F,·)$. Then we have:

${\pi }_{\mathrm{MK}}\in \underset{\gamma \in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )}{argmin}\int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }).$

Proof. 

Let $\gamma \in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )$, then:

$\begin{array}{cc}\hfill & \int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int (\int \int L(x,x^{\prime },y,y^{\prime }){\gamma }_{E^{\perp }\times F^{\perp }|E\times F}\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right)\hfill \\ & {\gamma }_{E^{\perp }\times F^{\perp }|E\times F}\left((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime })\right))\mathrm{d}{\gamma }_{E\times F}^{*}(x_E,y_F)\mathrm{d}{\gamma }_{E\times F}^{*}(x_E^{\prime },y_F^{\prime }).\hfill \end{array}$

However, for ${\gamma }_{E\times F}^{*}$ a.e. $(x_E,y_F),(x_E^{\prime },y_F^{\prime })$,

$\begin{array}{cc}\hfill & \int \int L(x,x^{\prime },y,y^{\prime }){\gamma }_{E^{\perp }\times F^{\perp }|E\times F}\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right){\gamma }_{E^{\perp }\times F^{\perp }|E\times F}\left((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime })\right)\hfill \\ \hfill & \ge \int \int L(x,x^{\prime },y,y^{\prime }){\gamma }_{E^{\perp }\times F^{\perp }|E\times F}^{*}\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right){\gamma }_{E^{\perp }\times F^{\perp }|E\times F}^{*}\left((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime })\right)\hfill \end{array}$

by definition of the Monge–Knothe coupling. By integrating with respect to ${\gamma }_{E\times F}^{*}$, we obtain:

$\int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\ge \int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}{\pi }_{\mathrm{MK}}(x,y)\mathrm{d}{\pi }_{\mathrm{MK}}(x^{\prime },y^{\prime }).$

Therefore, ${\pi }_{\mathrm{MK}}$ is optimal for subspace optimal plans.    □

The key properties of $GW$ that we would like to keep are its invariances. We show in two particular cases that we conserve them on the orthogonal spaces (since the measure on $E\times F$ is fixed).

Proposition 2.

Let $\mu \in \mathcal{P}\left({\mathbb{R}}^p\right)$, $\nu \in \mathcal{P}\left({\mathbb{R}}^q\right)$, $E\subset {\mathbb{R}}^p$, $F\subset {\mathbb{R}}^q$.

For $L(x,x^{\prime },y,y^{\prime })={\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2$ or $L(x,x^{\prime },y,y^{\prime })={\left({⟨x,x^{\prime }⟩}_p-{⟨y,y^{\prime }⟩}_q\right)}^2$, $G{W}_{E,F}$ (5) is invariant with respect to isometries of the form $f=(I{d}_E,f_{E^{\perp }})$ (resp. $g=(I{d}_F,g_{F^{\perp }})$) with $f_{E^{\perp }}$ an isometry on $E^{\perp }$ (resp. $g_{F^{\perp }}$ an isometry on $F^{\perp }$) with respect to the corresponding cost ($c(x,x^{\prime })={\parallel x-x^{\prime }\parallel }_2^2$ or $c(x,x^{\prime })={⟨x,x^{\prime }⟩}_p$).

Proof. 

We propose a sketch of the proof. The full proof can be found in Appendix A.1. Let $L(x,x^{\prime },y,y^{\prime })={\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2$, let $f_{E^{\perp }}$ be an isometry w.r.t $c(x_{E^{\perp }},x_{E^{\perp }}^{\prime })={\parallel x_{E^{\perp }}-x_{E^{\perp }}^{\prime }\parallel }_2^2$, and let $f:{\mathbb{R}}^p\to {\mathbb{R}}^p$ be defined as such for all $x\in {\mathbb{R}}^p$, $f\left(x\right)=(x_E,f_{E^{\perp }}\left(x_{E^{\perp }}\right))$.

By using Lemma 6 of [27], we show that ${\mathsf{\Pi }}_{E,F}(f_{\#}\mu ,\nu )=\left\{{(f,Id)}_{\#}\gamma \right|\gamma \in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )\}$. Hence, for all $\gamma \in {\mathsf{\Pi }}_{E,F}(f_{\#}\mu ,\nu )$, there exists $\tilde{\gamma }\in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )$ such that $\gamma ={(f,Id)}_{\#}\tilde{\gamma }$. By disintegrating $\tilde{\gamma }$ with respect to ${\gamma }_{E\times F}^{*}$ and using the properties of the pushforward, we can show that:

$\begin{array}{cc}\hfill & \int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}{(f,Id)}_{\#}\tilde{\gamma }(x,y)\mathrm{d}{(f,Id)}_{\#}\tilde{\gamma }(x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}\tilde{\gamma }(x,y)\mathrm{d}\tilde{\gamma }(x^{\prime },y^{\prime }).\hfill \end{array}$

Finally, by taking the infimum with respect to $\tilde{\gamma }\in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )$, we find:

$G{W}_{E,F}(f_{\#}\mu ,\nu )=G{W}_{E,F}(\mu ,\nu ).$

   □

3.3. Closed-Form between Gaussians

We can also derive explicit formulas between Gaussians in particular cases. Let $q\le p$, $\mu =\mathcal{N}(m_{\mu },\Sigma )\in \mathcal{P}\left({\mathbb{R}}^p\right)$, $\nu =\mathcal{N}(m_{\nu },\Lambda )\in \mathcal{P}\left({\mathbb{R}}^q\right)$ two Gaussian measures with $\Sigma =P_{\mu }{D}_{\mu }{P}_{\mu }^T$ and $\Lambda =P_{\nu }{D}_{\nu }{P}_{\nu }^T$. As previously, let $E\subset {\mathbb{R}}^p$ and $F\subset {\mathbb{R}}^q$ be k and $k^{\prime }$ dimensional subspaces, respectively. Following Muzellec and Cuturi [14], we represent $\Sigma$ in an orthonormal basis of $E\oplus E^{\perp }$ and $\Lambda$ in an orthonormal basis of $F\oplus F^{\perp }$, i.e., $\Sigma =\left(\begin{array}{cc}{\Sigma }_E& {\Sigma }_{E{E}^{\perp }}\\ {\Sigma }_{E^{\perp }E}& {\Sigma }_{E^{\perp }}\end{array}\right)$. Now, let us denote the following:

$\Sigma /{\Sigma }_E={\Sigma }_{E^{\perp }}-{\Sigma }_{E{E}^{\perp }}^T{\Sigma }_E^{-1}{\Sigma }_{E{E}^{\perp }}$

as the Schur complement of $\Sigma$ with respect to ${\Sigma }_E$. We know that the conditionals of Gaussians are Gaussians and that their covariances are the Schur complements (see, e.g., [28,29]).

For $L(x,x^{\prime },y,y^{\prime })={\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2$, we have for now no certainty that the optimal transport plan is Gaussian. Let ${\mathcal{N}}_{p+q}$ denote the set of Gaussians in ${\mathbb{R}}^{p+q}$. By restricting the minimization problem to Gaussian couplings, i.e., by solving:

(6)$\mathrm{GGW}(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )\cap {\mathcal{N}}_{p+q}}{inf}\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }),$

Salmona et al. [30] showed that there is a solution ${\gamma }^{*}={(Id,T)}_{\#}\mu \in \mathsf{\Pi }(\mu ,\nu )$ with $\mu =\mathcal{N}(m_{\mu },\Sigma )$, $\nu =\mathcal{N}(m_{\nu },\Lambda )$ and

(7)$\forall x\in {\mathbb{R}}^d,T\left(x\right)=m_{\nu }+P_{\nu }A{P}_{\mu }^T(x-m_{\mu })$

where $A=\left(\begin{array}{cc}{\tilde{I}}_q{D}_{\nu }^{\frac{1}{2}}{\left(D_{\mu }^{\left(q\right)}\right)}^{-\frac{1}{2}}& 0_{q,p-q}\end{array}\right)\in {\mathbb{R}}^{q\times p}$, and ${\tilde{I}}_q$ is of the form $\mathrm{diag}\left({(\pm 1)}_{i\le q}\right)$.

By combining the results of Muzellec and Cuturi [14] and Salmona et al. [30], we obtain the following closed-form for Monge–Knothe couplings:

Proposition 3.

Suppose $p\ge q$ and $k=k^{\prime }$. For the Gaussian-restricted GW problem (6), a Monge–Knothe transport map between $\mu =\mathcal{N}(m_{\mu },\Sigma )\in \mathcal{P}\left({\mathbb{R}}^p\right)$ and $\nu =\mathcal{N}(m_{\nu },\Lambda )\in \mathcal{P}\left({\mathbb{R}}^q\right)$ is, for all $x\in {\mathbb{R}}^p$, $T_{\mathrm{MK}}\left(x\right)=m_{\nu }+B(x-m_{\mu })$ where:

$B=\left(\begin{array}{cc}{T}_{E,F}& 0\\ C& T_{E^{\perp },F^{\perp }|E,F}\end{array}\right)$

with $T_{E,F}$ being an optimal transport map between $\mathcal{N}(0_E,{\Sigma }_E)$ and $\mathcal{N}(0_F,{\Lambda }_F)$ (of the form (7)), $T_{E^{\perp },F^{\perp }|E,F}$ an optimal transport map between $\mathcal{N}(0_{E^{\perp }},\Sigma /{\Sigma }_E)$ and $\mathcal{N}(0_{F^{\perp }},\Lambda /{\Lambda }_F)$, and C satisfies:

$C=({\Lambda }_{F^{\perp }F}{(T_{E,F}^T)}^{-1}-T_{E^{\perp },F^{\perp }|E,F}{\Sigma }_{E^{\perp }E}){\Sigma }_E^{-1}.$

Proof. 

See Appendix A.2.1.    □

Suppose that $k\ge k^{\prime }$, $m_{\mu }=0$, and $m_{\nu }=0$ and let $T_{E,F}$ be an optimal transport map between ${\mu }_E$ and ${\nu }_F$ (of the form (7)). We can derive a formula for the Monge–Independent coupling for the inner-GW problem and the Gaussian restricted GW problem.

Proposition 4.

${\pi }_{\mathrm{MI}}=\mathcal{N}(0_{p+q},\Gamma )$ where $\Gamma =\left(\begin{array}{cc}\Sigma & C\\ C^T& \Lambda \end{array}\right)$ with

$C=(V_E{\Sigma }_E+V_{E^{\perp }}{\Sigma }_{E^{\perp }E})T_{E,F}^T(V_F^T+{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T{V}_{F^{\perp }}^T)$

where $T_{E,F}$ is an optimal transport map, either for the inner-GW problem or the Gaussian restricted problem.

Proof. 

See Appendix A.2.2.    □

3.4. Computation of Inner-GW between One-Dimensional Empirical Measures

In practice, computing the Gromov–Wasserstein distance from samples of the distributions is costly. From a computational point of view, the subspace detour approach provides an interesting method with better computational complexity when choosing 1D subspaces. Moreover, we have the intuition than the GW problem between measures lying on smaller dimensional subspaces has a better sample complexity than between the original measures, as it is the case for the Wasserstein distance [31,32].

Below, we show that when both E and F are one-dimensional subspaces, then the resulting GW problem between the projected measures can be solved in linear time. This will rely on a new closed-form expression of the GW problem in 1D. Vayer et al. [12] provided a closed-form for GW with $c(x,x^{\prime })={\parallel x-x^{\prime }\parallel }_2^2$ in one dimension between discrete measures containing the same number of points and with uniform weights. However, in our framework, the 1D projection of $E,F$ may not have uniform weights, and we also would like to be able to compare distributions with different numbers of points. We provide in the next proposition a closed-form expression for the inner-GW problem between any unidimensional discrete probability distributions:

Proposition 5.

Consider ${\Sigma }_n=\{a\in {\mathbb{R}}_{+}^n,{\sum }_{i=1}^n{a}_i=1\}$ the n probability simplex. For a vector $a\in {\mathbb{R}}^n$, we denote $a^{-}$ as the vector with values sorted decreasingly, i.e., $a_1^{-}\ge \cdots \ge a_n^{-}$. Let $\mu ={\sum }_{i=1}^n{a}_i{\delta }_{x_i},\nu ={\sum }_{j=1}^m{b}_j{\delta }_{y_j}\in \mathcal{P}\left(\mathbb{R}\right)\times \mathcal{P}\left(\mathbb{R}\right)$ with $a,b\in {\Sigma }_n\times {\Sigma }_m$. Suppose that $x_1\le \cdots \le x_n$ and $y_1\le \cdots \le y_m$. Consider the problem:

(8) $\underset{\gamma \in \mathsf{\Pi }(a,b)}{min}\sum _{ijkl}{(x_i{x}_k-y_j{y}_l)}^2{\gamma }_{ij}{\gamma }_{kl}$

Then, there exists $\gamma \in \{NW(a,b),NW(a^{-},b)\}$ such that γ is an optimal solution of (8) where $NW$ is the North-West corner rule defined in Algorithm 1. As a corollary, an optimal solution of (8) can be found in $O(n+m)$.

Algorithm 1 North-West corner rule $NW(a,b)$

$a\in {\Sigma }_n,b\in {\Sigma }_m$ while$i<=n$, $j<=m$do    ${\gamma }_{ij}=min\{a_i,b_j\}$    $a_i=a_i-{\gamma }_{ij}$    $b_j=b_j-{\gamma }_{ij}$    If $a_i=0$, $i=i+1$, if $b_j=0$, $j=j+1$ end while return $\gamma \in \mathsf{\Pi }(a,b)$

Proof. 

Let $\gamma \in \mathsf{\Pi }(a,b)$. Then:

$\begin{array}{c}\hfill \sum _{ijkl}{(x_i{x}_k-y_j{y}_l)}^2{\gamma }_{ij}{\gamma }_{kl}=\sum _{ijkl}{\left(x_i{x}_k\right)}^2{\gamma }_{ij}{\gamma }_{kl}+\sum _{ijkl}{\left(y_j{y}_l\right)}^2{\gamma }_{ij}{\gamma }_{kl}-2\sum _{ijkl}{x}_i{x}_k{y}_j{y}_l{\gamma }_{ij}{\gamma }_{kl}\end{array}$

However, ${\sum }_{ijkl}{\left(x_i{x}_k\right)}^2{\gamma }_{ij}{\gamma }_{kl}={\sum }_{ik}{\left(x_i{x}_k\right)}^2{a}_i{a}_k$, and ${\sum }_{ijkl}{\left(y_j{y}_l\right)}^2{\gamma }_{ij}{\gamma }_{kl}={\sum }_{jl}{\left(y_j{y}_l\right)}^2{b}_j{b}_l$, so this does not depend on $\gamma$. Moreover $2{\sum }_{ijkl}{x}_i{x}_k{y}_j{y}_l{\gamma }_{ij}{\gamma }_{kl}=2{\left({\sum }_{ij}{x}_i{y}_j{\gamma }_{ij}\right)}^2$. Hence, the problem (8) is equivalent to ${max}_{\gamma \in \mathsf{\Pi }(a,b)}{\left({\sum }_{ij}{x}_i{y}_j{\gamma }_{ij}\right)}^2$ (in terms of the OT plan), which is also equivalent to solving ${max}_{\gamma \in \mathsf{\Pi }(a,b)}\left|{\sum }_{ij}{x}_i{y}_j{\gamma }_{ij}\right|$ or equivalently:

(9)$\underset{\gamma \in \mathsf{\Pi }(a,b)}{max}\pm 1\sum _{ij}{x}_i{y}_j{\gamma }_{ij}$

We have two cases to consider: If $\pm 1=1$, we have to solve $-{min}_{\gamma \in \mathsf{\Pi }(a,b)}{\sum }_{ij}(-x_i)y_j{\gamma }_{ij}$. Since the points are sorted, the matrix $c_{ij}=-x_i{y}_j$ satisfies the Monge property [33]:

(10)$\forall (i,j)\in \{1,\cdots ,n-1\}\times \{1,\cdots ,m-1\},c_{i,j}+c_{i+1,j+1}\le c_{i+1,j}+c_{i,j+1}$

To see this, check that:

(11)$\begin{array}{cc}\hfill & (-x_i)y_j+(-x_{i+1})y_{j+1}-(-x_{i+1})y_j-(-x_i)y_{j+1}\hfill \\ \hfill & =(-x_i)(y_j-y_{j+1})+(-x_{i+1})(y_{j+1}-y_j)=(y_j-y_{j+1})(x_{i+1}-x_i)\le 0\hfill \end{array}$

In this case, the North-West corner rule $NW(a,b)$ defined in Algorithm 1 is known to produce an optimal solution to the linear problem (9) [33]. If $\pm =-1$, then changing $x_i$ to $-x_i$ concludes. □

We emphasize that this result is novel and generalizes [12] in the sense that the distributions do not need to have uniform weights and the same number of points. I addition, Theorem 2 is not directly applicable to this setting since it requires having absolutely regular distributions, which is not the case here. Both results are, however, related, as the solution obtained by using the NW corner rule on the sorted samples is the same as that obtained by considering the coupling obtained from the quantile functions. The previous result could also be used to define tractable alternatives to GW in the same manner as the Sliced Gromov–Wasserstein [12].

3.5. Illustrations

We use the Python Optimal Transport (POT) library [34] to compute the different optimal transport problems involved in this illustration. We are interested here in solving a 3D mesh registration problem, which is a natural application of Gromov–Wasserstein [3] since it enjoys invariances with respect to isometries such as permutations and can also naturally exploit the topology of the meshes. For this purpose, we selected two base meshes from the Faust dataset [35], which provides ground truth correspondences between shapes. The information available from those meshes are geometrical (6890 vertices positions) and topological (mesh connectivity). These two meshes are represented, along with the visual results of the registration, in Figure 2. In order to visually depict the quality of the assignment induced by the transport map, we propagate through it a color code of the source vertices toward their associated counterpart vertices in the target mesh. Both the original color-coded source and the associated target ground truth are available on the first line of the illustration. To compute our method, we simply use as a natural subspace for both meshes the algebraic connectivity of the mesh’s topological information, also known as the Fiedler vector [36] (eigenvector associated to the second smallest eigenvalue of the un-normalized Laplacian matrix). Fiedler vectors are computed in practice using NetworkX [37] but could also be obtained by using power methods [38]. Reduced to a 1D optimal transport problem (8), we used the Proposition 5 to compute the optimal coupling in $O(n+m)$. Consequently, the computation time is very low ($\sim 5$ secs. on a standard laptop), and the associated matching is very good, with more than $98\%$ of correct assignments. We qualitatively compare this result to Gromov–Wasserstein mappings induced by different cost functions, in the second line of Figure 2: adjacency [39], weighted adjacency (weights are given by distances between vertices), heat kernel (derived from the un-normalized Laplacian) [40], and, finally, geodesic distances over the meshes. On average, computing the Gromov–Wasserstein mapping using POT took around 10 min of time. Both methods based on adjacency fail to recover a meaningful mapping. Heat kernel allows us to map continuous areas of the source mesh but fails in recovering a global structure. Finally, the geodesic distance gives a much more coherent mapping but has inverted left and right of the human figure. Notably, a significant extra computation time was induced by the computation of the geodesic distances ($\sim 1$ h/mesh using the NetworkX [37] shortest path procedure). As a conclusion, and despite the simplification of the original problem, our method performs best with a speed-up of two-orders of magnitude.

4. Triangular Coupling as Limit of Optimal Transport Plans for Quadratic Cost

Another interesting property derived in Muzellec and Cuturi [14] of the Monge–Knothe coupling is that it can be obtained as the limit of classic optimal transport plans, similar to Theorem 1, using a separable cost of the form:

$c_t(x,y)={(x-y)}^T{P}_t(x-y)$

with $P_t=V_E{V}_E^T+t{V}_{E^{\perp }}{V}_{E^{\perp }}^T$ and $(V_E,V_{E^{\perp }})$ as an orthonormal basis of ${\mathbb{R}}^p$.

However, this property is not valid for the classical Gromov–Wasserstein cost (e.g., $L(x,x^{\prime },y,y^{\prime })={(d_X{(x,x^{\prime })}^2-d_Y{(y,y^{\prime })}^2)}^2$ or $L(x,x^{\prime },y,y^{\prime })={({⟨x,x^{\prime }⟩}_p-{⟨y,y^{\prime }⟩}_q)}^2$) as the cost is not separable. Motivated by this question, we ask ourselves in the following if we can derive a quadratic optimal transport cost for which we would have this property.

Formally, we derive a new quadratic optimal transport problem using the Hadamard product. We show that this problem is well-defined and that it has interesting properties such as invariance with respect to axis. We also show that it can be related to a triangular coupling in a similar fashion than the classical optimal transport problem with the Knothe–Rosenblatt rearrangement.

4.1. Construction of the Hadamard–Wasserstein Problem

In this part, we define the “Hadamard–Wasserstein” problem between $\mu \in \mathcal{P}\left({\mathbb{R}}^d\right)$ and $\nu \in \mathcal{P}\left({\mathbb{R}}^d\right)$ as:

(12)${\mathcal{HW}}^2(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{inf}\int \int {\parallel x\odot x^{\prime }-y\odot y^{\prime }\parallel }_2^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }),$

where ⊙ is the Hadamard product (element-wise product). This problem is different than the Gromov–Wasserstein problem in the sense that we do not compare intradistance anymore bur rather the Hadamard products between vectors of the two spaces (in the same fashion as the classical Wasserstein distance). Hence, we need the two measures to belong in the same Euclidean space. Let us note L as the cost defined as:

(13)$\forall x,x^{\prime },y,y^{\prime }\in {\mathbb{R}}^d,L(x,x^{\prime },y,y^{\prime })=\sum _{k=1}^d{(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2={\parallel x\odot x^{\prime }-y\odot y^{\prime }\parallel }_2^2.$

We observe that it coincides with the inner-GW (4) loss in one dimension. Therefore, by Theorem 2, we know that we have a closed-form solution in 1D.

4.2. Properties

First, we derive some useful properties of (12) which are usual for the regular Gromov–Wasserstein problem. Formally, we show that the problem is well defined and that it is a pseudometric with invariances with respect to axes.

Proposition 6.

Let $\mu ,\nu \in \mathcal{P}\left({\mathbb{R}}^d\right)$.

• The problem (12) always admits a minimizer.

• $\mathcal{HW}$ is a pseudometric (i.e., it is symmetric, non-negative, $\mathcal{HW}(\mu ,\mu )=0$, and it satisfies the triangle inequality).

• $\mathcal{HW}$ is invariant to reflection with respect to axes.

Proof. 

Let $\mu ,\nu \in \mathcal{P}\left({\mathbb{R}}^d\right)$,

• $(x,x^{\prime })\mapsto x\odot x^{\prime }$ is a continuous map, therefore, L is less semi-continuous. Hence, by applying Lemma 2.2.1 of [26], we observe that $\gamma \mapsto \int \int L(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })$ is less semi-continuous for the weak convergence of measures.

  Now, as $\mathsf{\Pi }(\mu ,\nu )$ is a compact set (see the proof of Theorem 1.7 in [19] for the Polish space case and of Theorem 1.4 for the compact metric space) and $\gamma \mapsto \int \int L\mathrm{d}\gamma \mathrm{d}\gamma$ is less semi-continuous for the weak convergence, we can apply the Weierstrass theorem (Memo 2.2.1 in [26]), which states that (12) always admits a minimizer.

• See Theorem 16 in [25].

• For invariances, we first look at the properties that must be satisfied by T in order to have: $\forall x,x^{\prime },f(x,x^{\prime })=f(T\left(x\right),T\left(x^{\prime }\right))$ where $f:(x,x^{\prime })\mapsto x\odot x^{\prime }$.

  We find that $\forall x\in {\mathbb{R}}^d{,\forall 1\le i\le d,|\left[T\left(x\right)\right]}_i|=|x_i|$ because, denoting ${\left(e_i\right)}_{i=1}^d$ as the canonical basis, we have:

  $x\odot e_i=T\left(x\right)\odot T\left(e_i\right),$

  which implies that:

  $x_i={\left[T\left(x\right)\right]}_i{\left[T\left(e_i\right)\right]}_i.$

  However, $f(e_i,e_i)=f(T\left(e_i\right),T\left(e_i\right))$ implies ${\left[T\left(e_i\right)\right]}_i^2=1$, and therefore:

  ${|\left[T\left(x\right)\right]}_i|=|x_i|.$

  If we take for T the reflection with respect to axis, then it satisfies $f(x,x^{\prime })=f(T\left(x\right),T\left(x^{\prime }\right))$ well. Moreover, it is a good equivalence relation, and therefore, we have a distance on the quotient space.

□

$\mathcal{HW}$ loses some properties compared to $GW$. Indeed, it is only invariant with respect to axes, and it can only compare measures lying in the same Euclidean space in order for the distance to be well defined. Nonetheless, we show in the following that we can derive some links with triangular couplings in the same way as the Wasserstein distance with KR.

Indeed, the cost L (13) is separable and reduces to the inner-GW loss in 1D, for which we have a closed-form solution. We can therefore define a degenerated version of it:

(14)$\begin{array}{cc}\hfill \forall x,x^{\prime },y,y^{\prime }\in {\mathbb{R}}^d,L_t(x,x^{\prime },y,y^{\prime })& =\sum _{k=1}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\hfill \\ \hfill & ={(x\odot x^{\prime }-y\odot y^{\prime })}^T{A}_t(x\odot x^{\prime }-y\odot y^{\prime })\hfill \end{array}$

with $A_t=\mathrm{diag}(1,{\lambda }_t^{\left(1\right)},{\lambda }_t^{\left(1\right)}{\lambda }_t^{\left(2\right)},\cdots ,{\prod }_{i=1}^{d-1}{\lambda }_t^{\left(i\right)})$, such as for all $t>0$, and for all $i\in \{1,\cdots ,d-1\}$, ${\lambda }_t^{\left(i\right)}>0$, and ${\lambda }_t^{\left(i\right)}\underset{t\to 0}{\to }0$. We denote ${\mathcal{HW}}_t$ the problem (12) with the degenerated cost (14). Therefore, we will be able to decompose the objective as:

$\begin{array}{cc}\hfill & \int \int L_t(x,x^{\prime },y,y^{\prime })\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\hfill \\ & =\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\hfill \end{array}$

and to use the same induction reasoning as [21].

Then, we can define a triangular coupling different from the Knothe–Rosenblatt rearrangement in the sense that each map will not be nondecreasing. Indeed, following Theorem 2, the solution of each 1D problem:

$\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{argmin}\int \int {(x{x}^{\prime }-y{y}^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })$

is either ${(Id\times T_{\mathrm{asc}})}_{\#}\mu$ or ${(Id\times T_{\mathrm{desc}})}_{\#}\mu$. Hence, at each step $k\ge 1$, if we disintegrate the joint law of the k first variables as ${\mu }^{1:k}={\mu }^{1:k-1}\otimes {\mu }^{k|1:k-1}$, the optimal transport map $T(·|x_1,\cdots ,x_{k-1})$ will be the solution of:

$\underset{T\in \{T_{\mathrm{asc}},T_{\mathrm{desc}}\}}{argmin}\int \int {\left(x_k{x}_k^{\prime }-T\left(x_k\right)T\left(x_k^{\prime }\right)\right)}^2{\mu }^{k\mid 1:k-1}(\mathrm{d}{x}_k\mid x_{1:k-1}){\mu }^{k\mid 1:k-1}(\mathrm{d}{x}_k^{\prime }\mid x_{1:k-1}^{\prime }).$

We now state the main theorem, where we show that the limit of the OT plans obtained with the degenerated cost will be the triangular coupling we just defined.

Theorem 3.

Let μ and ν be two absolutely continuous measures on ${\mathbb{R}}^d$ such that ${\int \parallel x\parallel }_2^4\mu \left(\mathrm{d}x\right)<+\infty$, ${\int \parallel y\parallel }_2^4\nu \left(\mathrm{d}y\right)<+\infty$ and with compact support. Let ${\gamma }_t$ be an optimal transport plan for ${\mathcal{HW}}_t$, let $T_K$ be the alternate Knothe–Rosenblatt map between μ and ν as defined in the last paragraph, and let ${\gamma }_K={(Id\times T_K)}_{\#}\mu$ be the associated transport plan. Then, we have ${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\gamma }_K$. Moreover, if ${\gamma }_t$ are induced by transport maps $T_t$, then $T_t\underset{t\to 0}{\overset{L^2\left(\mu \right)}{\to }}{T}_K$.

Proof. 

See Appendix B.2. □

However, we cannot extend this Theorem to the subspace detour approach. Indeed, by choosing $A_t=V_E{V}_E^T+t{V}_{E^{\perp }}{V}_{E^{\perp }}^T$ with $(V_E,V_{E^{\perp }})$ an orthonormal basis of ${\mathbb{R}}^d$, then we project $x\odot x^{\prime }-y\odot y^{\prime }$ on E (respectively on $E^{\perp }$), which is generally different from $x_E\odot x_E^{\prime }-y_E\odot y_E^{\prime }$ (respectively $x_{E^{\perp }}\odot x_{E^{\perp }}^{\prime }-y_{E^{\perp }}\odot y_{E^{\perp }}^{\prime }$).

4.3. Solving Hadamard–Wasserstein in the Discrete Setting

In this part, we derive formulas to solve numerically $\mathcal{HW}$ (12). Let $x_1,\cdots ,x_n\in {\mathbb{R}}^d$, $y_1,\cdots ,y_m\in {\mathbb{R}}^d$, $\alpha \in {\Sigma }_n$, $\beta \in {\Sigma }_m$, $p={\sum }_{i=1}^n{\alpha }_i{\delta }_{x_i}$ and $q={\sum }_{j=1}^m{\beta }_j{\delta }_{y_j}$ two discrete measures in ${\mathbb{R}}^d$. The Hadamard Wasserstein problem (12) becomes in the discrete setting:

$\begin{array}{cc}\hfill {\mathcal{HW}}^2(p,q)& =\underset{\gamma \in \mathsf{\Pi }(p,q)}{inf}\sum _{i,j}\sum _{k,\ell }{\parallel x_i\odot x_k-y_j\odot y_{\ell }\parallel }_2^2{\gamma }_{i,j}{\gamma }_{k,\ell }\hfill \\ \hfill & =\underset{\gamma \in \mathsf{\Pi }(p,q)}{inf}\mathcal{E}\left(\gamma \right)\hfill \end{array}$

with $\mathcal{E}\left(\gamma \right)={\sum }_{i,j}{\sum }_{k,\ell }{\parallel x_i\odot x_k-y_j\odot y_{\ell }\parallel }_2^2{\gamma }_{i,j}{\gamma }_{k,\ell }$. As denoted in [9], if we note:

${\mathcal{L}}_{i,j,k,\ell }={\parallel x_i\odot x_k-y_j\odot y_{\ell }\parallel }_2^2,$

then we have:

$\mathcal{E}\left(\gamma \right)=⟨\mathcal{L}\otimes \gamma ,\gamma ⟩,$

where ⊗ is defined as:

$\mathcal{L}\otimes \gamma ={\left(\sum _{k,\ell }{\mathcal{L}}_{i,j,k,\ell }{\gamma }_{k,\ell }\right)}_{i,j}\in {\mathbb{R}}^{n\times m}.$

We show in the next proposition a decomposition of $\mathcal{L}\otimes \gamma$, which allows us to compute this tensor product more efficiently.

Proposition 7.

Let $\gamma \in \mathsf{\Pi }(p,q)=\{M\in {\left({\mathbb{R}}_{+}\right)}^{n\times m},M{𝟙}_m=p,M^T{𝟙}_n=q\}$, where ${𝟙}_n={(1,\cdots ,1)}^T\in {\mathbb{R}}^n$. Let us note $X={(x_i\odot x_k)}_{i,k}\in {\mathbb{R}}^{n\times n\times d}$, $Y={(y_j\odot y_{\ell })}_{j,\ell }\in {\mathbb{R}}^{m\times m\times d}$, $X^{\left(2\right)}=(\parallel X_{i,k}{{\parallel }_2^2)}_{i,k}\in {\mathbb{R}}^{n\times n}$, $Y^{\left(2\right)}=(\parallel Y_{j,l}{{\parallel }_2^2)}_{j,l}\in {\mathbb{R}}^{m\times m}$, and $\forall t\in \{1,\cdots ,d\},X_t={\left(X_{i,k,t}\right)}_{i,k}\in {\mathbb{R}}^{n\times n}$ and $Y_t={\left(Y_{j,\ell ,t}\right)}_{j,\ell }\in {\mathbb{R}}^{m\times m}$. Then:

$\mathcal{L}\otimes \gamma =X^{\left(2\right)}p{𝟙}_m^T+{𝟙}_n{q}^T{\left(Y^{\left(2\right)}\right)}^T-2\sum _{t=1}^d{X}_t\gamma Y_t^T.$

Proof. 

First, we can start by writing:

$\begin{array}{cc}\hfill {\mathcal{L}}_{i,j,k,\ell }& =\parallel x_i\odot x_k-y_j\odot y_{\ell }{\parallel }_2^2\hfill \\ \hfill & =\parallel X_{i,k}-Y_{j,\ell }{\parallel }_2^2\hfill \\ \hfill & =\parallel X_{i,k}{\parallel }_2^2+{\parallel Y_{j,\ell }\parallel }_2^2-2⟨X_{i,k},Y_{j,\ell }⟩\hfill \\ \hfill & ={[X^{\left(2\right)}]}_{i,k}+{[Y^{\left(2\right)}]}_{j,\ell }-2⟨X_{i,k},Y_{j,\ell }⟩.\hfill \end{array}$

We cannot directly apply proposition 1 from [9] (as the third term is a scalar product), but by performing the same type of computation, we obtain:

$\mathcal{L}\otimes \gamma =A+B+C$

with

$A_{i,j}=\sum _{k,\ell }{[X^{\left(2\right)}]}_{i,k}{\gamma }_{k,\ell }=\sum _k{[X^{\left(2\right)}]}_{i,k}\sum _{\ell }{\gamma }_{k,\ell }=\sum _k{[X^{\left(2\right)}]}_{i,k}{\left[\gamma {𝟙}_m\right]}_{k,1}={[X^{\left(2\right)}\gamma {𝟙}_m]}_{i,1}={[X^{\left(2\right)}p]}_{i,1}$

$B_{i,j}=\sum _{k,\ell }{[Y^{\left(2\right)}]}_{j,\ell }{\gamma }_{k,\ell }=\sum _{\ell }{[Y^{\left(2\right)}]}_{j,\ell }\sum _k{\gamma }_{k,\ell }=\sum _{\ell }{[Y^{\left(2\right)}]}_{j,\ell }{\left[{\gamma }^T{𝟙}_n\right]}_{\ell ,1}={[Y^{\left(2\right)}{\gamma }^T{𝟙}_n]}_{j,1}={[Y^{\left(2\right)}q]}_{j,1}$

and

$\begin{array}{cc}\hfill C_{i,j}=-2\sum _{k,\ell }⟨X_{i,k},Y_{j,\ell }⟩{\gamma }_{k,\ell }& =-2\sum _{k,\ell }\sum _{t=1}^d{X}_{i,k,t}{Y}_{j,\ell ,t}{\gamma }_{k,\ell }\hfill \\ \hfill & =-2\sum _{t=1}^d\sum _k{\left[X_t\right]}_{i,k}\sum _{\ell }{\left[Y_t\right]}_{j,\ell }{\gamma }_{\ell ,k}^T\hfill \\ \hfill & =-2\sum _{t=1}^d\sum _k{\left[X_t\right]}_{i,k}{\left[Y_t{\gamma }^T\right]}_{j,k}\hfill \\ \hfill & =-2\sum _{t=1}^d{\left[X_t{\left(Y_t{\gamma }^T\right)}^T\right]}_{i,j}.\hfill \end{array}$

Finally, we have:

$\mathcal{L}\otimes \gamma =X^{\left(2\right)}p{𝟙}_m^T+{𝟙}_n{q}^T{\left(Y^{\left(2\right)}\right)}^T-2\sum _{t=1}^d{X}_t\gamma Y_t^T.$

□

From this decomposition, we can compute the tensor product $\mathcal{L}\otimes \gamma$ with a complexity of $O\left(d(n^{2}m+m^{2}n)\right)$ using only multiplications of matrices (instead of $O\left(d{n}^2{m}^2\right)$ for a naive computation).

Remark 1.

For the degenerated cost function (14), we just need to replace X and Y by $\widetilde{X_t}=A_t^{\frac{1}{2}}X$ and $\widetilde{Y_t}=A_t^{\frac{1}{2}}Y$ in the previous proposition.

To solve this problem numerically, we can use the conditional gradient algorithm (Algorithm 2 in [41]). This algorithm only requires to compute the gradient:

$\nabla \mathcal{E}\left(\gamma \right)=2(A+B+C)=2(\mathcal{L}\otimes \gamma )$

at each step and a classical OT problem. This algorithm is more efficient than solving the quadratic problem directly. Moreover, while it is a non-convex problem, it actually converges to a local stationary point [42].

On Figure 3, we generated 30 points of 2 Gaussian distributions, and computed the optimal coupling of ${\mathcal{HW}}_t$ for several t. These points have the same uniform weight. We plot the couplings between the points on the second row, and between the projected points on their first coordinate on the first row. Note that for discrete points, the Knothe–Rosenblatt coupling amounts to sorting the points with respect to the first coordinate if there is no ambiguity (i.e., $x_1^{\left(1\right)}<\cdots <x_n^{\left(1\right)}$) as it comes back to perform the optimal transport in one dimension [43] (Remark 2.28). For our cost, the optimal coupling in 1D can either be the increasing or the decreasing rearrangement. We observe on the first row of Figure 3 that the optimal coupling when t is close to 0 corresponds to the decreasing rearrangement, which corresponds well to the alternate Knothe–Rosenblatt map we defined in Section 4.2. It underlines the results provided in Theorem 3.

5. Discussion

We proposed in this work to extend the subspace detour approach to different subspaces, and to other optimal transport costs such as Gromov–Wasserstein. Being able to project on different subspaces can be useful when the data are not aligned and do not share the same axes of interest, as well as when we are working between different metric spaces as it is the case, for example, with graphs. However, a question that arises is how to choose these subspaces. Since the method is mostly interesting when we choose one-dimensional subspaces, we proposed to use a PCA and to project on the first directions for data embedded in Euclidean spaces. For more complicated data such as graphs, we projected onto the Fiedler vector and obtained good results in an efficient way on a 3D mesh registration problem. More generally, Muzellec and Cuturi [14] proposed to perform a gradient descent on the loss with respect to orthonormal matrices. This approach is non-convex and is only guaranteed to converge to a local minimum. Designing such an algorithm, which would minimize alternatively between two transformations in the Stiefel manifold, is left for future works.

The subspace detour approach for transport problem is meaningful whenever one can identify subspaces that gather most of the information from the original distributions, while making the estimate more robust and with a better sample complexity as far as dimensions are lower. On the computational complexity side, and when we have only access to discrete data, the subspace detour approach brings better computational complexity solely when the subspaces are chosen as one dimensional. Indeed, otherwise, we have the same complexity for solving the subspace detour and solving the OT problem directly (since the complexity only depends on the number of samples). In this case, the 1D projection often gives distinct values for all the samples (for continuous valued data) and hence the Monge–Knothe coupling is exactly the coupling in 1D. As such, information is lost on the orthogonal spaces. It can be artificially recovered by quantizing the 1D values (as experimented in practice in [14]), but the added value is not clear and deserves broader studies. If given absolutely continuous distributions wrt. the Lebesgue measure, however, this limit does not exist but comes with the extra cost of being able to compute efficiently the projected measure onto the subspace, which might require discretization of the space and is therefore not practical in high dimensions.

We also proposed a new quadratic cost $\mathcal{HW}$ that we call Hadamard–Wasserstein, which allows us to define a degenerated cost for which the optimal transport plan converges to a triangular coupling. However, this cost loses many properties compared to $W_2$ or $GW$, for which we are inclined to use these problems. Indeed, while $\mathcal{HW}$ is a quadratic cost, it uses a Euclidean norm between the Hadamard product of vectors and requires the two spaces to be the same (in order to have the distance well defined). A work around in the case $X={\mathbb{R}}^p$ and $Y={\mathbb{R}}^q$ with $p\le q$ would be to “lift” the vectors in ${\mathbb{R}}^p$ into vectors in ${\mathbb{R}}^q$ with padding as it is proposed in [12] or to project the vectors in ${\mathbb{R}}^q$ on ${\mathbb{R}}^p$ as in [6]. Yet, for some applications where only the distance/similarity matrices are available, a different strategy still needs to be found. Another concern is the limited invariance properties (only with respect to axial symmetry symmetry in our case). Nevertheless, we expect that such a cost can be of interest in cases where invariance to symmetry is a desired property, such as in [44].

Author Contributions

Methodology, C.B., N.C., T.V., F.S., and L.D.; software, C.B. and N.C.; writing—original draft, C.B., N.C., T.V., F.S., and L.D. All authors have read and agreed to the published version of the manuscript.

Funding

This research wad funded by project DynaLearn from Labex CominLabs and Région Bretagne ARED DLearnMe. N.C. acknowledges fundings from the ANR OTTOPIA AI chair (ANR-20-CHIA-0030). T.V. was supported in part by the AllegroAssai ANR project (ANR-19-CHIA-0009) and by the ACADEMICS grant of the IDEXLYON, project of the Université de Lyon, PIA operated by ANR-16-IDEX-0005.

Data Availability Statement

The FAUST dataset might be found at http://faust.is.tue.mpg.de (accessed in 1 September 2021).

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

OT	Optimal Transport
GW	Gromov–Wasserstein
KR	Knothe–Rosenblatt
MI	Monge–Independent
MK	Monge–Knothe
PCA	Principal Component Analysis
POT	Python Optimal Transport

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures

Figure 1. From left to right: Data (moons); OT plan obtained with GW for [Forumla omitted. See PDF.]; Data projected on the first axis; OT plan obtained between the projected measures; Data projected on their first PCA component; OT plan obtained between the the projected measures.

Figure 2. Three-dimensional mesh registration. (First row) source and target meshes, color code of the source, ground truth color code on the target, result of subspace detour using Fiedler vectors as subspace. (Second row) After recalling the expected ground truth for ease of comparison, we present results of different Gromov–Wasserstein mappings obtained with metrics based on adjacency, heat kernel, and geodesic distances.

Figure 3. Degenerated coupling. On the first row, the points are projected on their first coordinate and we plot the optimal coupling. On the second row, we plot the optimal coupling between the original points.

Appendix A. Subspace Detours

Appendix A.1. Proofs

Proof of Proposition 2. 

We first deal with $$L(x,x^{\prime },y,y^{\prime })={\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2$$. Let $$f_{E^{\perp }}$$ be an isometry w.r.t $$c(x_{E^{\perp }},x_{E^{\perp }}^{\prime })={\parallel x_{E^{\perp }}-x_{E^{\perp }}^{\prime }\parallel }_2^2$$, and let $$f:{\mathbb{R}}^p\to {\mathbb{R}}^p$$ be defined such as for all $$x\in {\mathbb{R}}^p$$, $$f\left(x\right)=(x_E,f_{E^{\perp }}\left(x_{E^{\perp }}\right))$$.

From Lemma 6 of Paty and Cuturi [27], we know that $$\mathsf{\Pi }(f_{\#}\mu ,\nu )=\left\{{(f,Id)}_{\#}\gamma \right|\gamma \in \mathsf{\Pi }(\mu ,\nu )\}$$. We can rewrite: $$\begin{array}{cc}\hfill {\mathsf{\Pi }}_{E,F}(f_{\#}\mu ,\nu )& =\{\gamma \in \mathsf{\Pi }(f_{\#}\mu ,\nu )|{({\pi }^E,{\pi }^F)}_{\#}\gamma ={\gamma }_{E\times F}^{*}\}\hfill \\ \hfill & =\left\{{(f,Id)}_{\#}\gamma \right|\gamma \in \mathsf{\Pi }(\mu ,\nu ),{({\pi }^E,{\pi }^F)}_{\#}{(f,Id)}_{\#}\gamma ={\gamma }_{E\times F}^{*}\}\hfill \\ \hfill & =\left\{{(f,Id)}_{\#}\gamma \right|\gamma \in \mathsf{\Pi }(\mu ,\nu ),{({\pi }^E,{\pi }^F)}_{\#}\gamma ={\gamma }_{E\times F}^{*}\}\hfill \\ \hfill & =\left\{{(f,Id)}_{\#}\gamma \right|\gamma \in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )\}\hfill \end{array}$$ using $$f=(I{d}_E,f_{E^{\perp }})$$, $${\pi }^E\circ f=I{d}_E$$ and $${({\pi }^E,{\pi }^F)}_{\#}{(f,Id)}_{\#}\gamma ={({\pi }^E,{\pi }^F)}_{\#}\gamma$$.

Now, for all $$\gamma \in {\mathsf{\Pi }}_{E,F}(f_{\#}\mu ,\nu )$$, there exists $$\tilde{\gamma }\in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )$$ such that $$\gamma ={(f,Id)}_{\#}\tilde{\gamma }$$, and we can disintegrate $$\tilde{\gamma }$$ with respect to $${\gamma }_{E\times F}^{*}$$: $$\tilde{\gamma }={\gamma }_{E\times F}^{*}\otimes K$$ with K a probability kernel on $$(E\times F,\mathcal{B}\left(E^{\perp }\right)\otimes \mathcal{B}\left(F^{\perp }\right))$$.

For $${\gamma }_{E\times F}^{*}$$ almost every $$(x_E,y_F),(x_E^{\prime },y_F^{\prime })$$, we have: $$\begin{array}{cc}\hfill & \int \int {\left(\parallel x_E-x_E^{\prime }{\parallel }_2^2+\parallel x_{E^{\perp }}-x_{E^{\perp }}^{\prime }{\parallel }_2^2-\parallel y_F-y_F^{\prime }{\parallel }_2^2-{\parallel y_{F^{\perp }}-y_{F^{\perp }}^{\prime }\parallel }_2^2\right)}^2\hfill \\ \hfill & {(f_{E^{\perp }},Id)}_{\#}K((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})){(f_{E^{\perp }},Id)}_{\#}K((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime }))\hfill \\ \hfill & =\int \int {\left(\parallel x_E-x_E^{\prime }{\parallel }_2^2+\parallel f_{E^{\perp }}\left(x_{E^{\perp }}\right)-f_{E^{\perp }}\left(x_{E^{\perp }}^{\prime }\right){\parallel }_2^2-\parallel y_F-y_F^{\prime }{\parallel }_2^2-{\parallel y_{F^{\perp }}-y_{F^{\perp }}^{\prime }\parallel }_2^2\right)}^2\hfill \\ \hfill & K((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }}))K((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime }))\hfill \\ \hfill & =\int \int {\left(\parallel x_E-x_E^{\prime }{\parallel }_2^2+\parallel x_{E^{\perp }}-x_{E^{\perp }}^{\prime }{\parallel }_2^2-\parallel y_F-y_F^{\prime }{\parallel }_2^2-{\parallel y_{F^{\perp }}-y_{F^{\perp }}^{\prime }\parallel }_2^2\right)}^2\hfill \\ \hfill & K((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }}))K((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime }))\hfill \end{array}$$ using in the last line that $$\parallel f_{E^{\perp }}\left(x_{E^{\perp }}\right)-f_{E^{\perp }}\left(x_{E^{\perp }}^{\prime }\right){\parallel }_2={\parallel x_{E^{\perp }}-x_{E^{\perp }}^{\prime }\parallel }_2$$ since $$f_{E^{\perp }}$$ is an isometry.

By integrating with respect to $${\gamma }_{E\times F}^{*}$$, we obtain: (A1)$$\begin{array}{cc}\hfill & \int \int (\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\hfill \\ \hfill & {(f_{E^{\perp }},Id)}_{\#}K((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})){(f_{E^{\perp }},Id)}_{\#}K((x_E^{\prime },y_F^{\prime }),(\mathrm{d}{x}_{E^{\perp }}^{\prime },\mathrm{d}{y}_{F^{\perp }}^{\prime })))\hfill \\ & \mathrm{d}{\gamma }_{E\times F}^{*}(x_E,y_F)\mathrm{d}{\gamma }_{E\times F}^{*}(x_E^{\prime },y_F^{\prime })\hfill \\ \hfill & =\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}\tilde{\gamma }(x,y)\mathrm{d}\tilde{\gamma }(x^{\prime },y^{\prime }).\hfill \end{array}$$

Now, we show that $$\gamma ={(f,Id)}_{\#}\tilde{\gamma }={\gamma }_{E\times F}^{*}\otimes {(f_{E^{\perp }},Id)}_{\#}K$$. Let $$\varphi$$ be some bounded measurable function on $${\mathbb{R}}^p\times {\mathbb{R}}^q$$: $$\begin{array}{cc}\hfill \int \varphi (x,y)\mathrm{d}\gamma (x,y)& =\int \varphi (x,y)\mathrm{d}\left({(f,Id)}_{\#}\tilde{\gamma }(x,y)\right)\hfill \\ \hfill & =\int \varphi (f\left(x\right),y)\mathrm{d}\tilde{\gamma }(x,y)\hfill \\ \hfill & =\int \int \varphi (f\left(x\right),y)K\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right)\mathrm{d}{\gamma }_{E\times F}^{*}(x_E,y_F)\hfill \\ \hfill & =\int \int \varphi ((x_E,f_{E^{\perp }}\left(x_{E^{\perp }}\right)),y)K\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right)\mathrm{d}{\gamma }_{E\times F}^{*}(x_E,y_F)\hfill \\ \hfill & =\int \int \varphi (x,y){(f_{E^{\perp }},Id)}_{\#}K\left((x_E,y_F),(\mathrm{d}{x}_{E^{\perp }},\mathrm{d}{y}_{F^{\perp }})\right)\mathrm{d}{\gamma }_{E\times F}^{*}(x_E,y_F).\hfill \end{array}$$ Hence, we can rewrite (A1) as: $$\begin{array}{cc}\hfill & \int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}{(f,Id)}_{\#}\tilde{\gamma }(x,y)\mathrm{d}{(f,Id)}_{\#}\tilde{\gamma }(x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}\tilde{\gamma }(x,y)\mathrm{d}\tilde{\gamma }(x^{\prime },y^{\prime }).\hfill \end{array}$$

Now, by taking the infimum with respect to $$\tilde{\gamma }\in {\mathsf{\Pi }}_{E,F}(\mu ,\nu )$$, we find: $$G{W}_{E,F}(f_{\#}\mu ,\nu )=G{W}_{E,F}(\mu ,\nu ).$$

For the inner product case, we can do the same proof for linear isometries on $$E^{\perp }$$. □

Appendix A.2. Closed-Form between Gaussians

Let $$q\le p$$, $$\mu =\mathcal{N}(m_{\mu },\Sigma )\in \mathcal{P}\left({\mathbb{R}}^p\right)$$, and $$\nu =\mathcal{N}(m_{\nu },\Lambda )\in \mathcal{P}\left({\mathbb{R}}^q\right)$$ be two Gaussian measures with $$\Sigma =P_{\mu }{D}_{\mu }{P}_{\mu }^T$$ and $$\Lambda =P_{\nu }{D}_{\nu }{P}_{\nu }^T$$.

Let $$E\subset {\mathbb{R}}^p$$ be a subspace of dimension k and $$F\subset {\mathbb{R}}^q$$ a subspace of dimension $$k^{\prime }$$.

We represent $$\Sigma$$ in an orthonormal basis of $$E\oplus E^{\perp }$$ and $$\Lambda$$ in an orthonormal basis of $$F\oplus F^{\perp }$$, i.e., $$\Sigma =\left(\begin{array}{cc}{\Sigma }_E& {\Sigma }_{E{E}^{\perp }}\\ {\Sigma }_{E^{\perp }E}& {\Sigma }_{E^{\perp }}\end{array}\right)$$. We denote $$\Sigma /{\Sigma }_E={\Sigma }_{E^{\perp }}-{\Sigma }_{E{E}^{\perp }}^T{\Sigma }_E^{-1}{\Sigma }_{E{E}^{\perp }}$$ as the Schur complement of $$\Sigma$$ with respect to $${\Sigma }_E$$. We know that the conditionals of Gaussians are Gaussians and of covariance, the Schur complement (see e.g., Rasmussen [28] or Von Mises [29]).

Appendix A.2.1. Quadratic GW Problem

For $$GW$$ with $$c(x,x^{\prime })={\parallel x-x^{\prime }\parallel }_2^2$$, we have for now no guarantee that there exists an optimal coupling which is a transport map. Salmona et al. [30] proposed to restrict the problem to the set of Gaussian couplings $$\pi (\mu ,\nu )\cap {\mathcal{N}}_{p+q}$$ where $${\mathcal{N}}_{p+q}$$ denotes the set of Gaussians in $${\mathbb{R}}^{p+q}$$. In that case, the problem becomes:(A2)$$GGW(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )\cap {\mathcal{N}}_{p+q}}{inf}\int \int {\left(\parallel x-x^{\prime }{\parallel }_2^2-{\parallel y-y^{\prime }\parallel }_2^2\right)}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }).$$

In that case, they showed that an optimal solution is of the form $$T\left(x\right)=m_{\nu }+P_{\nu }A{P}_{\mu }^T(x-m_{\mu })$$ with $$A=\left(\begin{array}{cc}{\tilde{I}}_q{D}_{\nu }^{\frac{1}{2}}{\left(D_{\mu }^{\left(q\right)}\right)}^{-\frac{1}{2}}& 0_{q,p-q}\end{array}\right)$$ and $${\tilde{I}}_q$$ of the form $$\mathrm{diag}\left({(\pm 1)}_{i\le q}\right)$$.

Since the problem is translation invariant, we can always solve the problem between the centered measures.

In the following, we suppose that $$k=k^{\prime }$$. Let us denote $$T_{E,F}$$ as the optimal transport map for (A2) between $$\mathcal{N}(0,{\Sigma }_E)$$ and $$\mathcal{N}(0,{\Lambda }_F)$$. According to Theorem 4.1 in Salmona et al. [30], such a solution exists and is of the form (7). We also denote $$T_{E^{\perp },F^{\perp }}$$ as the optimal transport map between $$\mathcal{N}(0,\Sigma /{\Sigma }_E)$$ and $$\mathcal{N}(0,\Lambda /{\Lambda }_F)$$ (which is well defined since we assumed $$p\ge q$$ and hence $$p-k\ge q-k^{\prime }$$ since $$k=k^{\prime }$$).

We know that the Monge–Knothe transport map will be a linear map $$T_{\mathrm{MK}}\left(x\right)=Bx$$ with B a block triangular matrix of the form:$$B=\left(\begin{array}{cc}{T}_{E,F}& 0_{k^{\prime },p-k}\\ C& T_{E^{\perp },F^{\perp }}\end{array}\right)\in {\mathbb{R}}^{q\times p},$$ with $$C\in {\mathbb{R}}^{(q-k^{\prime })\times k}$$ and such that $$B\Sigma B^T=\Lambda$$ (to have well a transport map between $$\mu$$ and $$\nu$$).

Actually, $$B\Sigma B^T=\left(\begin{array}{cc}{T}_{E,F}{\Sigma }_E{T}_{E,F}^T& T_{E,F}{\Sigma }_E{C}^T+T_{E,F}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T\\ (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})T_{E,F}^T& (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})C^T+(C{\Sigma }_{E{E}^{\perp }}+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }})T_{E^{\perp },F^{\perp }}^T\end{array}\right).$$

First, we have well $$T_{E,F}{\Sigma }_E{T}_{E,F}^T={\Lambda }_F$$, as $$T_{E,F}$$ is a transport map between $${\mu }_E$$ and $${\nu }_F$$. Then:$$B\Sigma B^T=\Lambda \iff \left\{\begin{array}{c}{T}_{E,F}{\Sigma }_E{T}_{E,F}^T={\Lambda }_F\hfill \\ T_{E,F}{\Sigma }_E{C}^T+T_{E,F}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T={\Lambda }_{F{F}^{\perp }}\hfill \\ (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})T_{E,F}^T={\Lambda }_{F^{\perp }F}\hfill \\ (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})C^T+(C{\Sigma }_{E{E}^{\perp }}+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }})T_{E^{\perp },F^{\perp }}^T={\Lambda }_{F^{\perp }}.\hfill \end{array}\right.$$

We have:$$(C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})T_{E,F}^T={\Lambda }_{F^{\perp }F}\iff C{\Sigma }_E{T}_{E,F}^T={\Lambda }_{F^{\perp }F}-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{T}_{E,F}^T.$$

As $$k=k^{\prime }$$, $${\Sigma }_E{T}_{E,F}^T\in {\mathbb{R}}^{k\times k}$$ and is invertible (as $${\Sigma }_E$$ and $${\Lambda }_F$$ are positive definite and $$T_{E,F}=P_{{\mu }_E}{A}_{E,F}{P}_{{\nu }_F}$$ with $$A_{E,F}=\left(\begin{array}{c}{\tilde{I}}_k{D}_{{\nu }_F}^{\frac{1}{1}}{D}_{{\mu }_E}^{-\frac{1}{2}}\end{array}\right)$$ with positive values on the diagonals. Hence, we have:$$C=({\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}){\Sigma }_E^{-1}.$$

Now, we still have to check the last two equations. First:$$\begin{array}{cc}\hfill T_{E,F}{\Sigma }_E{C}^T+T_{E,F}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T& =T_{E,F}{\Sigma }_E{\Sigma }_E^{-1}{T}_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T-T_{E,F}{\Sigma }_E{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T+T_{E,F}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & ={\Lambda }_{F{F}^{\perp }}.\hfill \end{array}$$

For the last equation:$$\begin{array}{cc}\hfill & (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})C^T+(C{\Sigma }_{E{E}^{\perp }}+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }})T_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & =({\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}){\Sigma }_E^{-1}(T_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T-{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T)\hfill \\ \hfill & +{\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }}{T}_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & ={\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{T}_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T-{\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{T}_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T\hfill \\ \hfill & +T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{T}_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp }{F}^{\perp }}^T\hfill \\ \hfill & +{\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{\Sigma }_{E{E}^{\perp }}{T}_{E^{\perp },F^{\perp }}^T-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }}{T}_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & ={\Lambda }_{F^{\perp }F}{\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{T}_{E,F}^{-1}{\Lambda }_{F^{\perp }F}^T-T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T{T}_{E^{\perp },F^{\perp }}^T+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }}{T}_{E^{\perp },F^{\perp }}^T\hfill \end{array}$$ Now, using that $${\left(T_{E,F}^T\right)}^{-1}{\Sigma }_E^{-1}{T}_{E,F}^{-1}={\left(T_{E,F}{\Sigma }_E{T}_{E,F}^T\right)}^{-1}={\Lambda }_F^{-1}$$ and $${\Sigma }_{E^{\perp }}-{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T=\Sigma /{\Sigma }_E$$, we have:$$\begin{array}{cc}\hfill & (C{\Sigma }_E+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }E})C^T+(C{\Sigma }_{E{E}^{\perp }}+T_{E^{\perp },F^{\perp }}{\Sigma }_{E^{\perp }})T_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & ={\Lambda }_{F^{\perp }F}{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T+T_{E^{\perp },F^{\perp }}({\Sigma }_{E^{\perp }}-{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{\Sigma }_{E^{\perp }E}^T)T_{E^{\perp },F^{\perp }}^T\hfill \\ \hfill & ={\Lambda }_{F^{\perp }F}{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T+\Lambda /{\Lambda }_F\hfill \\ \hfill & ={\Lambda }_{F^{\perp }}\hfill \end{array}$$

Then, $${\pi }_{\mathrm{MK}}$$ is of the form $${(Id,T_{\mathrm{MK}})}_{\#}\mu$$ with:$$T_{\mathrm{MK}}\left(x\right)=m_{\nu }+B(x-m_{\mu }).$$

Appendix A.2.2. Closed-Form between Gaussians for Monge–Independent

Suppose is $$k\ge k^{\prime }$$ in order to be able to define the OT map between $${\mu }_E$$ and $${\nu }_F$$.

For the Monge–Independent plan, $${\pi }_{\mathrm{MI}}={\gamma }_{E\times F}^{*}\otimes ({\mu }_{E^{\perp }|E}\otimes {\nu }_{F^{\perp }|F})$$, let $$(X,Y)\sim {\pi }_{\mathrm{MI}}$$. We know that $${\pi }_{\mathrm{MI}}$$ is a degenerate Gaussian with a covariance of the form:$$\mathrm{Cov}(X,Y)=\left(\begin{array}{cc}\mathrm{Cov}\left(X\right)& C\\ C^T& \mathrm{Cov}\left(Y\right)\end{array}\right)$$ where $$\mathrm{Cov}\left(X\right)=\Sigma$$ and $$\mathrm{Cov}\left(Y\right)=\Lambda$$. Moreover, we know that C is of the form:$$\left(\begin{array}{cc}\mathrm{Cov}(X_E,Y_F)& \mathrm{Cov}(X_E,Y_{F^{\perp }})\\ \mathrm{Cov}(X_{E^{\perp }},Y_F)& \mathrm{Cov}(X_{E^{\perp }},Y_{F^{\perp }})\end{array}\right).$$

Let us assume that $$m_{\mu }=m_{\nu }=0$$, then:$$\begin{array}{cc}\hfill \mathrm{Cov}(X_E,Y_F)& =\mathrm{Cov}(X_E,T_{E,F}{X}_E)=\mathbb{E}\left[X_E{X}_E^T\right]T_{E,F}^T={\Sigma }_E{T}_{E,F}^T,\hfill \end{array}$$ $$\begin{array}{cc}\hfill \mathrm{Cov}(X_E,Y_{F^{\perp }})& =\mathbb{E}\left[X_E{Y}_{F^{\perp }}^T\right]\hfill \\ \hfill & =\mathbb{E}\left[\mathbb{E}\left[X_E{Y}_{F^{\perp }}^T\right|X_E,Y_F]\right]\hfill \\ \hfill & =\mathbb{E}\left[X_E\mathbb{E}\left[Y_{F^{\perp }}^T\right|Y_F]\right]\hfill \end{array}$$ since $$Y_F=T_{E,F}{X}_E$$, $$X_E$$ is $$\sigma \left(Y_F\right)$$-measurable. Now, using the equation (A.6) from Rasmussen [28], we have:$$\begin{array}{cc}\hfill \mathbb{E}\left[Y_{F^{\perp }}\right|Y_F]& ={\Lambda }_{F^{\perp }F}{\Lambda }_F^{-1}{Y}_F\hfill \\ \hfill & ={\Lambda }_{F^{\perp }F}{\Lambda }_F^{-1}{T}_{E,F}{X}_E\hfill \end{array}$$ and $$\mathbb{E}\left[X_{E^{\perp }}\right|X_E]={\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{X}_E.$$

Hence:$$\begin{array}{cc}\hfill \mathrm{Cov}(X_E,Y_{F^{\perp }})& =\mathbb{E}\left[X_E\mathbb{E}\left[Y_{F^{\perp }}^T\right|Y_F]\right]\hfill \\ \hfill & =\mathbb{E}\left[X_E{X}_E^T\right]T_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T\hfill \\ \hfill & ={\Sigma }_E{T}_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T.\hfill \end{array}$$

We also have:$$\mathrm{Cov}(X_{E^{\perp }},Y_F)=\mathbb{E}\left[X_{E^{\perp }}{X}_E^T{T}_{E,F}^T\right]={\Sigma }_{E^{\perp }E}{T}_{E,F}^T,$$ and $$\begin{array}{cc}\hfill \mathrm{Cov}(X_{E^{\perp }},Y_{F^{\perp }})& =\mathbb{E}\left[X_{E^{\perp }}{Y}_{F^{\perp }}^T\right]\hfill \\ \hfill & =\mathbb{E}\left[\mathbb{E}\left[X_{E^{\perp }}{Y}_{F^{\perp }}^T\right|X_E,Y_F]\right]\hfill \\ \hfill & =\mathbb{E}\left[\mathbb{E}\left[X_{E^{\perp }}\right|X_E]\mathbb{E}\left[Y_{F^{\perp }}^T\right|Y_F]\right]\mathrm{by}\mathrm{independence}\hfill \\ \hfill & =\mathbb{E}\left[{\Sigma }_{E^{\perp }E}{\Sigma }_E^{-1}{X}_E{X}_E^T{T}_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T\right]\hfill \\ \hfill & ={\Sigma }_{E^{\perp }E}{T}_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T.\hfill \end{array}$$

Finally, we find:$$C=\left(\begin{array}{cc}{\Sigma }_E{T}_{E,F}^T& {\Sigma }_E{T}_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T\\ {\Sigma }_{E^{\perp }E}{T}_{E,F}^T& {\Sigma }_{E^{\perp }E}{T}_{E,F}^T{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T\end{array}\right).$$

By taking orthogonal bases $$(V_E,V_{E^{\perp }})$$ and $$(V_F,V_{F^{\perp }})$$, we can put it in a more compact way, such as in Proposition 4 in Muzellec and Cuturi [14]:$$C=(V_E{\Sigma }_E+V_{E^{\perp }}{\Sigma }_{E^{\perp }E})T_{E,F}^T(V_F^T+{\Lambda }_F^{-1}{\Lambda }_{F^{\perp }F}^T{V}_{F^{\perp }}^T).$$

To check it, just expand the terms and see that $$C_{E,F}=V_{E}C{V}_F^T$$.

Appendix B. Knothe–Rosenblatt

Appendix B.1. Properties of (12)

Proposition A1.

In a slightly more general setting, let $$X_0=X_1={\mathbb{R}}^d$$, functions $$f_0,f_1$$ from $${\mathbb{R}}^d\times {\mathbb{R}}^d$$ to $${\mathbb{R}}^d$$, and measures $${\mu }_0\in \mathcal{P}\left(X_0\right)$$, $${\mu }_1\in \mathcal{P}\left(X_1\right)$$. Then, the family $${\mathcal{X}}_t=(X_0\times X_1,f_t,{\gamma }^{*})$$ defines a geodesic between $${\mathcal{X}}_0$$ and $${\mathcal{X}}_1$$, where $${\gamma }^{*}$$ is the optimal coupling of $$\mathcal{HW}$$ between $${\mu }_0$$ and $${\mu }_1$$, and $$f_t((x_0,x_0^{\prime }),(x_1,x_1^{\prime }))=(1-t)f_0(x_0,x_0^{\prime })+t{f}_1(x_1,x_1^{\prime }).$$

Proof. 

See Theorem 3.1 in [8]. □

Appendix B.2. Proof of Theorem 3

We first recall a useful theorem.

Theorem A1

(Theorem 2.8 in Billingsley [45]). Let $$\Omega =X\times Y$$ be a separable space, and let $$P,P_n\in \mathcal{P}(\Omega )$$ with marginals $$P_X$$ (respectively $$P_{n,X}$$) and $$P_Y$$ (respectively $$P_{n,Y}$$). Then, $$P_{n,X}\otimes P_{n,Y}\stackrel{\mathcal{D}}{\to }P$$ if and only if $$P_{n,X}\stackrel{\mathcal{D}}{\to }{P}_X$$, $$P_{n,Y}\stackrel{\mathcal{D}}{\to }{P}_Y$$ and $$P=P_X\otimes P_Y$$.

Proof of Theorem 3. 

The following proof is mainly inspired by the proof of Theorem 1 in [21] (Theorem 2.1), [22] (Theorem 3.1.6) and [19] (Theorem 2.23).

Let $$\mu ,\nu \in \mathcal{P}\left({\mathbb{R}}^d\right)$$, absolutely continuous, with finite fourth moments and compact supports. We recall the problem $${\mathcal{HW}}_t$$: $${\mathcal{HW}}_t^2(\mu ,\nu )=\underset{\gamma \in \mathsf{\Pi }(\mu ,\nu )}{inf}\int \int \sum _{k=1}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime }),$$ with $$\forall t>0,\forall i\in \{1,\cdots ,d-1\}$$, $${\lambda }_t^{\left(i\right)}>0$$ and $${\lambda }_t^{\left(i\right)}\underset{t\to 0}{\to }0$$.

First, let us denote $${\gamma }_t$$ the optimal coupling for $${\mathcal{HW}}_t$$ for all $$t>0$$. We want to show that $${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\gamma }_K$$ with $${\gamma }_K={(Id\times T_K)}_{\#}\mu$$ and $$T_K$$ our alternate Knothe-Rosenblatt rearrangement. Let $$\gamma \in \mathsf{\Pi }(\mu ,\nu )$$ such that $${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}\gamma$$ (true up to subsequence as $$\left\{\mu \right\}$$ and $$\left\{\nu \right\}$$ are tight in $$\mathcal{P}\left(X\right)$$ and $$\mathcal{P}\left(Y\right)$$ if X and Y are polish space, therefore, by [18] (Lemma 4.4), $$\mathsf{\Pi }(\mu ,\nu )$$ is a tight set, and we can apply the Prokhorov theorem [19] (Box 1.4) on $${\left({\gamma }_t\right)}_t$$ and extract a subsequence)).

Part 1:

First, let us notice that: $$\begin{array}{cc}\hfill {\mathcal{HW}}_t^2(\mu ,\nu )& =\int \int \sum _{k=1}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ \hfill & +\int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime }).\hfill \end{array}$$

Moreover, as $${\gamma }_t$$ is the optimal coupling between $$\mu$$ and $$\nu$$, and $${\gamma }_K\in \mathsf{\Pi }(\mu ,\nu )$$, $$\begin{array}{cc}\hfill {\mathcal{HW}}_t^2(\mu ,\nu )& \le \int \int \sum _{k=1}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime })\hfill \\ \hfill & +\int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime }).\hfill \end{array}$$

In our case, we have $${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}\gamma$$, thus, by Theorem A1, we have $${\gamma }_t\otimes {\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}\gamma \otimes \gamma$$. Using the fact that $$\forall i,{\lambda }_t^{\left(i\right)}\underset{t\to 0}{\to }0$$ (and Lemma 1.8 of Santambrogio [19], since we are on compact support, we can bound the cost (which is continuous) by its max), we obtain the following inequality $$\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\le \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime }).$$

By denoting $${\gamma }^1$$ and $${\gamma }_K^1$$ the marginals on the first variables, we can use the projection $${\pi }^1(x,y)=(x_1,y_1)$$, such as $${\gamma }^1={\pi }_{\#}^1\gamma$$ and $${\gamma }_K^1={\pi }_{\#}^1{\gamma }_K$$. Hence, we get $$\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime })\le \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_K^1(x_1,y_1)\mathrm{d}{\gamma }_K^1(x_1^{\prime },y_1^{\prime }).$$

However, $${\gamma }_K^1$$ was constructed in order to be the unique optimal map for this cost (either $$T_{asc}$$ or $$T_{desc}$$ according to theorem [26] (Theorem 4.2.4)). Thus, we can deduce that $${\gamma }^1={(Id\times T_K^1)}_{\#}{\mu }^1={\gamma }_K^1$$.

Part 2:

We know that for any $$t>0$$, $${\gamma }_t$$ and $${\gamma }_K$$ share the same marginals. Thus, as previously, $${\pi }_{\#}^1{\gamma }_t$$ should have a cost worse than $${\pi }_{\#}^1{\gamma }_K$$, which translates to $$\begin{array}{cc}\hfill \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_K^1(x_1,y_1)\mathrm{d}{\gamma }_K^1(x_1^{\prime },y_1^{\prime })& =\int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime })\hfill \\ \hfill & \le \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }_t^1(x_1,y_1)\mathrm{d}{\gamma }_t^1(x_1^{\prime },y_1^{\prime }).\hfill \end{array}$$

Therefore, we have the following inequality, $$\begin{array}{cc}\hfill & \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }^1(x,y)\mathrm{d}{\gamma }^1(x^{\prime },y^{\prime })+\int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ \hfill & \le {\mathcal{HW}}_t^2(\mu ,\nu )\hfill \\ \hfill & \le \int \int {(x_1{x}_1^{\prime }-y_1{y}_1^{\prime })}^2\mathrm{d}{\gamma }^1(x,y)\mathrm{d}{\gamma }^1(x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime }).\hfill \end{array}$$

We can substract the first term and factorize by $${\lambda }_t^{\left(1\right)}>0$$, $$\begin{array}{cc}\hfill & \int \int \sum _{k=2}^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ \hfill & ={\lambda }_t^{\left(1\right)}(\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=3}^d\left(\prod _{i=2}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime }))\hfill \\ \hfill & \le {\lambda }_t^{\left(1\right)}(\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=3}^d\left(\prod _{i=2}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime })).\hfill \end{array}$$

By dividing by $${\lambda }_t^{\left(1\right)}$$ and by taking the limit $$t\to 0$$ as in the first part, we get (A3)$$\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\le \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime }).$$

Now, the 2 terms depend only on $$(x_2,y_2)$$ and $$(x_2^{\prime },y_2^{\prime })$$. We will project on the two first coordinates, i.e., let $${\pi }^{1,2}(x,y)=((x_1,x_2),(y_1,y_2))$$ and $${\gamma }^{1,2}={\pi }_{\#}^{1,2}\gamma$$, $${\gamma }_K^{1,2}={\pi }_{\#}^{1,2}{\gamma }_K$$. Using the disintegration of measures, we know that there exist kernels $${\gamma }^{2|1}$$ and $${\gamma }_K^{2|1}$$ such that $${\gamma }^{1,2}={\gamma }^1\otimes {\gamma }^{2|1}$$ and $${\gamma }_K^{1,2}={\gamma }_K^1\otimes {\gamma }_K^{2|1}$$, where $$\forall A\in \mathcal{B}(X\times Y),\mu \otimes K\left(A\right)=\int \int {𝟙}_A(x,y)K(x,\mathrm{d}y)\mu \left(\mathrm{d}x\right).$$

We can rewrite the previous Equation (A3) as (A4)$$\begin{array}{cc}\hfill & \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\hfill \\ \hfill & =\int \int \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ & \mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime })\hfill \\ \hfill & \le \int \int \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }_K^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }_K^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ & \mathrm{d}{\gamma }_K^1(x_1,y_1)\mathrm{d}{\gamma }_K^1(x_1^{\prime },y_1^{\prime }).\hfill \end{array}$$

Now, we will assume at first that the marginals of $${\gamma }^{2|1}((x_1,y_1),·)$$ are well $${\mu }^{2|1}(x_1,·)$$ and $${\nu }^{2|1}(y_1,·)$$. Then, by definition of $${\gamma }_K^{2|1}$$, as it is optimal for the $$GW$$ cost with inner products, we have for all $$(x_1,y_1),(x_1^{\prime },y_1^{\prime })$$, (A5)$$\begin{array}{cc}\hfill & \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }_K^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }_K^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ \hfill & \le \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime })).\hfill \end{array}$$ Moreover, we know from the first part that $${\gamma }^1={\gamma }_K^1$$, then by integrating with respect to $$(x_1,y_1)$$ and $$(x_1^{\prime },y_1^{\prime })$$, we have (A6)$$\begin{array}{cc}\hfill & \int \int \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }_K^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }_K^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ & \mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime })\hfill \\ \hfill & \le \int \int \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ & \mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime }).\hfill \end{array}$$ By (A4) and (A6), we deduce that we have an equality and we get (A7)$$\begin{array}{cc}\hfill & \int \int (\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ \hfill & -\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }_K^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }_K^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime })))\hfill \\ & \mathrm{d}{\gamma }^1(x_1,y_1)\mathrm{d}{\gamma }^1(x_1^{\prime },y_1^{\prime })=0.\hfill \end{array}$$ However, we know by (A5) that the middle part of (A7) is nonnegative, thus we have for $${\gamma }^1$$-a.e. $$(x_1,y_1),(x_1^{\prime },y_1^{\prime })$$, $$\begin{array}{cc}\hfill & \int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }_K^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }_K^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime }))\hfill \\ \hfill & =\int \int {(x_2{x}_2^{\prime }-y_2{y}_2^{\prime })}^2{\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2)){\gamma }^{2|1}((x_1^{\prime },y_1^{\prime }),(\mathrm{d}{x}_2^{\prime },\mathrm{d}{y}_2^{\prime })).\hfill \end{array}$$ From that, we can conclude as in the first part that $${\gamma }^{2|1}={\gamma }_K^{2|1}$$ (by unicity of the optimal map). And thus $${\gamma }^{1,2}={\gamma }_K^{1,2}$$.

Now, we still have to show that the marginals of $${\gamma }^{2|1}((x_1,y_1),·)$$ and $${\gamma }_K^{2,1}((x_1,y_1),·)$$ are well the same, i.e., $${\mu }^{2|1}(x_1,·)$$ and $${\nu }^{2|1}(y_1,·)$$. Let $$\varphi$$ and $$\psi$$ be continuous functions, then we have to show that for $${\gamma }^1$$-a.e. $$(x_1,y_1)$$, we have $$\left\{\begin{array}{c}\int \varphi \left(x_2\right){\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2))=\int \varphi \left(x_2\right){\mu }^{2|1}(x_1,\mathrm{d}{x}_2)\hfill \\ \int \psi \left(y_2\right){\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2))=\int \psi \left(y_2\right){\nu }^{2|1}(y_1,\mathrm{d}{y}_2).\hfill \end{array}\right.$$ As we want to prove it for $${\gamma }^1$$-a.e. $$(x_1,y_1)$$, it is sufficient to prove that for all continuous function $$\xi$$, $$\left\{\begin{array}{c}\int \int \xi (x_1,y_1)\varphi \left(x_2\right){\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2))\mathrm{d}{\gamma }^1(x_1,y_1)\hfill \\ =\int \int \xi (x_1,y_1)\varphi \left(x_2\right){\mu }^{2|1}(x_1,\mathrm{d}{x}_2)\mathrm{d}{\gamma }^1(x_1,y_1)\hfill \\ \int \int \xi (x_1,y_1)\psi \left(y_2\right){\gamma }^{2|1}((x_1,y_1),(\mathrm{d}{x}_2,\mathrm{d}{y}_2))\mathrm{d}{\gamma }^1(x_1,y_1)\hfill \\ =\int \int \xi (x_1,y_1)\psi \left(y_2\right){\nu }^{2|1}(y_1,\mathrm{d}{y}_2)\mathrm{d}{\gamma }^1(x_1,y_1).\hfill \end{array}\right.$$

First, we can use the projections $${\pi }_x(x,y)=x$$ and $${\pi }_y(x,y)=y$$. Moreover, we know that $${\gamma }^1={(Id\times T_K^1)}_{\#}{\mu }^1$$. The alternate Knothe–Rosenblatt rearrangement is, as the usual one, bijective (because $$\mu$$ and $$\nu$$ are absolutely continuous), and thus, as we suppose that $$\nu$$ satisfies the same hypothesis than $$\mu$$, we also have $${\gamma }^1={({\left(T_K^1\right)}^{-1},Id)}_{\#}{\nu }^1$$. Let us note $${\tilde{T}}_K^1={\left(T_K^1\right)}^{-1}$$. Then, the equalities that we want to show are: $$\left\{\begin{array}{c}\int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right){\gamma }_x^{2|1}((x_1,T_K^1\left(x_1\right)),\mathrm{d}{x}_2)\mathrm{d}{\mu }^1\left(x_1\right)\hfill \\ =\int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right){\mu }^{2|1}(x_1,\mathrm{d}{x}_2)\mathrm{d}{\mu }^1\left(x_1\right)\hfill \\ \int \int \xi ({\tilde{T}}_K^1\left(y_1\right),y_1)\psi \left(y_2\right){\gamma }_y^{2|1}(({\tilde{T}}_K^1\left(y_1\right),y_1),\mathrm{d}{y}_2)\mathrm{d}{\nu }^1\left(y_1\right)\hfill \\ =\int \int \xi ({\tilde{T}}_K^1\left(y_1\right),y_1)\psi \left(y_2\right){\nu }^{2|1}(y_1,\mathrm{d}{y}_2)\mathrm{d}{\nu }^1\left(y_1\right).\hfill \end{array}\right.$$ In addition, we have indeed $$\begin{array}{cc}\hfill & \int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right){\gamma }_x^{2|1}((x_1,T_K^1\left(x_1\right)),\mathrm{d}{x}_2)\mathrm{d}{\mu }^1\left(x_1\right)\hfill \\ & =\int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right)\mathrm{d}{\gamma }^{1,2}((x_1,x_2),(y_1,y_2))\hfill \\ \hfill & =\int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right)\mathrm{d}{\gamma }_x^{1,2}(x_1,x_2)\hfill \\ \hfill & =\int \int \xi (x_1,T_K^1\left(x_1\right))\varphi \left(x_2\right){\mu }^{2|1}(x_1,\mathrm{d}{x}_2)\mathrm{d}{\mu }^1\left(x_1\right).\hfill \end{array}$$ We can do the same for the $$\nu$$ part by symmetry.

Part 3:

Now, we can proceed the same way by induction. Let $$\ell \in \{2,\cdots ,d\}$$ and suppose that the result is true in dimension $$\ell -1$$ (i.e., $${\gamma }^{1:\ell -1}={\pi }_{\#}^{1:\ell -1}\gamma ={\gamma }_K^{1:\ell -1}$$).

For this part of the proof, we rely on [19] (Theorem 2.23). We can build a measure $${\gamma }_K^t\in \mathcal{P}({\mathbb{R}}^d\times {\mathbb{R}}^d)$$ such that: (A8)$$\left\{\begin{array}{c}{\pi }_{\#}^x{\gamma }_K^t=\mu \hfill \\ {\pi }_{\#}^y{\gamma }_K^t=\nu \hfill \\ {\pi }_{\#}^{1:\ell -1}{\gamma }_K^t={\eta }_{t,\ell }\hfill \end{array}\right.$$ where $${\eta }_{t,\ell }$$ is the optimal transport plan between $${\mu }^{\ell }={\pi }_{\#}^{1:\ell -1}\mu$$ and $${\nu }^{\ell }={\pi }_{\#}^{1:\ell -1}\nu$$ for the objective: $$\int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime }).$$ By induction hypothesis, we have $${\eta }_{t,\ell }\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\pi }_{\#}^{1:\ell -1}{\gamma }_K$$. To build such a measure, we can first disintegrate $$\mu$$ and $$\nu$$: $$\left\{\begin{array}{c}\mu ={\mu }^{1:\ell -1}\otimes {\mu }^{\ell :d|1:\ell -1}\hfill \\ \nu ={\nu }^{1:\ell -1}\otimes {\nu }^{\ell :d|1:\ell -1},\hfill \end{array}\right.$$ then we pick the Knothe transport $${\gamma }_K^{\ell :d|1:\ell -1}$$ between $${\mu }^{\ell :d|1:\ell -1}$$ and $${\nu }^{\ell :d|1:\ell -1}$$. Thus, by taking $${\gamma }_K^T={\eta }_{t,\ell }\otimes {\gamma }_K^{\ell :d|1:\ell -1}$$, $${\gamma }_K^T$$ satisfies the conditions well (A8).

Hence, we have: $$\begin{array}{cc}\hfill & \int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ & =\int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1},y_{1:\ell -1})\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime })\hfill \\ \hfill & \le \int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime }),\hfill \end{array}$$ and therefore: $$\begin{array}{cc}\hfill & \int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=\ell }^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\hfill \\ \hfill & \le {\mathcal{HW}}_t^2(\mu ,\nu )\hfill \\ \hfill & \le \int \int \sum _{k=1}^{\ell -1}\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ & +\int \int \sum _{k=\ell }^d\left(\prod _{i=1}^{k-1}{\lambda }_t^{\left(i\right)}\right){(x_k{x}_k^{\prime }-y_k{y}_k^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime }).\hfill \end{array}$$

As before, by subtracting the first term, dividing by $${\prod }_{i=1}^{\ell -1}{\lambda }_t^{\left(i\right)}$$ and taking the limit, we obtain: $$\int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_t(x,y)\mathrm{d}{\gamma }_t(x^{\prime },y^{\prime })\le \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime }).$$ For the right hand side, using that $${\gamma }_K^t={\eta }_{t,\ell }\otimes {\gamma }_K^{\ell :d|1:\ell -1}$$, we have: $$\begin{array}{cc}\hfill & \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ & =\int \int \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2{\gamma }_K^{\ell :d|1:\ell -1}((x_{1:\ell -1},y_{1:\ell -1}),(\mathrm{d}{x}_{\ell :d},\mathrm{d}{y}_{\ell :d}))\hfill \\ & {\gamma }_K^{\ell :d|1:\ell -1}((x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime }),(\mathrm{d}{x}_{\ell :d}^{\prime },\mathrm{d}{y}_{\ell :d}^{\prime }))\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1},y_{1:\ell -1})\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime })\hfill \\ \hfill & =\int \int \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2{\gamma }_K^{\ell |1:\ell -1}((x_{1:\ell -1},y_{1:\ell -1}),(\mathrm{d}{x}_{\ell },\mathrm{d}{y}_{\ell }))\hfill \\ & {\gamma }_K^{\ell |1:\ell -1}((x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime }),(\mathrm{d}{x}_{\ell }^{\prime },\mathrm{d}{y}_{\ell }^{\prime }))\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1},y_{1:\ell -1})\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime }).\hfill \end{array}$$ Let us note for $${\eta }_{t,\ell }$$ almost every $$(x_{1:\ell -1},y_{1:\ell -1}),(x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime })$$ $$\begin{array}{cc}\hfill & GW({\mu }^{\ell |1:\ell -1},{\nu }^{\ell |1:\ell -1})\hfill \\ & =\int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2{\gamma }_K^{\ell |1:\ell -1}((x_{1:\ell -1},y_{1:\ell -1}),(\mathrm{d}{x}_{\ell },\mathrm{d}{y}_{\ell })){\gamma }_K^{\ell |1:\ell -1}((x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime }),(\mathrm{d}{x}_{\ell }^{\prime },\mathrm{d}{y}_{\ell }^{\prime })),\hfill \end{array}$$ then $$\begin{array}{cc}\hfill & \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ & =\int \int GW({\mu }^{\ell |1:\ell -1},{\nu }^{\ell |1:\ell -1})\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1},y_{1:\ell -1})\mathrm{d}{\eta }_{t,\ell }(x_{1:\ell -1}^{\prime },y_{1:\ell -1}^{\prime }).\hfill \end{array}$$ By Theorem A1, we have $${\eta }_{t,\ell }\otimes {\eta }_{t,\ell }\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\pi }_{\#}^{1:\ell -1}{\gamma }_K\otimes {\pi }_{\#}^{1:\ell -1}{\gamma }_K$$. So, if (A9)$$\eta \mapsto \int \int GW({\mu }^{\ell |1:\ell -1},{\nu }^{\ell |1:\ell -1})\mathrm{d}\eta \mathrm{d}\eta$$ is continuous over the transport plans between $${\mu }^{1:\ell -1}$$ and $${\nu }^{1:\ell -1}$$, we have $$\begin{array}{cc}\hfill & \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K^t(x,y)\mathrm{d}{\gamma }_K^t(x^{\prime },y^{\prime })\hfill \\ \hfill & \underset{t\to 0}{\to }\int \int GW({\mu }^{\ell |1:\ell -1},{\nu }^{\ell |1:\ell -1}){\pi }_{\#}^{1:\ell -1}{\gamma }_K(\mathrm{d}{x}_{1:\ell -1},\mathrm{d}{y}_{1:\ell -1}){\pi }_{\#}^{1:\ell -1}{\gamma }_K(\mathrm{d}{x}_{1:\ell -1}^{\prime },\mathrm{d}{y}_{1:\ell -1}^{\prime })\hfill \end{array}$$ and $$\begin{array}{cc}\hfill & \int \int GW({\mu }^{\ell |1:\ell -1},{\nu }^{\ell |1:\ell -1}){\pi }_{\#}^{1:\ell -1}{\gamma }_K(\mathrm{d}{x}_{1:\ell -1},\mathrm{d}{y}_{1:\ell -1}){\pi }_{\#}^{1:\ell -1}{\gamma }_K(\mathrm{d}{x}_{1:\ell -1}^{\prime },\mathrm{d}{y}_{1:\ell -1}^{\prime })\hfill \\ \hfill & =\int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime })\hfill \end{array}$$ by replacing the true expression of $$GW$$ and using the disintegration $${\gamma }_K={\left({\pi }_K^{1:\ell -1}\right)}_{\#}{\gamma }_K\otimes {\gamma }_K^{\ell |1:\ell -1}$$.

For the continuity, we can apply [19] (Lemma 1.8) (as in the [19] (Corollary 2.24)) with $$X=Y={\mathbb{R}}^{\ell -1}\times {\mathbb{R}}^{\ell -1}$$, $$\tilde{X}=\tilde{Y}=\mathcal{P}(\Omega )$$ with $$\Omega \subset {\mathbb{R}}^{d-\ell +1}\times {\mathbb{R}}^{d-\ell +1}$$ and $$c(a,b)=GW(a,b)$$, which can be bounded on compact supports by $$max\left|c\right|$$. Moreover, we use Theorem A1 and the fact that $${\eta }_t\otimes {\eta }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\gamma }_K^{1:\ell -1}\otimes {\gamma }_K^{1:\ell -1}$$.

By taking the limit $$t\to 0$$, we now obtain: $$\int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}\gamma (x,y)\mathrm{d}\gamma (x^{\prime },y^{\prime })\le \int \int {(x_{\ell }{x}_{\ell }^{\prime }-y_{\ell }{y}_{\ell }^{\prime })}^2\mathrm{d}{\gamma }_K(x,y)\mathrm{d}{\gamma }_K(x^{\prime },y^{\prime }).$$

We can now disintegrate with respect to $${\gamma }^{1:\ell -1}$$ as before. We just need to prove that the marginals coincide, which is performed by taking for test functions: $$\left\{\begin{array}{c}\xi (x_1,\cdots ,x_{\ell -1},y_1,\cdots ,y_{\ell -1})\varphi \left(x_{\ell }\right)\hfill \\ \xi (x_1,\cdots ,x_{\ell -1},y_1,\cdots ,y_{\ell -1})\psi \left(y_{\ell }\right)\hfill \end{array}\right.$$ and using the fact that the measures are concentrated on $$y_k=T_K\left(x_k\right)$$.

Part 4:

Therefore, we have well $${\gamma }_t\underset{t\to 0}{\overset{\mathcal{D}}{\to }}{\gamma }_K$$. Finally, for the $$L^2$$ convergence, we have: $$\int \parallel T_t\left(x\right)-T_K{\left(x\right)\parallel }_2^2\mu \left(\mathrm{d}x\right)=\int \parallel y-T_K{\left(x\right)\parallel }_2^2\mathrm{d}{\gamma }_t(x,y)\to \int {\parallel y-T_K\left(x\right)\parallel }_2^2\mathrm{d}{\gamma }_K(x,y)=0$$ as $${\gamma }_t={(Id\times T_t)}_{\#}\mu$$ and $${\gamma }_K={(Id\times T_K)}_{\#}\mu$$. Hence, $$T_t\underset{t\to 0}{\overset{L^2}{\to }}{T}_K$$. □

References

1. Arjovsky, M.; Chintala, S.; Bottou, L. Wasserstein generative adversarial networks. Proceedings of the International Conference on Machine Learning, PMLR; Sydney, Australia, 6–11 August 2017; pp. 214-223.

2. Courty, N.; Flamary, R.; Tuia, D.; Rakotomamonjy, A. Optimal transport for domain adaptation. IEEE Trans. Pattern Anal. Mach. Intell.; 2016; 39, pp. 1853-1865. [DOI: https://dx.doi.org/10.1109/TPAMI.2016.2615921] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/27723579]

3. Mémoli, F. Gromov–Wasserstein distances and the metric approach to object matching. Found. Comput. Math.; 2011; 11, pp. 417-487. [DOI: https://dx.doi.org/10.1007/s10208-011-9093-5]

4. Chowdhury, S.; Miller, D.; Needham, T. Quantized Gromov–Wasserstein. Proceedings of the Machine Learning and Knowledge Discovery in Databases, Research Track—European Conference, ECML PKDD 2021; Bilbao, Spain, 13–17 September 2021; Proceedings, Part III Oliver, N.; Pérez-Cruz, F.; Kramer, S.; Read, J.; Lozano, J.A. Springer: Berlin/Heidelberg, Germany, 2021; Volume 12977, pp. 811-827. [DOI: https://dx.doi.org/10.1007/978-3-030-86523-8_49]

5. Alvarez-Melis, D.; Jegelka, S.; Jaakkola, T.S. Towards optimal transport with global invariances. Proceedings of the The 22nd International Conference on Artificial Intelligence and Statistics, PMLR; Naha, Japan, 16–18 April 2019; pp. 1870-1879.

6. Cai, Y.; Lim, L.H. Distances between probability distributions of different dimensions. arXiv; 2020; arXiv: 2011.00629

7. Mémoli, F. On the use of Gromov-Hausdorff Distances for Shape Comparison. Proceedings of the 4th Symposium on Point Based Graphics, PBG@Eurographics 2007; Prague, Czech Republic, 2–3 September 2007; Botsch, M.; Pajarola, R.; Chen, B.; Zwicker, M. Eurographics Association: Switzerland, Geneve, 2007; pp. 81-90. [DOI: https://dx.doi.org/10.2312/SPBG/SPBG07/081-090]

8. Sturm, K.T. The space of spaces: Curvature bounds and gradient flows on the space of metric measure spaces. arXiv; 2012; arXiv: 1208.0434

9. Peyré, G.; Cuturi, M.; Solomon, J. Gromov–Wasserstein averaging of kernel and distance matrices. Proceedings of the International Conference on Machine Learning, PMLR; New York, NY, USA, 19–24 June 2016; pp. 2664-2672.

10. Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. Adv. Neural Inf. Process. Syst.; 2013; 26, pp. 2292-2300.

11. Scetbon, M.; Peyré, G.; Cuturi, M. Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs. arXiv; 2021; arXiv: 2106.01128

12. Vayer, T.; Flamary, R.; Courty, N.; Tavenard, R.; Chapel, L. Sliced Gromov–Wasserstein. Adv. Neural Inf. Process. Syst.; 2019; 32, pp. 14753-14763.

13. Fatras, K.; Zine, Y.; Majewski, S.; Flamary, R.; Gribonval, R.; Courty, N. Minibatch optimal transport distances; analysis and applications. arXiv; 2021; arXiv: 2101.01792

14. Muzellec, B.; Cuturi, M. Subspace Detours: Building Transport Plans that are Optimal on Subspace Projections. Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019; Vancouver, BC, Canada, 8–14 December 2019; Wallach, H.M.; Larochelle, H.; Beygelzimer, A.; d’Alché-Buc, F.; Fox, E.B.; Garnett, R. 2019; pp. 6914-6925.

15. Bogachev, V.I.; Kolesnikov, A.V.; Medvedev, K.V. Triangular transformations of measures. Sb. Math.; 2005; 196, 309. [DOI: https://dx.doi.org/10.1070/SM2005v196n03ABEH000882]

16. Knothe, H. Contributions to the theory of convex bodies. Mich. Math. J.; 1957; 4, pp. 39-52. [DOI: https://dx.doi.org/10.1307/mmj/1028990175]

17. Rosenblatt, M. Remarks on a multivariate transformation. Ann. Math. Stat.; 1952; 23, pp. 470-472. [DOI: https://dx.doi.org/10.1214/aoms/1177729394]

18. Villani, C. Optimal Transport: Old and New; Springer Science & Business Media: Berlin/Heidelberg, Germany, 2008; Volume 338.

19. Santambrogio, F. Optimal transport for applied mathematicians. Birkäuser NY; 2015; 55, 94.

20. Jaini, P.; Selby, K.A.; Yu, Y. Sum-of-Squares Polynomial Flow. Proceedings of the 36th International Conference on Machine Learning, PMLR; Long Beach, CA, USA, 9–15 June 2019; pp. 3009-3018.

21. Carlier, G.; Galichon, A.; Santambrogio, F. From Knothe’s transport to Brenier’s map and a continuation method for optimal transport. SIAM J. Math. Anal.; 2010; 41, pp. 2554-2576. [DOI: https://dx.doi.org/10.1137/080740647]

22. Bonnotte, N. Unidimensional and Evolution Methods for Optimal Transportation. Ph.D. Thesis; Université Paris-Sud: Paris, France, 2013.

23. Ambrosio, L.; Gigli, N.; Savaré, G. Gradient Flows: In Metric Spaces and in the Space of Probability Measures; Springer Science & Business Media: Berlin/Heidelberg, Germany, 2008.

24. Niles-Weed, J.; Rigollet, P. Estimation of wasserstein distances in the spiked transport model. arXiv; 2019; arXiv: 1909.07513

25. Chowdhury, S.; Mémoli, F. The gromov–wasserstein distance between networks and stable network invariants. Inf. Inference A J. IMA; 2019; 8, pp. 757-787. [DOI: https://dx.doi.org/10.1093/imaiai/iaz026]

26. Vayer, T. A Contribution to Optimal Transport on Incomparable Spaces. Ph.D. Thesis; Université de Bretagne Sud: Vannes, France, 2020.

27. Paty, F.P.; Cuturi, M. Subspace robust wasserstein distances. Proceedings of the 36th International Conference on Machine Learning, PMLR; Long Beach, CA, USA, 9–15 June 2019; pp. 5072-5081.

28. Rasmussen, C.E. Gaussian processes in machine learning. Summer School on Machine Learning; Springer: Berlin/Heidelberg, Germany, 2003; pp. 63-71.

29. Von Mises, R. Mathematical Theory of Probability and Statistics; Academic Press: Cambridge, MA, USA, 1964.

30. Salmona, A.; Delon, J.; Desolneux, A. Gromov–Wasserstein Distances between Gaussian Distributions. arXiv; 2021; arXiv: 2104.07970

31. Weed, J.; Bach, F. Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli; 2019; 25, pp. 2620-2648. [DOI: https://dx.doi.org/10.3150/18-BEJ1065]

32. Lin, T.; Zheng, Z.; Chen, E.; Cuturi, M.; Jordan, M. On projection robust optimal transport: Sample complexity and model misspecification. Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR; Virtual, 13–15 April 2021; pp. 262-270.

33. Burkard, R.E.; Klinz, B.; Rudolf, R. Perspectives of Monge Properties in Optimization. Discret. Appl. Math.; 1996; 70, pp. 95-161. [DOI: https://dx.doi.org/10.1016/0166-218X(95)00103-X]

34. Flamary, R.; Courty, N.; Gramfort, A.; Alaya, M.Z.; Boisbunon, A.; Chambon, S.; Chapel, L.; Corenflos, A.; Fatras, K.; Fournier, N. et al. POT: Python Optimal Transport. J. Mach. Learn. Res.; 2021; 22, pp. 1-8.

35. Bogo, F.; Romero, J.; Loper, M.; Black, M.J. FAUST: Dataset and evaluation for 3D mesh registration. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition; Columbus, OH, USA, 23–28 June 2014; pp. 3794-3801.

36. Fiedler, M. Algebraic connectivity of graphs. Czechoslov. Math. J.; 1973; 23, pp. 298-305. [DOI: https://dx.doi.org/10.21136/CMJ.1973.101168]

37. Hagberg, A.; Swart, P.; Chult, D.S. Exploring Network Structure, Dynamics, and Function Using NetworkX; Technical Report Los Alamos National Lab. (LANL): Los Alamos, NM, USA, 2008.

38. Wu, J.P.; Song, J.Q.; Zhang, W.M. An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration. J. Comput. Appl. Math.; 2014; 269, pp. 101-108. [DOI: https://dx.doi.org/10.1016/j.cam.2014.03.018]

39. Xu, H.; Luo, D.; Carin, L. Scalable Gromov–Wasserstein learning for graph partitioning and matching. Adv. Neural Inf. Process. Syst.; 2019; 32, pp. 3052-3062.

40. Chowdhury, S.; Needham, T. Generalized spectral clustering via Gromov–Wasserstein learning. Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR; Virtual, 13–15 April 2021; pp. 712-720.

41. Vayer, T.; Courty, N.; Tavenard, R.; Flamary, R. Optimal transport for structured data with application on graphs. Proceedings of the 36th International Conference on Machine Learning, PMLR; Long Beach, CA, USA, 9–15 June 2019; pp. 6275-6284.

42. Lacoste-Julien, S. Convergence rate of frank-wolfe for non-convex objectives. arXiv; 2016; arXiv: 1607.00345

43. Peyré, G.; Cuturi, M. Computational optimal transport: With applications to data science. Found. Trends^® Mach. Learn.; 2019; 11, pp. 355-607. [DOI: https://dx.doi.org/10.1561/2200000073]

44. Nagar, R.; Raman, S. Detecting approximate reflection symmetry in a point set using optimization on manifold. IEEE Trans. Signal Process.; 2019; 67, pp. 1582-1595. [DOI: https://dx.doi.org/10.1109/TSP.2019.2893835]

45. Billingsley, P. Convergence of Probability Measures; John Wiley & Sons: Hoboken, NJ, USA, 2013.