Fast Optimal Transport through Sliced Generalized Wasserstein Geodesics
Authors: Guillaume Mahey
Laetitia Chapel
Gilles Gasso
Clément Bonet
Nicolas Courty
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Optimal Transport
Wasserstein distance
Generalized Geodesics
Sliced Wasserstein
TL;DR: A new upper bound of $W^2_2$ that is fast to compute and comes with a transport plan

Abstract: Wasserstein distance (WD) and the associated optimal transport plan have been proven useful in many applications where probability measures are at stake. In this paper, we propose a new proxy of the squared WD, coined $\textnormal{min-SWGG}$, that is based on the transport map induced by an optimal one-dimensional projection of the two input distributions. We draw connections between  $\textnormal{min-SWGG}$, and Wasserstein generalized geodesics in which the pivot measure is supported on a line. We notably provide a new closed form for the exact Wasserstein distance in the particular case of one of the distributions supported on a line allowing us to derive a fast computational scheme that is amenable to gradient descent optimization. We show that  $\textnormal{min-SWGG}$, is an upper bound of WD and that it has a complexity similar to as Sliced-Wasserstein, with the additional feature of providing an associated transport plan. We also investigate some theoretical properties such as metricity, weak convergence, computational and topological properties. Empirical evidences support the benefits of  $\textnormal{min-SWGG}$, in various contexts, from gradient flows, shape matching and image colorization, among others.

Fast Optimal Transport through Sliced Wasserstein Generalized Geodesics
Guillaume Mahey
INSA Rouen Normandie Université Bretagne Sud
LITIS IRISA
guillaume maaeeyissa-rouu..fff.
Lactitia Chapel
Gilles Gasso
Université Bretagne Sud Institut Agro Rennes-Angers IRISA
INSA Rouen Normandie LITIS gilles gwwsolinsa--oun..nooo
laetitia. Laetitia.chapeleeeeeeeeeee wwwpelhiriss......ccc..
Clément Bonet
Nicolas Courty Université Bretagne Sud IRISA nicolas. coboolaa..uutyyyuiiuubb....
Université Bretagne Sud
LMBA clement boweb:unii--us......
Abstract
Wasserstein distance (WD) and the associated optimal transport plan have proven useful in many applications where probability measures at stake. In this paper, we propose a new proxy for the squared WD, coined min-SWGG, which relies on the transport map induced by an optimal one-dimensional projection of the two input distributions. We draw connections between min-SWGG and Wasserstein generalized geodesics with pivot measure supported on line. We notably provide a new closed form of the Wasserstein distance in the particular case where one of the distributions is supported on line, allowing to derive fast computational scheme that is amenable to gradient descent optimization. We show that min-SWGG is upper bound of WD and that it has complexity similar that of Waseeddsessrrtnnnn with the additional feature of providing an associated transport plan. We also investigate some theoretical properties such metricity, weak convergence, computational and topological properties. Empirical evidences support the benefits of min-SWGG in various contexts, from gradient flows, shape matching and image colorization, among others.
Introduction
Gaspard Monge, in his seminal work Optimal Transport (OT) 42), studied the following problem: how to move with minimum cost the probability mass of source measure to a target one, for a given transfer cost function? At the heart of OT is the optimal map that describes the optimal displacement as the Monge problem can be reformulated as an assignment problem. has been relaxed by [33 by finding plan that describes the amount of mass moving from the souree to the target. Beyond this optimal plan, an interest of OT that it defines a distance between probability measures: the Wasserstein distance (WD).
Recently, OT has been successfully employed in a wide range of machine learning applications, in which the Wasserstein distance is estimated from the data, such as supervised learning (30 natural
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

language processing [38] or generative modelling [S]. Its capacity to provide meaningful distances between empirical distributions is at the core of distance-based algorithms such as kernel-based methods [60] or k-nearest neighbors [6] The optimal transport plan has also been used successfully
in many applications where a matching between empirical samples is sought such as color transfer [99] and positive-unlabeled learning [15].
[55]. domain adaptation
Solving the OT problem is computationally intensive: the most common algorithmic tools to solve the
discrete OT problem are borrowed from combinatorial optimization and linear programming, leading to cubic complexity with the number of samples that prevents its use in large scale applications [53]. To reduce the computation burden, regularizing the OT problem with e.g. an entropic term has led to
solvers with a quadratic complexity [23]. Other methods based on the existence of a closed form of OT have also been devised to efficiently compute proxy for WD, as outlined below.
Projections-based OT. The Sliced- Wasserstein distance (SWD) 56 10 leverages 1 IDDprojections of distributions to provide a lower approximation of the Wasserstein distance, relying on the closed form of OT for ID probability distributions. Computation of SWD leads a linearithmic time complexity,
While SWD averages WDs computed over several ID projections, max-SWD (24) keeps only the most informative projection. These frameworks provide efficient algorithms that can handle millions of samples and have similar topological properties as WD
Other works restrain SWD and to provide more robust estimation of those OT metrics. Although effective as proxies for WD. those methods do not provide a transport plan in the original space Rd. To overcome this limitation, 471 aims to compute transport plans in a subspace which are extrapolated to the original space.
45
max-SWD to projections onto low dimensional subspaces _2
40
Pivot crrasure-basedd OT. Other research works rely on pivot, yet intermediate measure. They decompose the OT metric into Wasserstein distances between each input measure and the con- sidered pivot measure. They exhibit better properties such as statistical sample complexity or computational efficiency (29) 65). Even though the OT problems are split, they are still expensive when dealing with large sample size distributions, notably when only two distributions are involved.
Contributions. We introduce a new proxy for the squared WD that exploits the principles of aforementioned approximations of OT metric. The original idea is to rely projections and one- dimensional assignment of the projected distributions to compute the new proxy. The approach is well-grounded as it hinges on the notion of Wasserstein generalized geodesics 4 with pivot measure supported on a line. The main features of the method are as: i) its computational complexity is on par with SW, ii) it provides an optimal transport plan through the 1D assignment problem, iii) it acts an upper bound of WD, and iv) is amenable to optimization to find the optimal pivot measure. As an addi- tional contribution, we establish a closed form of the WD when an input measure is supported on a line.
Outline. Section presents some background of OT. Section 3 formulates our new WD proxy, provides some of its topological properties and numerical computation scheme. Section 4 builds upon the concept of Wasserstein generalized geodesics to reformulate our OT metric approximation as the Sliced Wasserstein Generalized Geodesics (SWGG) along its optimal variant coined min-SWGG. This reformulation allows deriving additional topological properties and an optimization scheme. Finally, Section 5 provides experimental evaluations.
Notations. Let (..)) be the Euclidean inner product on RRd and let Sd-1 = {u E Rd s.t. ||u||2 = 1}. the unit sphere. We denote P(RR)) the set of probability measures on Rd endowed with the o algebra of Borel set and (2() ((Rd)) those with finite second-order moment i.e. P2(R2))
{u
P(RR) s.t. Se= [00]2du(xx) < oo Let (RR)) be the subspace of (22(R)) defined by empirical measures with n-atoms and uniform masses. For any measurable function f : IRd - Rd, we denote J its push forward, namely for μ (22(R)) and for any measurable set A E Rd. fa (A)), with (A) (xc Rd s.t. f(x) E A).
2 Background on Optimal Transport
Definition 2.1 (Wasserstein distance). The squared WD 63 between N1, E P2(RR)) is defined as:
W2 (M1, U2) def inf rEIl()).H)) wz) xRd || - v11.d
/
(1)
2

---

with [[ μ2) = { E P2(RR x RR) s.t. x(A x R*) = (1( and T(R x A) = M2(A), AA measurable set of R.
The arg min of Eq. is referred to as the optimal transport plan. Denoted πT", it expresses how move the probability mass from fai μl2 with minimum cost. In some cases, n² is of the form (Id, T) # for measurable map T R + R", i.e. there is no mass splitting during the transport. This map is called a Monge map and is denoted Th-+/2 (or shortly Tl-?). Thus, one has (2 (/1,, (22 infr xa Tam-=ur Jpa x ((x) [[dd (a:). This occurs, for instance, when (41 has density w.r.t the Lebesgue measure or when μl and #2 are P2 (Rd) [38.
Endowed with the WD, the space P2(Rd) ) is geodesic space. Indeed, since there exists Monge map T between jl and (22, one can define geodesic curve f yx/=²2 [0, 1] + P2(RR) 31 as:
AI E [0, (1) del (IT)-2 2 + (1 - +
which represents the shortest path w.r.t. Wasserstein distance in P2(RR)) between μ and jr2. The Wasserstein mean between μni and μl2 corresponds to / = 0.5 and we simply write 1!=+2
This notion of geodesic allows the study of the curvature of the Wasserstein space M. Indeed, the Wasserstein space of positive curvature [51], i.e. it respects the following incquality:
W (p1, p2) 2 2W (M1, v/) + 2W2 (v. p2) - (W2
(3)
for all pivot measures v E P2(R*).
Solving and approximating Optimal Transport. The Wasserstein distance between empirical measures M1, H2 with n-atoms can be computed in On n). preventing from the use of OT for large scale applications [I]]. Several algorithms have been proposed to lower this complexity, for example the Sinkhorn algorithm [3 that provides an approximation in near (n?)) complexity [2].
Notably, when μl = Σ 5z, and μ/2 = Em= 6y, are 1D distributions, computing the WD can be done by matching the sorted empirical samples, leading to overall complexity of O( log n). More precisely, let a and I two permutation operators s.t. Za(1) I To(2) I S Fo(m) and
Ur(1) S Vr(2) S ... S Wr(n). Then, the ID Wasserstein distance is given by:
(2(,1, P2) =
(Ia(1) V=(1))²
(4)
Sliced WD. The Sliced-Waa Wasserstennnnninn distance (SWD) (56 aims to scale up the computation of OT by leveraging the closed form expression (4) of the Wasserstein distance for ID distributions. is defined as the expectation of ID-WD computed along projection directions & Sd-1 over the unit sphere:
SW3
W 111 (22) (w),
(5)
J
where pa and pd # 12 are projections onto the direction 0 Sd-1 1 with p8 Rdd R, +> (x.
and where is the uniform distribution over Sd-1
Since the integral in Eq. (5) is intractable, one resorts, in practice, to Monte-Cart estimation to approximate the SWD.
Its computation only involves projections and permutations. For L directions, the computational complexity is (dIn + Ln n) and the memory complexity is ( Ln). However, high dimension, several projections are necessary to approximate accurately the SWD and many projections lead to ID-WD close to 0. This issue well known in the SW community [68), where different
ways of performing effective sampling have been proposed (49 46 50 such as distributional or hierarchical slicing. In particular, this motivates the definition of maxc-Slcced-- -----ll-Wawsersseeiei keeps only the most informative slice:
24 which
max- max-Sw? (W1 def
max (2 Ppp)). 0ES4-1
(6)
While being a non convex problem, it can be optimized efficiently using a gradient ascent scheme.
The SW-like distances are attractive since they are fast to compute and enjoy theoretical properties: they are proper metrics and metricize the weak convergence. However, they do not provide an OT plan.
3

---

Projected WD. Another quantity of interest based on the ID-WD is the projected Wasserstein distance (PWD) [57] leverages the permutations of the projected distributions in ID in order to derive couplings between the original distributions.
Let f11 - on, and μ12
Ei=ı ty. in P2z (RR)). The PWD is defined as:
PWD def
c ooo(i) (m001//2w00
Sd-1
where oa, TB are the permutations obtained by sorting Pa and P #22.
As some permutations are not optimal, straightforwardly have W3 S PWD Note that some permutations can appear highly irrelevant in the original space, leading to an overestimation of W? (typically when the distributions see Supp. 7.1 for a discussion).
multi-modal or with support lying in low dimensional manifold,
In this paper, we restrict ourselves to empirical distributions with the same number of samples. They are defined as μl = 1 Σi=1 82; and μ22 x Σi=1 6y. in P3 (RR).. Note that the results presented therein can be extended to any discrete measures by mainly using quantile functions instead of permutations and transport plans instead of transport maps (see Supp. 7.2).
Definition and properties of min-SWGG
The fact that the PWD overestimates W3 motivates the introduction of our new loss function coined min-SWGG which keeps only the most informative permutation. Afterwards, we derive a property of distance and grant estimation of min-SWGG via random search of the directions.
Definition 3.1 (SWGG and min-SWGG). Let P2 E P7z (Rd) and 0 E Sd-1, Denote by and т the permutations obtained by sorting the 1D projections P /1 and pd #22 SWGG and min-SWGG as:
We define respectively
SWGG (2, der 1
y 110 (oi(
(8)
min-SWGG
min SWGG #E5
(9)
One shall remark that the function SWGG corresponds to the building block of PWD in eq. 77.
One main feature of min-SWGG is that it comes with a transport map. Let l" argmin SWGG u2, 0) be the optimal projection direction. The associated transport map is:
T(x;)- = " (mr. (+)) V1 5
(10)
In Supp. 7.6 we give several examples of such transport plan. These examples show that the overall structure of the optimal transport plan is respected by the transport plan obtained via miG-SWGG.
We now give some theoretical properties of the quantities min-SWGG and SWGG. Their proofs are given in Supp. 7.3
Proposition 3.2 (Distance and Upper bound). Let E sd-1, SWGG2(::, defines a distance on PT (R*). Moreover, min-SWGG is an upper bound of W3, and W3 & min-SWGG3 & PWD3, with equality between W3 and min-SWGG,, when d > 2n.
Remark 3.3. Similarly to max-SW, min-SWGG retains only one optimal direction 6" E Sd-1 However, the two distances strongly differ: min-SWGG is upper bound and max-SW lower bound of W2. ii) the optimal 0* may differ (see Supp. 7.4 for an illustration), and iii) max-SW does provide transport plan between bn and μ22.
Solving Eq. (9) can be achieved using a random search, by sampling L directions E Sd-1 and keeping only the one leading the lowest value of SWGG.
This gives an overall computational complexity of ((Tdn + Ln log and memory complexity of (dn). In low dimension, the random search estimation is effective: covering all possible

---

permutations through Sd-1 can be done with a low number of directions. In high dimension, many more directions are needed to have a relevant approximation, typically OLL=-)). This motivates the design of gradient descent techniques for finding 0"
4 SWGG as minimizing along the Wasserstein generalized geodesics
m//
Solving problem in Eq. (9) amounts optimize over set of admissible permutations. This prob- lem is hard since SWGG non convex w.r.t. and piecewise constant, thus not differentiable over Sd-1 Indeed, as long as the permuta- tions remain the same for different directions 0, the value of SWGG remains constant. When the permutations change, the objective SWGG "jumps" as illustrated in Fig. [
SWOG value
3m/2
Figure (Left) Empirical distributions with ex- amples of 2 sampled lines (Right) that lead to possible values of SWGG when 0 E 2m].
In this section, we tackle this problem by provid- ing alternative formulation of min-SWGG that allows smoothing the different kinks of SWGG, hence, making min-SWGG amenable optimization. This formulation relies on Wasserstein generalized geodesics we introduce hereinafter.
We show that this alternative formulation brings in computational advantages and allows establishing some additional topological properties and deriving an efficient optimization scheme. We also provide a new closed form expression of the Wasserstein distance (21,,, (u2) when either fr or u22 is supported on a line.
4.1 SWGG based on Wasserstein Generalized Geodesics
Wasserstein generalized geodesics (see Supp. 8 for more details) were first introduced in 4 in order to ensure the convergence of Euler scheme for Wasserstein Gradient Flows. This concept has been used notably in 129 44 to speed up some computations and to derive some theoretical properties. Generalized geodesic is also highly related with the idea of linearization of the Wasserstein distance via an L space 665 43, see Supp. for more details on the related works.
Generalized geodesics lay down on a pivot measure v P (Rd) to transport the distribution 141 toward f2z Indeed, one can leverage the optimal transport maps T and T to construct curve f + 11g (t)) linking μ1 μ12 as
1 (1) def ((1 L)T + (T v,
1].
(11)
The related generalized Wasserstein mean corresponds to = 0.5 and is denoted 11-2
Intuitively, the optimal transport maps between and μs. i 1,2 give rise to sub-optimal transport map between μl and μ2:
T def Tu- o T with (T!+ #11
= //2-
(12)
One can be interested in the cost induced by the transportation of μ1 to μi via the transport map T! known the y-based Wasserstein distance [77 and defined as
/ -
(31,
(1)
v). (13)
Notably, the second part of Eq. 13 straddles the square Wasserstein distance with Eq. 3 Re-
markably, the computation of W can be efficient if the pivot measure is chosen appropriately. As established in Lemma 4.6) it is the case when u is supported on a line. Based on these facts, we propose hereafter alternative formulation of SWGG.
Definition 4.1 (Pivot measure). Let μy and μl2 E P (RR). We restrict the pivot measure u to be the Wasserstein mean of the measures Q and u2:
14
1-+2 def
arg min (Rd)
W. (Q² # #1, p)) W Q2p2).
5

---

where 0 E S and Q" Rd - R x - 0(2, f) is the projection onto the subspace generated by 6. 22 is always defined as the middle of a geodesic as in Eq
Moreover Pg ++2
One shall notice that Q and Q are supported on the line defined by the direction 8, so the pivot measure / - 1b 2 We are now ready to reformulate the metric SWGG.
Proposition 4.2 (SWGG based on generalized geodesies). Let 0 E S M1, /22 E P2 (R4) and p be the pivot measure. Let (' be the generalized Wasserstein mean between μr and #2 P2 (R4)
with pivot measure 11) 22 Then,
SWGG U2, 0) = 2W2 (M1, un -2)
(ub - (2)) - 2 11 2
(14)
The proof is in Supp 10.1 From Proposition 4.2 SWGG is the -ba-dd Wasserstein dis-
tance between (41 and P2. This alternative formulation allows establishing additional properties
of min-SWGG.
4.2 Theoretical properties
Additionally the properties derived in Section (SWGG is distance and min-SWGG is upper bound of W we provide below other theoretical guarantees.
Proposition 4.3 (Weak Convergence), min-SWGG metricizes the weak convergence in P3 (RR). In other words, let (pR)keN be a sequence of measures in P (RR) and μ E P2 (R5). We have:
min-SWGG
where L.3 stands for the weak convergence of measure i.c. S fduu + STe fdp for all continuous bounded functions
Beyond the weak convergence, min-SWGG possesses the translation property, i.e. the translations can be factored out as the Wasserstein distance does (see [53] remark 2.] for recall).
Proposition 4.4 (Translation). Let T (resp. 7") be the map + (resp. æ x v), with u, v vectors of IRd. We have:
min- STG,
= min-SWGG (annSSWGG3(L1, (22 + l|u - 0112 - 2(u v. m2 m2)
where mi = -ga addu (z) and m2 Je ad) are the means of μr, 112-
This property useful in some applications such as shape matching, which translation invariances sought.
The proofs of the two Propositions are deferred Supp. 10.2 and 10.3
Remark 4.5 (Equality). min-SWGG and W3 equal in different cases. First, 43 showed that it
the case whenever f4 the shift and scaling of #12 (see Supp. 9.1 for full discussion). In Lemma will state that it is also the case if one of the two distributions is supported line.
4.6
4.3
Efficient computation of SWGG
SWGG defined in Eq. [4 involves computing three WDs that are fast to compute, with an overall O(dn + log n. complexity, detailed below. Building this result, we provide optimization scheme that allows optimizing over 8 with O(sdn + sn log sn) operations at each iteration, with s (small) integer. We first start by giving new closed form expression of the WD whenever one distribution is supported on a line, that proves useful for deriving an efficient computation scheme.
New closed form of the WD. The following lemma states that W (11, (1)) admits closed form whenever μز is supported on a line.
This lemma leverages the computation of the WD between #22 and the orthogonal projection of yn onto the linear subspace defined by the line. Additionally, it provides an explicit formulation for the optimal transport map T12

---

Lemma 4.6. Let Pl, A2 in P2 (RR) with #2 supported on line of direction & E Sd-1, We have:
W2(,) (i 24 /4) W 1 (1)
(15)
with Q" as in Def. 4.1 Note that ( 23 - = ||:
Q" (xx)) and (2 ( 41 H2)
= ( #/1,, P (22) are the WD between 1D distributions. Additionally, the optimal transport map is given by 71-+2 T9 TH- m Q". In particular, the map 71 can be obtained via the permutations of the ID distributions ps and p The proof is provided in Supp. 10.4
Efficient computation of SWGG. Eq. (14) is defined as the Wasserstein distance between distri- bution (either μ4 or μl or m362 and a distribution supported on a line (ub-+2). As detailed in Supp. 10.5] computation of Eq. (14) involves three Wasserstein distances between distributions and their projections: i) W (Mi, Q dt (1), ïi) (22 (z iii) W (ug.7 Mg - and a one dimensional Wasserstein distance W2 (Pá
( Pd (2)), resulting in a O(dn + log m) complexity.
The term W2 g.0 1ub 2 in Eq. 14 is not continuous w.r.t. Indeed, the generalized mean u/1²² depends only on the transport maps T T and pu-->2-pp which remain constant as long as different projection directions 0 lead to the same permutations de and Tq. Hence, rely smooth surrogate 1 of the generalized mean and aim to minimize the following objective function:
Optimization scheme for min-SWGG.
(2,, def (w1, +2) + 2W2 +2, 22))) - 4W2 (ug,0" 14 2
(16)
To define 2 one option would be to entropic maps in Eq. 11 but at the price of a quadratic
time complexity. We rather build upon the blurred Wasserstein distance 26 to define 14 as can be seen as an efficient surrogate of entropic transport plans in 1D. one dimensional setting, "000 can be approximated efficiently by adding an empirical Gaussian noise followed by a sorting pass. In our case, it resorts in making s copies of each sorted projection pd (I=(1)) and Pa (V)) respectively, to add an empirical Gaussian noise of deviation vE/2 and to compute averages of sorted
blurred copies xir, n We finally have (p),²2) = 1 Σ -==(i-))++ (²)()) + vー))))) 126 showed 2s
is
that this blurred WD has the same asymptotic properties as the Sinkhorn divergence.
The surrogate SWGG #2, 0) is smoother w.r.t. 0 and can thus be optimized using gradient descent, converging towards local minima. Once the optimal direction 0* is found, min-SWGG resorts to be the solution provided by SWGG(H1 M2, 0*). Fig. 2 illustrates the effect of the smoothing on
toy example and more details are given in Supp. 10.6 The computation of SWGG(u1, #2, 0) is summarized in Alg.
Algorithm 1 Computing SWGG? (H1, M2,
Require: A1 = Σ 8e., M22 = Σ 8g 0 gd-1, s E N4 and c E R+
o. + ascending ordering of (Po (z:)),. (Q.():)),
x² + s copies of (Io(i)) ), 3² + s copies of (3+())
o², 7 + ascending ordering of (z", 0) + E. (yr" 0) + + for & ~ N(O,, Vi vi sn
a + 2 E, (1|a: (2:)) 11 - (v))))
b 2w, 22.z) ) + 222 (12, Q
b+ Σ, (2) + pd (2+
> 22W p2P22)
c 1 Σ
Q2 (F(()))
Σ
(x (x)*()) + y y 112 4W3 (p) ,10 22)
25
k= Dsst1
Output a bb-c
7

---

DeneraFiedd Wasserstein mien
Smooth gooo and Wassersten moat
// AJ2 SP
SWOG
SWGG
Figure 2: Illustration of the smoothing effect in the same setting as in Fig. (Left) Two sets of generalized Wasserstein means are possible, depending on the direction of the sampled line w.r.t 8 and 82. giving rise to different values for SWGG. (Middle) The surrogate provides a smooth transition between the two sets of generalized Wasserstein means as the direction & changes, (Right) providing smooth approximation of SWGG that is amenable optimization.
5 Experiments
We highlight that min-SWGG is fast to compute, gives an approximation of the WD and the associated transport plan. We start by comparing the random search and the gradient descent schemes for finding the optimal direction in subsection 5.1] Subsection [.22 illustrates the weak convergence property of min-SWGG through gradient flow application to match distributions. We then implement an efficient algorithm for colorization of gray scale images in [..]] thanks to the new closed form expression of the WD. We finally evaluate min-SWGG
shape matching context in subsection 5.44 When possible from the context, we compare min-SWGG with the main methods for approximating the WD namely SW, max-SW, Sinkhorn [3], factored coupling (29 and subspace robust WD (SRW)
[52]. Supp. I1 provides additional results the behavior of min-SWGC and experiments other tasks such as color transfer or on data sets distance computation. All the code is available at
5.1 Computing min-SWGG
Let consider Gaussian distributions in dimensions d E {2, 20, 200}. We first sample n = 1000 points from each distribution to define μul and μ22- We then compute (i (22) computed using different schemes, either by random search, by simulated annealing (54] by gradient descent. We report the obtained results Fig. 3 (left). For the random search scheme, we repeat each experiment 20 times and we plot the average value of SWGG = 2 times the standard deviation.
For the gradient descent, we select random initial We observe that, in low dimension, all schemes provide similar values of min-SWGG. When the dimension increases, optimizing the direction 0 yields a more accurate approximation of the true Wasserstein distance (see plots' title in Fig. 3). On Fig. (right), we compare the empirical runtime evaluation for min-SWGG with different competitors for d = and using n samples from Gaussian distributions, with n {102, 10 10a, 5 x 10 10%).
We observe that, as expected, min-SWGG with random search is as fast as SW with super linear time complexity. With the optimization process, it is faster than SRW for a given number of samples. We also note that SRW is more demanding in memory and hence does not scale well miG-SWGG. We give more details on this experimentation and comparison with competitors in Supp. I1.2
Doup kng
SWG3, L-250
Wassersich Sinkmom
SPV
W/ 28966.0
man-SWGG optin
15.0
random search optimired
1..
$4.52
armenling
2740
$4.02
177
38.3
3000
3500
300
2042
9030
10
1000
10
1000
Number projection
Number samples each das butoon
Figure 3: (Left) evolution of miG-SWGG with different numbers of projections and with the dimension in {2, 20, 200}. (Right) Runtimes.
https://ggthub..co//aalayy/////
8

---

5.2 Gradient Flows
We highlight the weak convergence property of min-SWGG, Initiating from random initial distribu- tion, we aim to move the particles of a source distribution μ1 towards a target one μ2 by reducing the objective min-SWGG (m,, M22) at each step. We compare both variants of min-SWGG against SW, max-SW and PWD, relying the code provided in [37] for running the experiment; the results on Fig. 4 We consider several target distributions, representing diverse scenarios and fix 100. We run each experiment 10 times and report the mean the standard deviation. In every case, one can see that moves towards μl2 and that all methods tend to have similar behavior. One can notice though that, for the distributions in d 500 dimensional space, min-SWGG computed with the optimization scheme leads to the best alignment of the distributions.
report
SW
max-SW
min-SWGG trandom search)
mi-SwGG (oplim)
PWD
196
106
175
Ierations
Logu WW)
Gaussian 500d
Ano -e Edtt Number Ieerttoon
100
Loa
300
Figure 4: Log of the WD between different source and target distributions as a function of the number of iterations.
5.3
Gray scale image colorization
Lemma 4.6 states that the WD has a closed form when one of the distributions is supported on a line, allowing particular situation arises for instance with RBG images (Mi /2 E PT (R*)), where black and white line (the line of grays). One can address the problem of image colorization through color transfer [25). where a black and white image is the source and colorful image the target. Our fast procedure allows considering large images without sub-sampling with a reasonable computation time. Fig. | gives an example of colorization of an image of size 1280x 1024 that was computed in less than 0.2 second, while being totally untractable for the O log n) solver of WD.
compute the WD and the OT map with complexity of O + log... This
images are supported
Daget mage
Tapeling
Figure 5: Cloud point source and target (left) colorization of image (right).
This procedure can be lifted to pan-sharpening (64] where one aims construct a super-resolution multi-chromatic satellite image with the help of a super-resolution mono-chromatic image (source) and low-resolution multi-chromatic image (target). Obtained results are given in the Supp. 11.4
5.4 Point clouds registration
Iterative Closest Point (ICP) is an algorithm for aligning point clouds based on their geometries (7]. Roughly, its most popular version defines one-to-ons correspondence between point clouds, computes a rigid transformation (namely translation, rotation or reflection). moves the source point clouds using the transformation, and iterates the procedure until convergence. The rigid transformation is the solution of the Procrustes problem i.e. arg min (or) || - t) Y 1/.. where X, Y are the source and the target cloud points and (dd) the space orthogonal matrices of dimension d. This Procrustes problem can be solved using SVD [59] for instance.
We perform the ICP algorithm with different variants to compute the one-to-one correspondence: neareast neighbor (NN) correspondence, OT transport map (for small size datasets) and min-SWGG

---

transport map. Note that SW, PWD, SRW, factored coupling and Sinkhorn cannot be run in this context where a one-to-one correspondence mandatory: subspace detours 44 are irrelevant in this context (see Supp. 11.5). We evaluate the results of the ICP algorithm in terms of: i) the quality of the final alignment, measured by the Sinkhorn divergence between the re-aligned and target point cloud; ii) the speed of the algorithm given by the running time until convergence. We consider 3 datasets of different sizes. The results are shown in Table I and more details about the setup, can be found in Supp. 11.5 In Supp. 11.5 we give deeper analysis of the results, notably with different criteria for the final assignment, namely the Chamfer and the Frobenius distance. One can see that allows working with
the assignment provided by OT- methods is better than NN.
large datasets, while OT fails to provide a solution for n 150000.
Souce
π2 NN OT min-SWGG
500
3000
150 000
Target
3.54 (0.02)
96.9 (0.30)
23.3 (59.37)
0.32 (0.
48.4 (58.46) 46)
0.05 (0.04)
37.6 (0.90)
6.7 (105.75)
Table 1: Sinkhorn Divergence between final transformation on the source and the target. Timings in seconds are into parenthesis.
Best values are boldfaced. An example of a point clouds (n 3000) is provided on the left.
Conclusion
In this paper, we hinge on the properties of sliced Wasserstein distance and on the Wasserstein generalized geodesics to define min-SWGG, a new upper bound of the Wasserstein distance that comes with an associated transport map. Topological properties of SWGG are provided, showing that it defines metric and that min-SWGG metrizes the weak convergence of measure. We also propose two algorithms for computing min-SWGG, either through random search scheme or a gradient descent procedure after smoothing the generalized geodesics definition of min-SWGG. We illustrate its behavior in several experimental setups, notably showcasing interest applications where transport map is needed.
The set of permutations covered by min-SWGG is the one induced by projections and permutations on the line. It is a subset of the original Birkhoff polytope and it would be interesting to characterize how these two sets relates. In particular, in the case of empirical realizations of continuous distributions, the behavior of SWGG, when grows, needs to be investigated. In addition, the fact that min-SWGG and WD coincide when d 2n calls for embedding the distributions in higher dimensional spaces to benefit from the greater expressive power of projection onto the line. Another important consideration to establish theoretical upper bound for min-SWGG.
Acknowledgments
The authors gratefully acknowledge the financial support of the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CHIA-00211011 (project RAIM grant ANR -0--20- 0030 (project OTTOPIA) and grant ANR-18-CE22 ANR-I8-CE23-0022-01 (project MULTISCALE), Clément Bonet is supported by the project DynaLearn from Labex Comin and Région Bretagne ARED DLearnMe.
https://chaire-raatn www.taiirrr..rri..ig.tu.........
10

---

References
[1] Alcksandr Danilovich Alexandrov. theorem on triangles metric space and some of its applications. Trudy Mat. Inst. Steklov, 38:5-23, 1951.
[2] Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approxima- tion algorithms for optimal transport via sinkhorn iteration. Advances in neural information processing systems, 30, 2017.
[3] David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21428-216 2020.
[4] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science Business Media, 2005.
[5] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214 PMLR, 2017.
[6] Arturs Backurs, Yihe Dong, Piotr Indyk, lyy Razenshteyn, and Tal Wagner. Scalable nearest neighhor search for optimal transport. International Conference on Machine Learning, pages 497-506. PMLR, 2020.
[7] Paul J Besl and Neil D McKay. Method for registration of 3-d shapes. In Sensor fusion IV: control paradigms and data structures, volume 1611, pages 586-606. Spie, 1992.
[8] Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A, 5:147-154, 1946.
[9] Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38(4):1-33, 2019.
[10] Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasser- stein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(():22-45, 2015.
[11] Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia conference, pages 1-12, 2011.
[12] Yann Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on pure and applied mathematics, 44(4):375-417, 1991.
[13] Giuseppe Buttazzo, Guillaume Carlier, and Katharina Eichinger. Wasserstein interpolation with constraints and application to parking problem. arXiv preprint 11XX1:22077.1261,, 2022.
[14] Luis A Caffarelli. Monotonicity properties of optimal transportationf] and the fkg and related inequalities. Communications in Mathematical Physics, 214(3):547-563, 2000.
[15] Lactitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applica- tions unlable- learning. In Advances in Neural Information Processing Systems, volume 33, pages 2903-2913, 2020.
[16] Rui Chibante. Simulated annealing: theory with applications. BoD-Books on Demand, 2010.
[17] Tarin Clamuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. In Neural Information Processing Systems Machine Learning for Creativity and Design Workshop, 2018.
[18] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending MNIST to handwritten letters. 2017 international joint conference on neural networks
(IJCNN), pages 2921 -226,, 2017.
[19] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy, Optimal transport for domain adaptation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 39(9):1853-1863 2017.
11

---

[20] Thomas M Cover. The number of linearly inducible orderings of points in d-space. SIAM Journal on Applied Mathematics, 15(2):434-44 439, 1967.
[21] Katy Craig. The exponential formula for the wasserstein metric. ESAIM: Control, Optimisation and Calculus of Variations, 22(1):169 (((1):169-18))) 187, 2016.
[22] JA Cuesta-Albertoss C. Matrán, and Araceli Tuero-Diaz. Optimal transportation plans and convergence in distribution. journal of nultivariate analysis, 60(1):72-83, 1997.
[23] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[24] Ishan Deshpande, Yuan-Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander G Schwing. Max-sliced wasserstein distance and its use for gans. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11648-10656 2019.
[25] Sira Ferradans, Nicolas Papadakis, Julien Rabin, Gabriel Peyré, and Jean-François Aujol. Regularized discrete optimal transport. In International Conference on Scale Space and Variational Methods in Computer Vision, pages 428 439. Springer, 2013.
[26] Jean Feydy. Geometric data analysis, beyond convolutions. PhD thesis, Université Paris-Saclay Gif-sur- Yvette, France, 2020.
[27] Jean Feydy, Thibault Séjourné, François- Xavier Vialard, Shun-ichi Amari, Alain Trouve, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. The 22nd International Conference on Artificial Intelligence and Statisticy, pages 2681-2690, 2019.
[28] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. POT: Python Optimal Transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
[29] Aden Forrow, Jan annCChistiian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2454-2465. PMLR, 2019.
[30] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso Poggio. Learning with a wasserstein loss. Advances in neural information processing systems, 28, 2015.
[31] Wilfrid Gangbo and Robert J McCann. The geometry of optimal transportation. Acta Mathe- matica, 177(2):13-161,, 1996.
[32] Jonathan Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550-554, 1994.
[33] Leonid V Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, pages 199-201, 1942.
[34] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, 24(7):881-892, 2002.
[35] Young- Young-Heon Kim, Brendan Pass, and David J Schneider. Optimal transport and barycenters for dendritic measures. Pure and Applied Analysis, 233):581-601, 2020.
[36] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario Vecchi. Optimization by simulated annealing. science, 220(4598):671-688, 1983.
[37] Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Gener- alized sliced wasserstein distances. Advances in neural information processing systems, 32, 2019.
12

---

[38] Matt Kusner, Yu Sun. Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document distances. In International conference on machine learning, pages 957-966. PMMR, 2015.
[39] Yann LeCun. The MNIST database of handwritten digits. http://yann. lecun, com/exdb/mnistl, 1998.
[40] Tianyi Lin, Zeyu Zheng, Elynn Chen, Marco Cuturi, and Michael Jordan. On projection robust optimal transport: Sample complexity and model misspecification. In International Conference on Artificial Intelligence and Statistics, pages 262-270, 2021.
[41] Quentin Mérigot, Alex Delalande, and Frédéric Chazal. transport maps and lincarization of the 2-wasserstein space. In International Conference on Artificial Intelligence and Statistics, pages 3 3186-3196, 2020.
Quantitative stability of optimal
[42] Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., pages 666-704, 1781.
[43] Caroline Moosmüller and Alexander Cloninger. Linear optimal transport embedding: Provable wasserstein classification for certain rigid transformations and perturbations. Information and Inference: A Journal of the IMA, 12(1):363-389 2023.
[44] Boris Muzellec and Marco Cuturi. Subspace detours:
Building transport plans that are optimal on subspace projections. Advances in Neural Information Processing Systems, 32, 2019.
[45] Kimia Nadjahi, Alain Durmus, Lénaic Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Simsekli. Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33, 2020.
[46] Kimia Nadjahi, Alain Durmus, Pierre E Jacob, Roland Badeau, and Umut Simsekli. Fast approximation of the wasserseen distance using concentration random projections. 2021.
Advances in Neural Information Processing Systems,
[47] Luca Nenna and Brendan Pass. Transport type metrics on the space of probability measures involving singular base measures. Applied Mathematics & Optimization, 87(2):28, 2023..
[48] Peer Neubert and Peter Protzel. Compact watershed and preemptive slic: On improving trade- offs of superpixel segmentation algorithms. In 2014 22nd international conference pattern recognition, pages 996-1001. IEEE, 2014.
[49] Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Distributional sliced-ward wasserstein and applications to generative modeling. In International Conference on Learning Representations, 2021.
[50] Khai Nguyen, Tongzheng Ren, Huy Nguyen, Litu Rout, Tan Nguyen, and Nhat Ho. Hierarchical sliced wasserstein distance. arXiv preprint arXiv:2209.1335 2022.
[51] Felix Otto. The geometry of dissipative evolution equations: the porous medium equation. Communications in Partial Differential Equations, 26(1-2):101-174, 2001. 2001.
[52] François- Pierre Paty and Marco Cuturi. Subspace robust wasserstein distances. In International conference on machine learning, pages 5072-5081, 2019.
[53] Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 11(5-6):355 607, 2019.
[54] Martin Pincus. A monte carlo method for the approximate solution of certain types of constrained optimization problems. Operations research, 126551225- 1970.
[55] Julien Rabin, Sira Ferradans, and Nicolas Papadakis. Adaptive color transfer with relaxed optimal transport. In IEEE international conference on image processing (ICIP), pages 4852- 4856, 2014.
13

---

[56] Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Berno.. Wasserstein barycenter and its application texture mixing. In Alfred M. Bruckstein, Bart M. ter Haar Romeny, Alexander M. Bronstein, and Michael M. Bronstein, editors, Scale Space and Variational Methods in Computer Vision, pages 435 446, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg.
[57] Mark Rowland, Jiri Hron, Yunhao Tang, Krzysztof Choromanski, Tamas Sarlos, and Adrian Weller. Orthogonal estimation of wasserstein distances. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 186-195. PMLR, 2019.
[58] Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58- 63):94, 2015.
[59] Peter H Schönemann. generalized solution of the orthogonal procrustes problem. Psychome- trika, 31(1):1-10, 1966.
[60] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borg- wardt. Wasserstein weisfeiler-lehman graph kernels. Advances Neural Information Processing Systems, 32, 2019.
[61] Stefan Van der Walt, Johannes L Schönberger, Juan Nunez-Iglesias, François Boulogne, Joshua Warner, Neil Yager, Emmanuelle Gouillart, and Tony Yu. scikit-image: image processing in python. PeerJ, 2:e453, 2014.
[62] Peter JM Van Laarhoven, Emile HL Aarts, Peter JM Laarhoven, and Emile HL Aarts. Simulated annealing. Springer, 1987.
[63] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[64] Gemine Vivone, Mauro Dalla Mura, Andrea Garzelli, and Fabio Pacifici. A benchmarking protocol for pansharpening: Dataset, preprocessing, and quality assessment, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 14:6102-611 2021.
[65] Wei Wang, Dejan Slepčev, Sauray Basu, John A Ozolek, and Gustavo K Rohde. A linear optimal transportation framework for quantifying and visualizing variations in sets of images. International journal of computer vision, 101(2):254 269, 2013.
[66] Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):2620-2648 2019.
[67] Han Xiao, Kashif Rasul, and Roland Vollgraf. mushion-mnist a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1eX8v:170.007444 2017.
[68] Jingyi Zhang, Ping Ma, Wenxuan Zhong, and Cheng Meng. Projection- techniques for high-dimensional optimal transport problems. Wiley Interdisciplinary Reviews: Computational Statistics, 15(2)xe1577, 2023.
14

---

7 Proofs and supplementary results related to Section 3
7.1 Overestimation of WD by PWD
As stated in Section 2 the projected Wasserstein distance PWD (see Eq. 7 tends overestimate the Wasserstein distance. This is due to the fact that some permutations dg and Ty (with 0 E 1 involved in PWD computation may be irrelevant. Such situation occurs when the distributions are in high dimension but supported on a low dimensional manifold or when the distributions are multi-modal.
Let consider the distributions μ4 and μl2 lying on a low dimensional manifold. In high dimension, randomly sampled vectors 9 tend to be orthogonal. Moreover, vectors orthogonal to the low dimen- sional manifold lead to "collapsed" projected distributions P and p H2 onto Hence, such projection directions lead to permutations that can be randomly chosen. To empirically illustrate this behavior of PWD, we consider μ4l and (22 Gaussian distributions in R d = 10 but supported on the first two coordinates and we sample 200 points per distribution. Table 2 summarizes the obtained corresponding distances and shows that PWD overestimates the WD.
Now, let us consider two multimodal distributions μl, P2 with K clusters such that each cluster of μ1 has close cluster from μl2 (cyclical monotonicity assumption). Also we assume the same number of points in each cluster. OT plan will match the corresponding clusters and will lead to a relatively low value for W22 (since cluster from μl1 has a closely related cluster in (22). However as PWD may allow permutations that make correspondences between points from different clusters (since source cluster and a target cluster can be far in the original space but very close when projected on ID), the resulting distance will be much more larger, leading an overestimation of the Wasserstein distance. Table 2 provides an illustration for K 10 clusters and d = 2.
Table 2: Values of W3, PWD and miG-SWGG on two toy examples. PWD samples 0 uniformly over 5d-1; PWD Orthogonal Projections seek orthogonal vectors (see [57] for more details) Multi-modal Low dimensional manifold
Distributions
W
12
12
PWD Monte-Carlo
54
29
PWD? Orthogonal Projections
54
min-SWGG?
13
7.2 Quantile version of SWGG
The main body of the paper expresses SWGG for empirical distributions μl and μi with the same number of points and uniform probability masses. In this section we derived SWGG in more general setting of discrete distributions.
Let remark that min-SWGG relies on solving a optimal transport (OT) problem. So far, the ID OT problem was derived for /4 E 'D (R) and thus was expressed using the permutation operators 7 and Ø. In the general setting of distributions b4 (P) and μ4 E PTr(R) with n o m, the ID optimal transport is computed based on quantile functions. Hence, the expression of SWGG in the general setting of μ Pg (R) and μı PTT(R) (R) hinges on quantile functions instead of permutations.
More formally, let μ E PP (R); its cumulative function defined as:
Fg : R - [0, 1] x x f dp
(17)
and its quantile function (or pseudo inverse), is given by:
In [0, 1] + R. r min(x E RU(-~0) s.t. Fx(x) 2 r}
(18)
An important remark is that the quantile function is a step function with (the number of atoms) discontinuities. Thus, can be stored efficiently using two vectors of size n (one for the locations of the discontinuities and the other for the values of the discontinuities)
15

---

For μl E (R) and μ22 E (R), we recover the Wasserstein distance through quantiles with:
(21, = Jo² 19m (r) quz (r)
(19)
Moreover, the optimal transport plan is given by:
(gaz 4ua) ( A1o,1]
(20)
where A[o.1] is the Lebesgue measure on [0, 1]. The transport plan can be stored efficiently using two vectors of size (n + m 1) (see [53] Prop 3.4).
Following [53] Remark 9.6], one can define the quantile function related to the Wasserstein mean by:
qu-02 = 2 9m1 + 2 902
(21)
Now, let μn E (RR) and E (R"). Let n3--2 be the Wasserstein mean of the projected
distributions on 0. Finally let 9- denote the transport plan from u/2-2 to and π be the transport plan from ng- to f2z. Following the construction 4 Sec. 9.2], we shall introduce a multi marginal plan defined
E P22(R" x IRd x Rd) s.I. PH π
0-11
P π
1- 0 0-+ and E MT))) ,1, ,1,22)
(22)
where p12 (RR))3 + 2 projects to the first two coordinates and pl3 projects to the coordinates I and 3. In particular, 212 is the projection of т its 2 first marginals and p1ar x the first and 3rd marginal. Similarly to the 2-marginal transport plan we defined [
[0 un, (1, = (m E Pa (RR x
Rd (Rd) s.t. π (A IRd x Rd) = 1b (A). x (Rd A, xR = PI (A) and (R(2 Rd A) 1 (A),
AA measurable set of Rd
1-2 is then defined as: The generalized barycenter M9.8
11 = (1 p2
1 +
p3 x
(23)
2
2
where pi is the projection on the i-th coordinate.
We finally have all the building blocks to compute SWGG in the general case. Let remark that the complexity goes from O(d + n n) in the P7z (Rd) case to Oddnn + m) + (n + m) log(n + m))
in the general case.
7.3 Proof Proposition
3.2
We aim to prove that (WGG)2M1, M2, 0) is upper bound of WW3,,, and that SWGG(H1, 0) is a distance v0 E Sd-1 , (Rd) 1,2.
Distance.
Note that this proof will be derived for the alternative definition of SWGG in supp. 10.8
Let μ4 = - Se., 122 1. Σ 8y, M3 + dz. be in (2 let 0 E sd-1, We note (resp. 0) (resp. (Br 0) s s
T and T) the permutation such that (Ix(1), 0) S S
... ..))) f) and (zæ(1). 8) f ... S ...( 8)).
Non-negativity and finite value. From the lg norm, is derived
Symmetry. SWGG)(u1. 0) = 1 Σ, |(o(())))))
v-an12 = 1 Σ, 11760) - 22 =
(P2,
Identity property. From one side, fn = 112 implies that (r,, 0) = (y), 0) VI Si n and that a = T,
which implies SWGG2 #2, ()) =
From the other side, SWGG P2, 0) v1 < S
1 Σ [x((i) v- 113 = 0 Iz(() リr(1**
#1 = U2.
16

---

1/2
Triangle Inequality.
We
have
SWGG2(m1 (11: (2,
(+ [[ y yr(0)
2 Σ, (i(())
+ E, (m(() + vr(0) l13
1/2
[ (x00()) =x(0)1 1/2
1/2
Σ (+) (r(1) 11
SWGG U3. 8) SWGG2(M3. M2, 0)
Upper Bound The fact that min-SWGG; in upper bound of W3 comes from the sub-optimality of the permutations Fg, Ta- Indeed, they induce a one-to-one correspondence (t) - (4)
v1 < i S n. This correspondence corresponds transport map 7 such that T μ22 Since
W3- infT Tem=ue Σ x (=)) we necessarily have W3 I min-SWGG
Equality The equality W min-SWGG whenever d 2n comes from the fact that all the permutations are within the range of SWGG. In particular minimizing SWGG is equívalent to solve the Monge problem. We refer to Supp. [1.] for more details.
7.4 Difference between max-SW and min-SWGG
Herein, we give an example where the selected vectors for max-SW and min-SWGG differ.
(-10)
10
Let M1, 122 PP(R2) be an empirical sampling of Amm1, E1) and of (m,,, Σ2) with m²
= 10
2 0
() 11 and Σ2
0
2 0
2
0 2
Since these two distributions are far away on the z-coordinate, max-SW will catch this difference
1
between the means by selecting 0 ~=
0
Indeed, the projection on the s-coordinate represents the
largest ID WD.
()) that separates the
Conversely, min-SWGG selects the pivot measure to be supported on 0 as
two distributions. Indeed, this direction better captures the geometry of the distributions, delivering permutations that are well grounded to minimize the transport cost.
Fig. illustraaee that difference between max-SW and min-SWGG.
min-sWGG
max-SW
Figure 6: Optimal 0 for max-SW and min-SWGG
7.5 From permutations to transport map
In this section provide the way of having transport map from permutations.
Let μr, #2 E P2 (Rd), let 0* E arg min SWGG and let ae To- the associated permutations. The associated map must be T(x.()) Vr(i) V1 < i < In the paper, we formulate the associated transport map as:
T(x;) = y (ap-
( (0)
VI visian
(24)
17

---

Moreover, the matrix representation of T is given by: fo
To
(25)
otherwise
7.6 Examples of Transport Plan
Fig. 7 iillustrates instances of the transport plan obtained via min-SWGG, Even though these transport plans are not optimal, they were able to capture the overall structure of the true optimal transport plans.
Tranezertpin -1.2
Thesper: plan mi 5U10-11
Tranpan par Naturath W3
Tarepor par me SWS0-8.
Figure 7: Example of transports plan given by Wasserstein (left and middle-right) and min-SWGG (middle left and right). Transport plan distribution (top) and transport matrix (bottom). The relative distances between source and target are given in the title.
The first example shows that the OT plan by min-SWGG exhibits "block" structure, and thus approximates well the true Wasserstein distance. The second example shows that even context of superimposed distribution the "general transport direction" in min-SWGG is representative of that of the optimal transport map.
8 Background on Wasserstein Generalized Geodesics
We introduce some concepts related the Wasserstein generalized geodesics in Sec. 4. In this section, we provide more details about these geodesics in order to provide wider view on this theory.
In the following definitions, we do not address the issue of uniqueness of the geodesics. However this a problem our setup since we focus our study on pivot measure with n-atoms E Pg (R*). In this case, we have uniqueness of the y-based Wasserstein distance 47
Wasserstein generalized geodesics As mentioned in Sec. 4.1 Wasserstein generalized geodesics rely on pivot measure v E ' (Rd) to transport la to /12. Indeed, one can leverage the optimal transport maps Th and T construct curve linking μh to /22 The generalized geodesic with pivot measure is defined as:
(1) ((1 T + (T"
VI E [0.
(26)
The generalized Wasserstein mean refers the middle of the geodesic, i.e. when 0.5 and has been denoted 1 1-+2
Intuitively, the optimal transport maps between and pi; i 1,2 give rise to sub-optimal transport map between μl and through:
T1-2 del Tu- o -2 with (T) (2 #1z F2.
(27)
18

---

T links to 22 via the generalized geodesic:
H (t) = ((1 - -)dd + +T ) #1
(28)
We recall here the based Wasserstein distance induced by T T and introduced Eq.
Definition 8.1. The v-based Wasserstein distance [2] is defined as:
W (M1, def
J
{ x - T -
( (x) (2)d4u
(29)
(T TV (z) (2)
(30)
Moreover, this new notion of geodesics comes with inequality, which is of the opposite side Eq. 3 ( s (1 (1--t)000 (1-t) + WW3 (v, p2) - +(1 -)W (11 p2).
(31)
The parallelogram law respected but straddles with eq. (3) and eq. We refer Figure for an intuition behind positive curvature [51], parallclogram law and generalized geodesics.
y
p1
(2()))
f22
01
P2
[x +
t)
Mg (1-)(())
Figure 8: Geodesic (IId + (1 (----+))+++++- #141 and generalized geodesic (LId + 1)T
# in
Wasserstein space (Left and Right) in dashed line and parallelogram law in Rd (middle).
Setting & 0.5 in Eq. 31 and reordering the term gives:
W (21,)2) - 2 + 2W3 (v, p2)
(32)
Moreover one can remark that:
(ML, #2) = 2W2 (11, v) 2w (u)
(33)
In particular situations W and W coincide. It is the case for ID distributions where the Wasserstein space is known be flat [4] In that case, the Wasserstein mean and the generalized Wasserstein mean are the same.
Multi-marginal Another formulation of the v-based Wasserstein distance is possible through the perspective of multi-marginal OT Let IT(11 H2, v) { s.t. p 1112 p13
n. 1- and p23 = 2 where pi is the projection onto the coordinates i. Let also II (14, be the space of optimal transport maps between μ4 and v. We have:
(3
inf xEIl(pp,aa.e) st. P "PB 1=1,2
| - v vI
(34)
Equation 34 expresses the fact that we select the optimal plan from 11( #2, v) which is already problem, since the
optimal for [1(,,, v). Mathematicallyy this minimization is not a optimal plan supposed be already optimal for some coordinate.
The set {I E I[H11, H2, v) s.t. pia т E II" (P; v) = 1,2} never empty, i.e. there is always existence of n!-²2 (thanks to the gluing lemma 63 page 23). Moreover, in situations where it is singleton, there uniqueness of m1-2. Uniqueness is an ingredient which overpasses the selection of final coupling and comes with additional result.
Lemma 8.2 (Lemma 6 47 Whenever (ニ E [[
PiST IT" u) i 1,2) is singleton, 3 is a proper distance. is a semi-distance otherwise.
Notably, ID pivot measure was studied in 35 to ensure a dendritic structure of the distributions along the geodesic.
19

---

Related Works
In this section we highlight the fact that several upper approximations of W2 in the framework of generalized geodesics. The differences lay in the choice of the pivot measure v.
Factored Coupling. In [29]. the authors impose a low rank structure on the transport plan by factorizing the couplings through pivot measure expressed as the k-Wasserstein mean between μ41 and μ/2 (k I n). is of particular interest since whenever the pivot distribution is the Wasserstein mean between μı and P2, W and W2 coincide.
Factored coupling results in problem of computing the --Wassesstinn mean (p' followed by solving two OT problems between the clustered Wasserstein mean and the two input distributions (M), 22) and (11 (12)) Even though the OT problems are smaller, they are still expensive in practice.
Moreover, in this scenario, the uniqueness of the OT plan T T2-+2 is not ensured. It appears that 22 chooses the most entropic transport plan, i.e simply T.) T2 Tu' pp o Th -pp""""""
Subspace Detours. From a statistical point of view, beneficial to consider optimal transport on a lower dimensional manifold [66]. In [44), authors compute an optimal transport plan Tuf - between projections
lower linear subspace E of bn and μ1, i.e. nf #E#pi, where Pr: the linear projection on E. They aimed at leveraging Tui-up to construct a sub-optimal map T between fl1 and (12-
The problem can recast as generalized geodesic problem with being the Wasserstein mean of "I and uz embedded in IRd, Once again, uniqueness of Tu--p is not guaranteed, authors provide two ways of selecting the map, namely Monge-Knothe and Kongee-nneepenent lifting.
Subspace detours result in a problem where one needs to select a linear subspace E (which is non convex procedure). compute an optimal transport between μ1 and #2 (in On log n) whenever dim E) > 1) and reconstruct T -22
Linear Optimal Transport (LOT). Given a set of distributions (4:) E PR LOT (65] embeds the set of distributions into the (2()-sce by computing the OT of each distribution to the pivot distribution. Mathematically, it computes Tw-p; V1 S and lies on estimating W2 (1s, (1)) with W (ps, P3)) through eq. (13)
In LOT, the pivot measure y chosen to be the average of the input measures (65, the Lebesgue measure on Rd [41] or an isotropic Gaussian distribution [43].
Instead of computing (z)) expensive Wasserstein distances, it resorts only on m Wasserstein distances
between (Jo)," and v. While significantly reducing the computational cost when several distributions
stake, does not allow speeding up the computation when only two distributions involved.
9.1 Linear Optimal Transport with shift and scaling
In this section, we recall the result from 43 The theorem states that the u-based approximation is very close to WD whenever #1, #2 are continuous distributions which are very close be shift and scaling of each other. It can applies to a continuous version of SWGG, however it works with discrete measures in the particular case of equality between W? and W3.
Theorem 9.1 (Theorem 4.1 43 Let A = {Sa (shift) a E Rd) U (Re (scaling) E R]. An,R = (h E A s.t. ||]] 2 R} and Gj,,R.- = {g E (2(Rd) 11) s.t. 3h E A s.t. llg - -hlp S [e
Let v. μr E P2(Rd), with u,v & X (the Lebesgue measure). Let 0,6
* For $1 E Gp.RR and X on convex compact subset of (Rd, we have:
W, (o o 1) W2(01 < Cc + 2c
(35)
20

---

If h and y satisfy the assumption of Caffarelli's regularity theorem [4], then for 91. 92 E R.o., we have:
W (1 92# W2(11# 92# S CC + Ce
(36)
where C, C' depdends v, a and R.
10
Proofs and other results related to Section 4
10.1
Proof of Proposition 4.2 equivalence between the two formulations of SWGG
In this section, we prove that the two definitions of SWGG in Def. 3.1 and Prop. 4.2 are equivalent. Let E Sd-1 be fixed.
From one side in Def.
3.1 we have:
1
( (1)
(37)
where og and Ta are the permutations obtained by sorting Pe pi and u2.
From the other side we note D(11, (2,0) 0) the quantity:
D(u P2, 0) def 2W2 (11, ub 2 2w2 (mb 1- p2) 4 (W2 140 2))
(38)
We want to prove that SWGG p2, 0) = (H1 M2, 0), V41, E P3z (RR) and 0 E Sd-1,
Eq. 13) in the main paper states that (111, M2, 0) is equivalent fga || 3 (x) 12 | (a:).
Finally, Lemma 4.6 states that the transport map T3 is fully determined by the permutations on the line: the projections part is one-to-one correspondence between and 0(r, 0) (resp. between y and (yy 0)). More formally TI - (Foo(1))
Vro(i)) v1 sis n. And thus we recover:
1 Σ |1000(0 (r0
| - T (x) (2)d)))))))
(39)
which concludes the proof.
10.2 Proof of Weak Convergence (Proposition 4.3)
We want to prove that, for sequence of measures (μK)REN E (RR),, we have:
M4 E (IR)) <> min-SWGG3((xe1)) -0
(40)
The notation μı 4.2 stands for the weak convergence in PT (Rd( ie. SRe (d))))))())) + Jga (x)ddp())) for all continuous bounded functions f and for the Euclidean distance f(x) =
| 2112 for all zo E Rd.
From one side, SinnSWGG? p)) +
= W2 ()) 0 -
#k μ. The first
implication is due to the fact that min-SWGG? is an upper-bounds of W3, the Wasserstein distance, and that WD metrizes the weak convergence.
E.2
From another side, assume j4k
μe we have for any 8:
1. Let p HN P2 (Rd) stands for the Wasserstein mean of the projections Q9 Quttr pa and Q and let 1 = Q2141 u. We have ut - converges towards (in law) to s which implies that:
(px, 10 (a) W2 10 : (2,
(41)
21

---

2. Since E (R((R), we have T m
Tu x (see
22
theorem 3.2). It
implies that - _ p and particularly:
W2 . 14g ()
(42)
By combining the previous elements, we get:
2W (W2 1o ~*) + 2W (1/ m4a 4W2 (12 (1 1,0000 =)
22W (1, 14 #)
2W 2 (11 + p4)
4W2 (11, 11g 11) = (43)
The previous relation shows that μk 43 implies SWGG 0) can conclude that:
0 for any 0. Hence, we
P4
min-SWGG3(H4s14) +
(44)
This concludes the proof.
Note that when μl and (22 are continuous, 41 proved that when the distributions are smooth enough
(i.e. respecting the Cafarelli theorem (14). there is bi-Holder equivalence between the y-based Wasserstein distance and W3. Hence, it still holds for SWGG for any A E 5d
W 12) SWGG P2, 02, B W (2),
Vpa P2(R*)
(45)
where B depends on js, E (1,2), 0 and the dimension d. This bound sufficient to prove that SWGG metrizes the weak convergence in this context. We refer to [1] for more details.
10.3 Proof of Translation property (Proposition 4.4
We prove that SWGG has the same behavior w.r.t. the translation as W3. This property is well known for Wasserstein and useful in applications such as shape matching.
Let Pr, H2 E P2 (R"), and let 7 (resp. T") be the map x + x u (resp. a + x U), with u, v
vectors of Rd.
To case the notations, let define ت1 = TW and Aá2 = M2
Let remind that in the case of Wasserstein distance we have [53 (Remark 2.19):
W (22) def (T u2) (11, 2(u v, m. -m²) + ||u v1/ (46)
with m Sea ædui (x) and m2 = Jiza xx))
We aim compute min-SWGG:((11, def
min Let express first
(P1, (2) = (M 2 - + 2 2ib -2) 4W 4 pb 22)
(47)
where ni is the Wasserstein mean of the projections along 0 of the shifted measures ja T M1 and j2 Thp2 as Proposition 2 The generalized Wasserstein mean - is defined accordingly
(see also Proposition 11).
We have:
W (b
W m1 (22 - 2(u,, m, -ms) + |/
(48)
where my = Sgs x (xx)
Similarly ( -22 W (#2 11/ +2) 2/v, m2 ma) + 1/21/2.
22

---

Let express now the third term in 47p. For that we require to define the generalized Wasserstein
mean 1 with pivot measure Bgg By the virtue of eq.
(II) in the main paper, we have:
1000²
T 0 -
= T
1
-
Mg
1-
(49)
2
$
32 -at Tub
Tuu 12 -p12 2
T -
12+22
(50)
(!rr
( -px + Tuà
T
#
118
1 1-
(51)
#
Hence, the third term in 47 is:
(m 2 W2 1-2 :
140 12) - u + v
+
12
ma) +
u + 0
(52)
2
2
2
since the mean of Wasserstein mean is the mean of my, m2-
Putting all together, have:
min-SWGG3 12) (in-SwGG3(u,,.a))
-4(u, m: -ma) 4(v, m2 -m3)
(53)
+ 8 u + v
mi + m2
m3
2
2
1 +
+ 2/|u||B [ + 2//2112 - -4
2
min-SWGGi3(41,
+4(u v, m3) - 4(u + v, m2) 4(u, m,) - 4(0, m2)
(54)
+ +44u + m2 + m2 + || - v 21
(Parallelogram law)
min-SWGG3(M1,mp) -2(u, m1) 2(m m2) + 2(u, m2) + 2(0, mi)
(55)
+ || 01/2
min-SWGG3(m -2(u U, mi m2) + ||u 012 (56)
10.4 Proof of the new closed form of the Wasserstein distance (Lemma 4.6
We recall and prove the lemma that makes explicit a new closed form for WD. Let μn, u2 be in P7 (Rd) with #s a distribution supported line whose direction is 0 5d-1, We have:
W (11 (2) W (u1, 22 + W Q (1,)1))
(57)
Moreover, the optimal map is given by 71-2 = T .22 o T +0 m
T 10-1--p o Q?.
Let pi,po u2 be in Pn (Rd) with #2 distribution supported line of direction 0. We have: (21, W3 (2QQ2
(58)
Moreover, the optimal map is given by:
1- = R2 T- 11 = -2 Q?
(59)
Here Q" is given in Def. 4.1 of the paper.
The proof of the Lemma was first inspired by 13 Proposition 2.3), where authors show that (M1, = W (μ1, u1) + W2 with C* C2 and C' some cost matrices with the con-
straints Cig min, Cl2 + C2
23

---

Let μl = -6 direction 0. Let 24 F = - dz E PR*).. We emphasize here the fact that the atoms of 1 and are supported on a line are denoted by the overline symbol.
6z. and μl = 3. be in (R((R) with μ2 distribution supported on a line with
From one side, have:
/ - T (x))ld)))
W2 (21)
inf Ta st. T
(60)
Rd
inf T s...
(1 (x) + 110 ( (a)
(61)
14 12 Ru
- > Q (2:))l
/ 1Q((ar) T (x)) (p2 (2)
inf T st T 1
(62)
11 I || - (xx))1))1841110 +
inf 7 Thuu
inf 73 st.
T 12 .
| - T (p)
(63)
W (11,72) P2)) (2
(64)
Equation 61 is obtained thanks the Pythagorean theorem since (a,, (z.). Di) is right triangle V1 < i S n. The equation (64) is obtained by taking the inf of the previous first term of the previous
equation.
From the other side:
/ Rd
(22, W (2))))2)
(
| (x) (x)
(65)
1 (x) (22
(66)
Rd
W2 (M1. U2)
W (21)
(67)
Where 3 and 7 are the optimal plan of W 1i and (2 Similarly, via the Pythagorean theorem. This concludes the proof.
65 is obtained
We plot an illustration of the lemma in Figure
Q"
(17-")
Pa
(Q")
Figure 9: Closed form for Wasserstein with Pythagorus theorem
10.5 Details on the efficient computation of SWGG
We decompose the second formulation of SWGG. Let first remind that Q" Rd + Rdd x 012,0 0) and pe Rd + RR, (ax, 0) are the projections the subspace generated by 0.
We have:
(WG, 0) = 2w3 1b 22) + 2W (ub 1-2 22222 - 4W: 1-2 14 2
(68)
24

---

First, by lemma 4.6
2w 2 (10 -²) = 2W2 (m) 2z
+ 2W #111 P 1 22)
#
(69)
as p10- 2 support on line. Similarly,
2W (12, -2) = 2W3 (122, 12+12) +
1 -
(70)
and
AW2 (1 .40 2) (4 24 4W2 (P # 1, P 22).
(71)
We notice that 2 # u1, P 1 ( pe 1 +2, pe p2
(P #11, (12) (as P #140 is the Wasserstein mean between P and PT We also notice that (P
0 (it comes from the fact that the generalized Wasserstein mean induced by the permutations the line), we can put all together to have:
# 22 22,22 1
2W2 (Mz, 1())1) 2W (u2, 22))2) 4W2 (mg (zppb))) + (P u2, 0) (PL
(72)
One can show that SWGG is divided into 3 Wasserstein distances between distribution and its projections on a line and ID Wasserstein problem. This results a very fast computation SWGG.
10.6 Smoothing of SWGG
In this section, we give details on the smoothing procedure of min-SWGG, additional landscape of SWGG and its smooth counterpart SWGG and an empirical heuristic for setting hyperparameters and c.
Smoothing Procedure. natural surrogate would be to add an entropic regularization within the definition of "'p, i {1, 2} and to solve an additional optimal transport problem. Nevertheless, it would lead to an algorithm with Onn²) complexity. Instead, build upon the blurred Wasserstein distance [26) between two distributions ei and 12:
(M,, v2) def
W. (ke// V1, ki, V2)
where denotes the smoothing (convolution) operator and ke/4 the Gaussian kernel of deviation ve/2. In our case, resorts making copies of each sorted projections pd (xx;) and p6 (y:) respectively, to add Gaussian noise of deviation ve/2 and to compute averages of sorted blurred copies a y
is
Σ
2 + g*
(73)
28
k=(i-))s+1
Further, we provide additional examples of the landscape of min min-SWGG(p1,,p) and discuss how to choose empirically relevant and values.
26 has shown that the blurred WD has the same asymptotic properties the Sinkhorn divergence, with parameter e the strength of the blurring: it interpolates between WD (when > 0) and a degenerate constant value (when c > oc).
To find a minimum of Eq. (16) in the paper (i.e. SWGG)(M11 P2, 0)), we iterate over:
Oct1 =0; WVSGG
0+1 100+1/110+++11
where E IR4 is the learning rate. This procedure converges towards local minima with a complexity of O(snd + en log(sn)) for each iteration. Once the optimal direction 0* is found, the final solution resorts to the solution provided by SWGG (Mi, U2; 0*), where the induced optimal transport map is an unblurred matrix.
25

---

Heuristic for setting the hyperparameters of SWGG We here provide heuristic for setting parameters (number of copies of each points) and (strength of the blurring). We then give an example of the behavior of SWGG w.r.t. these hyper parameters.
Let f41 = # Σ 8mn and 222 = Σ ky.
I4 represents the number of copies of each sample. We observe empirically that the quantity sn should be large to provide smooth landscape. It means that the values can be small when n increases, allowing to keep competitive algorithm (as the complexity depends on ns)
RR represents the variance of the blurred copies of each sample. Empirically, should depend on the variance of the distributions projected on the line. Indeed, an very close to zero will not smooth enough the discontinuities whereas large will give a constant landscape.
As discussed in Section 4.3 finding an optimal 0 E S is a non convex problem and provides
discontinuous loss function. We give some examples of the landscape of SWGG w.r.t. different values of the hyperparameters in Fig. [0] The landscapes were computed with set of projections regularly sampled with angles E [0, |
We observe that the larger s. the smoother SWGG. Additionally, raising e tends to flatten SWGG w.r.t. (erasing local minima). Indeed similarly Sinkhorn, large e blurred the transport plan and thus homogenize all the value of SWGG w.r.t. 6.
Moreover, we empirically observe that the number of samples for μn and μl enforces the continuity of SWGG. We then conjecture that the discontinuities of SWGG are due to artifact of the sampling and thus the smoothing operation erases this unwanted behavior. A full investigation of this assumption is left for future work.
SWGG
Dinarra
5-10 eps-2.0
ops-0.2
A: 100 spa:2.0
44
Degroe
SWGG
Distanca
eps-0.2
5-10 eps-2.0
5-100 ops-0.2
5- 100 ops-2.0
Degree
Figure 10: Non-convex landscapes for SWGG and SWGG with different hyper parameters.
10.7 Inconsequential of the pivot measure
Importantly, only the direction 0 is of importance for the value of SWGG. Indeed, whenever E (R4) is supported on line of direction 0, the position of the atoms is irrelevant for W, and the associated transport plan whenever the atoms are distinct. Despite the fact that the pivot measure is inconsequential for the value of SWGG (at 0 fixed), we choose it to be μn =222 This choice supported by the fact that p can be efficiently computed (as a ID Wasserstein mean) and that some computation can be alleviated:
(Q M1, m -2) 2W2 (1b (n) 1-2 Q 12) W2(Q' S
(74)
It is an important comment to derive the property of distance for SWGG; it also allows minimizing SWGG over 0 E 5d-1 without consideration for v, since any choice of v supported on the subspace generated by 0 give the same result for min-SWGG. This property of irrelevance comes from the
26

---

nature of the subspace where / is supported, which is uni-dimensional. More formally we give the following proposition and its associated proof.
Proposition 10.1. Let pi, μl2 E P2 (R*). Let S Let P1, v2 P (IR) be two pivot measures supported on line with direction 6 with disctines atoms for each measure. We then have:
W in (21, W (11, u2)
(75)
We give a proof of this proposition.
Thanks to lemma 4.6 we known that the transport map Ty is fully induced by the transport
plan Ty Paam +Q P2
Let remind that T is given by Tu T - (see equation Moreover the two optimal transport plans are obtained via the ordering permutations, i.e. let
3 T, S(n) S.E.
To(l) ... S Fn(()
TT(1) S S Vr(n)
xx(1) S S (x(n)
With H; being the atoms of Qg D. the atoms of 22 M2 and Σ; being the atoms of DzV.
One have (T=((()) = (x()) (resp. TV (2x = (i)) AA i n. Composing these two identities gives:
T (x)(())) = vr(()
L1 sisn n
(76)
The last equation shows that T is in fact independent of æ and thus of v.
10.8 Proof that min-SWGG a distance (generalized geodesic formulation)
This proof has already been established in 7.3 However we rephrase the proof in the context of generalized geodesics.
We aim to prove that SWGG, = v 2W3 2W v2) AW3(w)) mg 2 de-
fines a metric.
Finite and non-negativity. Each term of SWGG? is finite thus the sum of the three terms is finite. Moreover, being an upper bound of WD makes it nog-negaeeve.
Symmetry. We have
SWG = 2W mb -2) + ( Hb 2 -W: (1 , -2 2W2 11 2 + 2W? (11 (11, 2 -wW? (1 ,14 2 SWGG (p2, H1,
Identity property.
From one side, when μi
n12
Twi-pb - >2 Id, giving 1322" 11 u12
Thus:
SWGG M2, 0) (M1, (2) 12+ (11; (11, 2 = (77)
From another side, SWGG 0) = = W2(m1:12) =0 = an = 122 (by being an upper bound of WD).
27

---

Triangle Inequality. We have:
(11, 2W H0 + ,22 -W3 (1
112))
1-2 .10
-110 -2)
(78)
= 1 (x) - x112pb + / (11((x) x =12d10 (z)
(79)
/ (x)) - 2 =11dpt (a)
RR
J (21TT((x) - -013 + x1 42) - =013) 2 (ax)
=
(80)
[Tg T3 122dp ((x) 1 ga
(81)
where, with an abuse of notation for clarity sake, T3 is the optimal map between Hg -2 and μ4 and Tg is the optimal map between ug]+2 and 2 The last line comes from the parallelogram rule of Rd. Thanks Proposition 10.1 we see that SWGG is simply the L LR(RR, v) square norm, i.e.:
SWGG P2, [T)
T
(T) Rd
1
(82)
with being any arbitrary pivot measure P3 (Rd). And thus SWGG2 is the (RR .)) norm. This observation is enough to conclude that SWGG2 is a proper distance for A fixed.
11 Experiment details and additional results
WD, SW, Sinkhorn, Factored coupling are computed using the Python OT Toolbox (28) and our code is available at htthtts://ggg //gi cww/ Com//aheyG/SWdd The Sinkhorn divergence for the point cloud matching experiment was computed thanks to the Geomloss package (27).
11.1 Behavior of min-SWGG with the dimension and the number points
In this section, we draw two experiments to study the behavior of min-SWGG w.r.t. the dimension and to the number of points.
Evolution with d In 20 (hheormm of Section 2], authors aim at enumerate the number of permuta- tions obtained via the projection point clouds on line. appears that the number of permutations increases with the dimension. They even show that whenever d 2 2n (2n being the total number of points of the problem), all the possible permutations (n!) are in the scope of line. Fig. IT depicts the number of obtainable permutations to conclude that whenever d 2 2n, we have min-SWGG? = -W?.
function of the dimension d, for fixed. This theorem
can be applied to
It turns empirically that the greater the dimension, the better the approximation of W3 with min-SWGG (see Fig. 11 for a fixed n. More formally, the set of all possible transport maps is called the Birkhoff polytope and it is known that the minimum of the Monge problem is attained the extremal points (which are exactly the set of permutations matrices, set of n! matrices in our context) (8). The set of the transport maps in the scope of SWGG is subset of the extremal points of the Birkhoff polytope (there are permutations matrices but not all possibilities are represented). Theoretically, the set of transport maps in the scope of SWGG is larger as d grows, giving a subset that is more and more tight with the extremal points of the Birkhoff polytope. This explains that min-SWGG can benefit from higher dimension.
We plot in Fig. 11 the evolution, over 50 repetitions, of the ratio min SWGG(p1,52) with 50 and (i(m)
M1 (1 Id), #2 (N Id).
Evolution with n Fig. 12 represents the evolution of W u2) and min-SWGG for two distributions μ41 ( g4, Td) and #/2 ~ 1-11 Id), with d and varying number of points. The results are averages over 10 repetitions.
28

---

til
10
all Co
30
020
parmusein
Cirension
Dimersion
Figure 11: Evolution of W2 and min-SiGGe with the dimension d for isotropic Gaussian distribu- tions (left) Number of permutations induced by direction 0 E Sd-1 with 310 and a varying dimension (right)
Ig min SWGG for d
Number of points
Figure 12: Evolution of W and min-SWGG w.r.t the number of points
We observe that, when n is large enough, min-SV SWGG tends to stabilize around some constant value. We conjecture that there may exist an upper bound for min-SWGG:
min-SWGG; 12) v'dd, n. W2 (21)
(83)
Where d' is the max the dimensions of the distributions A22 [66 and y an unknown function.
11.2 Computing min-SWGG
We now provide here more details about the experimental setup of the experiments of Section 5.1
compare three variants for choosing optimal direction random search, simulated annealing and optimization (defined in Section 4.3). We choose to compare with simulated annealing since it is widely used in discrete problem (such as the travelling salesman) and known to perform well in high dimension (62] [16] [36]. We notice in Fig. of the paper that the smooth version of nin-SWGG is always (comparable or) better than the simulated annealing. In this experiment, randomly sample 2 Gaussian distributions with different means and covariances matrices, whose parameters are chosen randomly. For optimizing min-SWGG, we use the Adam optimizer of Pytorch, with fixed learning rate of 5e during 100 iterations, considering 10 and 1.
Choosing the optimal
Fig. 13 provides the timings for computing the random search approximation, simulated annealing and the optimization scheme. In all cases, we recover the linear complexity of mGG (blue curves) in a log space. For the computation timings we compute min-SWGG with random search
29

---

with L = 500, simulated annealing (green curves) with 500 iterations with temperature scheme (1
500 k=1 and the optimization scheme (considering 10 with a fixed number of iterations for the optimization scheme equals to 100).
k+1 )==
1,00
Time (660)
0.30
0.01
0.01
Monte Carlo
Optim
00
0
Anneainn
10000
number of paints
Figure 13: Considering two Gaussian distributions in dimensions d equals to: 2 (left), 20 (middle), 200 (right).we compute min-SWGG with random search, simulated annealing schemes and optimization procedure and report the timings for varying number of points and fixed number of projections.
Additionally, reproduce the same setup in 5.1 for the SW, max-SW and PWD distance. For sake of readability we compared with min-SWGG optim and report the results in Fig. 14
WS 92.4
WS- 948.1
W4- 5699
145-22.4
W4-3445
VS 5889
WaddW peptritnt Oylimtud
Mlams (Catriint
3000
376
1000
10
1002
10
1000
10
1200
10
1002
10
1000
prpediuaa
Number praeelto
Figure 14:
Comparison of min-SWGG optim with PWD (left) and with max-SW and SW (right). PWD and SW are computed with a growing number of projection
Runtime Evaluation In the paper, on Fig. 3 (Right), we compare the empirical runtime evaluation on GPU for different methods. We consider Gaussian distributions in dimension
and we sample points per distribution with E {102, 103 10 5 10 109). For SW Monte-Carde Carlo and min-SWGG random search, we use T. = 200 projections. For both max-SW and min-SWGG with optimization, use 100 iterations with learning rate of 1, and we fix 50 for min-SWGG. We use the official implementation the Subspace Robust Wasserstein (SRW) with the Frank-Wore Wolfe algorithm [52]
11.3 Gradient Flows
We rely on the code provided with 37 for running the experiment Section 5.2
We fix n 100, the source distribution taken to be Gaussian and we consider four different target measures that represent several cases: 2 dimensional Gaussian, ii) 500 dimensional Gaussian (high dimensional case), iii) Gaussians (multi-modal distribution) and iv) a two-moons distribution (non-linear case).
We fix a global learning rate of 5e -3 with an Adam optimizer. For SW, PWD and SWGG (random search), sample L 100 directions. For the optimization methods max-SW, set a learning rate of 1e with a number of 100 iterations for i), iii), and iv) and 200 iterations for ii). For min-SWGG (optimization), we took learning rate of i)le -iile-3 iii)5e 2 and iv) 1e-3. The hyper parameters for the optimization of min-SWGG are = 10 and e 0.5, except for the 500-dimensional Gaussian for which pick 10.
Each experiment is run 10 times and shaded areas Fig. (see the main paper) represent the mean
+ the standard deviation.
30

---

11.4 Gray scale image colorization
We now provide additional results on pan-sharpeeeee -un-shapennin application complete results provided in Section 5.3
In pan- -an-shapenning 64]. one aims at constructing super-resolution multi-chromatic satellite im- age with the help of super-resolution mono-chromatic image (source) and low-resolution multi- chromatic image (target).
To realize this task, we choose to used a color transfer procedure, where the idea is to transfer the color palette from the target to the source image. This transfer is carry by the optimal transport plan of the Wasserstein distance. More details on color transfer can be found in Supp. T1.6
Additionally, we improve the relevance of the colorization by adding proximity prior. For that, we used super pixels computed via the Watershed algorithm [48] thanks the the scikit-image package [6]]. Obtained high resolution colorized images of size 512x (n 262 144) are reported on Fig. 15
Source
Torget
Figure 15: Source high resolution black and white image (left) Target low resolution colorful image (right) Obtained high resolution colorful image (mid).
All pan-sharpening experiments were run the PairMax data (64 The hyperparameters (markers and compactness) for the watershed super-pixels are: 500, 200, 200, 200 markers (an upper bound for the number of super pixel) for each image (by order of apparition) and compactness le 8 (high values result in more regularly-shaper watershed basins) for all the images.
11.5 Point clouds registration
We here provide additional details and results about the experiments in Section 5.4
31

---

Authors of [9] highlighted the relevance of OT in the point clouds registration context, plugged into an Iterative Closest Point (ICP) algorithm. They leveraged the 1D partial OT without consideration for the direction of the line. Our experiment shows the importance of 0: the smaller SWGG is, the better the registration.
In this experiment, having a one to one correspondence is mandatory: as such, we compare min-SWGG with a nearest neighbor assignment and the one provided by OT. Note that we do not compare min-SWGG with subspace detour [44], since: i) with empirical distributions, the re- construction of the plan degenerated (as it doesn't involve any computation), ii) the research of subspace can be intensive no prior is provided.
To create the source distributions, used random transformation (St t) O(d) Rd of the target domain. 52 was picked randomly from O(d), the set of rotations and reflections, and t has random direction with ||d||
We also add Gaussian noise (O, eId), with 0.1.
The ICP algorithm was run with 3 datasets with the following features: i) 500 points in 2D, ii) 3000 points in 3D, and iii) 150 000 points in 3D. min-SWGG was computed through the random search estimation with the algorithm, which varies with the dataset i.e.: i) 50, ii) 100, and iii) 200 respectively. The other stopping criterion is || - Id|l + ||t]|2 I E with chosen respectively for the datasets as follows: i) 1e-1, ii) 1 and iii) -2, where (St, 1) E (d) x Rd is the current transformation and || the Frobenius norm. All these settings were run with 50 different seeds. Results are reported in Fig. T6
100. A stopping criterion was the maximum number of iterations of
Figure 16: The three datasets (left) and the distributions the Sinkhorn divergences, the Chamfer distance, the Frobenius distance, the timing and the number of iterations over 50 seeds (right).
From Fig. 16 one can see that for:
n 500: The registration obtained via OT is very powerful (it is fast to compute and converges toward good solution). min-SWGG slightly faster with better convergence result and equivalent number of iterations. Finally the nearest neighbor does not converge to a solution closed to the target.
n 3000: registration by OT converge poorly, moreover the timings much higher than the competitors. min-SWGG shows efficient convergence results with an attractive computation time (order of fews seconds). We observe that the number of iterations very large and we conjecture that it is due to the fact that min-SWGG-baas ICP can exit local minima. The nearest neighbor is fast but, most of the time, does converge global minima (i.e. the exact matching of the shapes).
be
n 150000: In this setting, OT is totally untractable (the cost matrix needs 180 GB in memory), min-SWGG shows good convergence and is most of the time very fast whenever
32

---

the number of iterations does not attain the stopping criterion. The nearest neighbor assignment faster but only converges local minima.
Note that, despite the fact that min-SWGG is slightly slower than the nearest neighbor, the overall algorithm can faster due to the better quality of each iteration (min-SWGG can attain minimum with less iterations).
In Table 3 we give additional results on the final distribution. We control the final convergence via the square Chamfer distance and the square Frobenius distance. The Square Chamfer distance is sqaure distance between point cloud defined as:
(X, = Σ min |a
-alrr-llle 2112 +
Σ min | zEX
y
(84)
xEX yEY
DEY
and the Square Frobenius norm is square distance between the transformation, defined as:
Fre frea),, (Sestimated festimmted)) = [[aeeal -
Restimatedd 112 + ||eral - festimated
(85)
In both cases we can that the final results for min-SWGG are much better than the results for NN and relatively closed to the results from OT.
7
500
3000
1500 00
NN
I1.65
0.20
6.90
OT
0.03
0.16
min-SWGG
0.08
0.13
8 x 10 10-4
500
3000
150 000
NN
526
30.04
21.7
OT
3.8
6.5
min-SWGG
4.5
6.01
Table 3: Square Chamfer distance (top) and Square Frobenius distance (bottom) between final transformation the source and the target. Best values are boldfaced.
An other important aspect of ICP is that the algorithm tends fall into local minima: the current solution is not good and further iterations do not allow a better convergence of the algorithm. We observed empirically that min-SWGG can avoid getting stuck local minima when reasonable number directions f is sampled (L ~ 100). We conjecture that the random search approximation not always the ideal solution and hence may escape local minima. This may lead to better convergence solution for min-SWGG-based ICP.
11.6
Color Transfer
In this section, we provide additional experiment in a color transfer context.
We aim at adapting the color of an input image match the color of a target one 25 problem can be recast as an optimal transport problem where we aim at transporting the color of the source image X into the target Y. For that, usual methods lie down on the existence of map T X + Y. We challenge min-SWGG to this problem to highlight relevance of the obtained transport map.
44
This
Images are encoded as vector in Ramx3 where and m are the size of the image and 3 corresponds the number channels (here RBG channels). We first compute map To Xo + Yo between subsample of X and Y of size 20000 and secondly extend this mapping to the complete distributions T' X + Y using a nearest neighbor interpolation. The subsampling step is mandatory due the size of the images but can deteriorate the quality of the transfer.
We compare the results obtained with maps obtained from Wasserstein distance, min-SWGG with random search (100 projections), subspace detour 44 and min-SWGG (optimized). Obtained images and the associated timings are provided in fig. 17
Figure shows that min-SWGG and W provide visually equivalent solutions. Since, the quality of the color transfer is dependent on the size of the subsampling: using SWGG permits larger
33

---

fnurtime 02.2281
SUSG mrmtiine
SMIDO spdim Cranliigg 0.101
Salopane Dallurr Eurtime
Tarpe
Crttine (urdree
barect
Figure 17: Color transfer of images with W3, min-SWGG and subspace detours, with runtimes.
subsamples than W2 and thus improves the quality of the map T. Moreover note that min-SWGG (optimized) is the fastest to compute.
We now give more details about how to perform color transfer between two distributions. The first step to encode n x m images as Ramx3 vectors, with channels RGB image. Note that m and n can differ for the source and target image. The second step consists of defining subsamples Xo. Yo X, Y. in our case we took Xo; Yo E R22000x4 We subsample the same number points for the source and target image. In order have a better subsampling of X and Y, it is common to perform k-means [3]] to derive X, and Yo (X Yo are then taken as centroids of the k-means algorithm). The third step is compute To X Yo- We set T as the optimal Monge map given by the Wasserstein distance and T as the optimal map given by min-SWGG. Finally, the fourth step deals with extending To: Xu Y T X + Y. Vx X. We compute the closest element 2o E X and we pose:
T(x) T(
(86)
More details on the overall procedure can be found in (25]
To perform the experiment, we took L 100 projections for min-SWGG (random search). For min-SWGG (optimized), we fixed the following set of parameters for the gradient descent: learning rate 5 number of iterations 20, number of copies 10 and
Regarding the subspace
detour results, we used the code of [4]] provided at https: ttte://iittnn gitgub..hh... Satam/BoriiMuzeelle.. SubspaceOT]
Additionally, we perform color transfer without sub-sampling with the help of min-SWGG (we the same hyperparameters). This procedure is totally untractable for either W22 and subspace detours (due to memory issues). As we mentioned before, the subsampling phase can decrease the quality of the transfer and thus min-SWGG can deliver better result than before. Result are give in Fig. 18
SINGo (oundmm
entin turliow
Figure 18: Color transfer of images with min-SWGG without sub- uub-sampling.
11.7 Data set distance
We finally evaluate min-SWGG in an other context: computing distances between datasets. Let D, { y ) and D: {a? v be source and target data sets such that x!. ot e Rd are samples and y y are labels v1 I S n. Bl the authors compare those data sets using the Wasserstein distance with the entries of the cost matrix defined as:
(1ar)
2311
W3 (a 0yz)) 1/2
(87)
and the corresponding distance as:
OTDD(D, D2)
min (C, P) Pet
(88)
34

---

where dy is the distribution of all samples with label y. namely {x E [=1 y) E D) for D being either 11 or D and U is the Birkhoff polytope which encodes the marginal constraints. Notice that cost in Eq. (87) encompasses the ground distance and a label-to-label distance. This distance is appealing in transfer learning application since model-agnostic. However, can be cumbersome to compute in practice since it lays down on solving multiple OT problems (to compute the cost matrix and the OTDD). To circumvent that, [3] proposed several methods to compute the cost matrix in Eq. (87). They used the Sinkhorn algorithm (in ((n)) or they assumed ay ~ MM Mny in order to get the WD through the Bures metric (that provides a closed form of OT for Gaussian distributions in (dd))) )) which is still prohibitive for high dimension. We challenge min-SWGG in this context.
In this experiment, we compare the following datasets: MNIST 39 EMNIST [18] MNSS 67.. KMNIST 17 and USPS (32] We rely on the code of OTDD provided at https:/ thub com mniicroooft/tde In order to make it compliant with the min-SWGG hypothesis, we require
the empirical distributions Oy to have the same number of atoms.
Fig. 19 provides results for a batch size of n = 40000 samples using the Sinkhorn divergence (with regularisen aggularistionn parameter of le 1) and for min-SWGG (optimized) on batch of size 40000. We report results for a learning rate of le 20 iterations and & and e to be and O.
0.9
0.88
1.3
1.2
1.2
1.3
1.2
0.8
338NST
1.2
1.2
1.3
1.1
1
1.2
0.9
022
0.8
USS
0.9
0.9
0.7
0.9
Figure 19: OTDD results (x10²) distances for min-SWGG (left) and Sinkhorn divergence (right) for various datasets.
We check that the orders of magnitude preserved with min-SWGG. For example OTDD(MNIST,USPS) is smaller than OTDDDMMNIST FashioMMNIS)) for either Sinkhorn divergence min-SWGG as distance between labels, this validate that min-SWGG is meaningful distance in this case scenario. Moreover in our setup, the computation cost is more expensive for Sinkhorn than for min-SWGG and totally untractable for W On smaller batches (see Fig 20). the same observation can be made: min-SWGG is comparable (in term of magnitude) with W.,. Sinkhorn and the Bures approximation.
We give additional results in Fig. 20 for batches of size of n = 2000 samples obtained with W2. Sinkhorn divergence (setting the entropic regularization parameter to 1e- 11, the Bures approximation, min-SWGG (random search with = 1000 projections) and min-SWGG (optimized, with a learning rate of 5e -1 50 iterations, = 20 and 0.5).
055
13
1:34
2.5
05
0.5
177
00
13
1.4
1.5
1.5
Figure 20: OTDD distance with W3 (left), Sinkhorn (left-mid), Bures (middle) and random search min-SWGG (right-mid) and min-SWe SWGG-optimization (right) distances between labels distribution x 1
35

---

Note that the Figs.
19 and 20 are not symmetric (OTDDEENNNSSTFashionNNNSS11
OTDDGEshIMNNISTAKNNNSST because of the random aspect of batches.
36


Reviews:
[{"review_id": "Nf40ujzw06", "reviewer": "Reviewer_5WTB", "summary": "The paper proposes a new formulation and algorithm to approximate Wasserstein 2-distance (i.e., the distance of two points is the squared Euclidean one) between two distributions. Though some of the development is general, the key parts and the algorithms apply only to distributions being the sums of delta functions with the same weights. The approach builds on approaches approximating the true WD by using 1-D slices of the distributions, the distance between which can be computed cheaply as pointwise sum of squared differences of sorted distributions.\n\nThe basic Sliced WD, which approximates the true WD by the integral of the distance between such 1-D projections over all directions (eq. (5)). Its approximation is Max-Sliced WD, which replaces the integral by maximization (eq. (6)), leading to a lower bound on the true WD.\n\nAnother existing sliced formulation is Projected WD, which approximates the true WD by the integral of the pointwise sum of squared differences between the two distributions in which the points are sorted as if the distributions were projected onto the direction, over all directions (eq. (7)). The approach proposed in the manuscript replaces the integral here by minimization (eq. (9)), which is called Min-SWGG. It yields an upper bound in the true WD. This problem is non-convex, in fact discontinuous because the objective jumps with every change of either permutation (which sort the points on the projections). Therefore, it is smoothed and at the same time reformulated using the concepts from differential geometry of WD, generalized geodesics. This leads to a smooth non-convex problem, approximating the initial min-WDGG formulation. Its objective for a given direction can be evaluated cheaply: its most expensive part is the WD between a general point cloud and a point cloud on a line, which can be computed cheaply by just sorting 1-D distributions. The obtained problem is solved by gradient descent (yielding thus a local minimum).\n\nThe experiments compare the Min-SWGG, optimized either by smoothing and gradient descent or by random search or by simulated annealing, with existing (approximate) WD methods on synthetic data. Then it is illustrated on colorization of gray-scale images by OT, where computing the exact OT is intractable. Then it is demonstrated on point cloud registration by the ICP algorithm, where the point correspondence in every ICP iteration is computed either by nearest-neighbor or OT.", "questions": "Q1) In the restricted setting of unweighted discrete distributions (i.e., from $P_2^n(R^d)$), the problem (1) reduces to linear assignment problem with costs being squared Euclidean distances. This is a classical problem, for which a great number of exact and approximate algorithms have been proposed. Unfortunately, I am not that familiar with existing approximate algorithms for this problem. Did you double check that there is no existing approximate algorithm for this problem that would compare in efficiency with your algorithm but which would however not generalize to arbitrary distribution (e.g., various primal heuristics, moving between permutations by local changes)? In other words, is the strength of the proposed approach only in its generalizability to arbitrary distributions, or already for the distributions from $P_2^n(R^d)$?\n\nQ2) In particular, the experiments do not convince me that min-SWGG is more efficient than Sinkhorn. The right-most graph in Figure 3 does not make clear to what accuracy the individual algorithms were run - in other words, it mixes accuracy and runtime (it does not compare the runtimes for the same achieved accuracy, or vice versa). Note, Sinkhorn keeps only dual variables and it need not keep the cost matrix (n-by-n) explicitly, so its memory complexity scales up well with n and d. Please comment.\n\nQ3) Please comment on parallelizability of the algorithm. I guess that the gradient descent to minimize (9) is not easy to parallelize. Of course, random search is.\n\nQ4) A suggestion: for small $d$, it might be interesting to try optimizing (9) (non-smoothed) by derivative-free methods, such as Nelder-Mead.", "limitations": "The experiments are done only for unweighted discrete distributions.\n\nThe experiments do not convincingly show that min-SWGG is more efficient than, e.g., Sinkhorn.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem addressed is useful in a number of applications.\n\nTechnically sound.\n\nClearly enough written.", "weaknesses": "The formulation of min-SWGG (eq. (9)) is rather straightforward. Namely, approximating the integral (7) by the minimization (9) is analogous to approximating the integral (5) by the maximization (6). In this sense, I see the novelty of the paper as rather incremental.\n\nIt is inconvenient that a lot of non-trivial information is in the supplement (I wonder if this format of presentation is desirable for NIPS). E.g., in the main paper the problem is restricted for the distributions from $P_2^n(R^d)$, i.e., unweighted averages of delta-distributions (see line 116), so that the exact WD (formula (1)) reduces to a linear assignment problem with the costs being squared Euclidean distances, for which the transport plan is a permutation. I.e., given two clouds of points in R^d with n elements, we want to find a permutation of one point cloud such that the sum of squared Euclid. distances between the points is minimum. In this restricted formulation, the min-SWGG (9) just optimizes over a subset of all possible permutations, given by sorting the projections of the distributions onto some direction. It is mentioned that this formulation can be extended to arbitrary distributions, but the details of this extension are just sketched in the supplement (section A.2). It is not clear from A.2 what would be the complexity of the algorithm in this general setting. In particular, I do not see why the transport plan (eq. (4) in A.2) should always have only $n+m-1$ nonzeros. Moreover, the experiments are done only for the restricted setting.\n\nDetails of some experiments are also often given only in the supplement. E.g., Section 5.3 has too little details to me, so that I do not understand how exactly image colorization is formulated. The additional info in the supplement is not helpful.\n\nIn experiments, Table 1 (report on point cloud registration by ICP) might be unfair to the nearest-neighbor method because the table reports Sinkhorn divergence of the registered clouds, which is close to what is optimized in min-SWGG. A better criterion to report might be the difference between the estimated and the ground-truth transformation (assuming that the latter is available, which trivially is e.g. when the target cloud is constructed by transforming the source cloud). Moreover, NN might perform well in the regime when the point clouds are initially close to each other.\n\nMinor comments:\n- The formulas for $\\mu_1,\\mu_2$ on line 116 are repeated on lines 122. The text could be optimized such that they appear only once.\n- Denoting the distances (8) and (9) as (min-)SWGG is confusing because generalized geodesics (GG) are not needed for their definitions (they are needed only later to reformulate the definitions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your work in revising our paper and for the valuable comments and questions.\n\n- **The formulation of min-SWGG is straightforward**. We respectfully disagree. You are correct in stating that PWD and min-SWGG share some similarities. While the definition of min-SWGG might appear simple in eq. (9), it can also be reformulated thanks to Wasserstein Generalized Geodesics (eq. 14), which is far from being trivial. Additionally, we want to emphasize that min-SWGG's appeal lies in two key properties: i) its ability to provide a transport plan, and ii) its suitability for optimization via gradient descent. These two properties do not hold with the original PWD loss.\n\n- **The color transfer experiment lacks sufficient details.** Details on the experiments can be found in [1]. More details will be added to the supplementary material.\n\n- **Regarding the ICP experiment.** Tables 1 and 2 (of the rebuttal's pdf) provide additional results for the ICP experiment (with $n=500$ and $n=3000$) and show that min-SWGG performs favorably when considering square Frobenius or Chamfer distance.\n\n- **The transport plan has (at most) n+m-1 non-null values.** This is a general property of an OT plan (see [2], Proposition 3.4, for example). In our case, the transport plans are optimal between $\\mu_i$ ($i=1,2$) and the pivot measure $\\nu$. This ensures that they have at most $n+m-1$ non-null values.\n\n- **Existing approximations of the linear assignment problem.** We thank the reviewer for this question. To the best of our knowledge, there is no algorithm that solves approximately (with guarantees) the linear assignment (Monge) problem with a complexity lower than quadratic (compared to our superlinear one), without additional assumptions about the nature of the problem/distributions. A relevant reference can be found in [3].  The reviewer is also correct in stating that the strength of the proposed approach also lies in its generalization to arbitrary distributions.\n\n- **Comparison with the Sinkhorn algorithm.** In the right part of Figure 3, we ran all the algorithms until convergence. Specifically, Sinkhorn was computed in a favorable convergence setup ($\\epsilon=1$). Indeed, Sinkhorn keeps in memory the dense matrix via the dual variables which reduces the memory cost of the method. min-SWGG is more memory-efficient than Sinkhorn as it only stores the permutations ($n$ values). In the case of $\\mu_1 \\in \\mathcal{P}_2^{n_1}(\\mathbb{R^d})$ and $\\mu_2 \\in \\mathcal{P}_2^{n_2}(\\mathbb{R^d})$ with $n_1\\neq n_2$, min-SWGG requires to store the quantile function, which consists of at most $n+m-1$ values.\n\n- **Parallelization of SWGG.** The reviewer is right. In terms of parallelization min-SWGG is comparable to the Sliced Wasserstein methods and may be parallelizable for random search but not for the optimization scheme.\n\n\n- **Gradient-free and Nelder-Mead methods.** We appreciate the reviewer's suggestion. We believe that gradient-free optimization schemes for min-SWGG could be practically beneficial, and we will closely examine them in our future investigations. However, let us note that the Nelder-Mead method requires the function to optimize to be continuous, which is not the case in our specific setting. Furthermore, when the measures belong to $\\mathcal{P}_2^n(\\mathbb{R^d})$, we are currently exploring differentiable sorting methods [4] that optimize directly over the permutahedron (the convex hull of permutations). These methods allow us to maintain the $O(n \\log(n))$ complexity of the approach, and might be more efficient than the ad-hoc, yet simple, solution presented in our paper.*\n\n[1]Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014). Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, 7(3), 1853-1882.\n\n[2] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5-6), 355-607.\n\n[3]Duan, R., & Pettie, S. (2014). Linear-time approximation for maximum weight matching. Journal of the ACM (JACM), 61(1), 1-23.\n\n[4]Blondel, M., Teboul, O. Berthet, Q. and Djolonga, J.  Fast Differentiable Sorting and Ranking, ICML (2020) \n"}, {"review_id": "H86WCz3cAt", "reviewer": "Reviewer_rywq", "summary": "This paper proposed a novel proxy of the squared Wasserstein distance called min-SWGG, which is based on Sliced-Wasserstein distance (SWD) and the projected Wasserstein distance (PWD). This quantity is also shown to be relevant to Wasserstein Generalized Geodesics with pivot measure, which makes it more interesting. The theoretical properties of min-SWGG has been discussed, including the topological properties and the relationships with Wasserstein Generalized Geodesics. The authors provide two efficient algorithms for computing min-SWGG.  The experimental results indicates better computational efficiency of the proposed algorithm compared to the state-of-the-art methods.\n", "questions": "See weakness.\n\n", "limitations": "I have not found the limitations of the approach to be addressed in the paper. Maybe the authors can elaborate more on these.\n\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and clear, the approach is well supported by the theoretical analysis. The experiment and application seem strong and nice. The authors also made comparisons to other state-of-the-art methods that makes the paper more complete.", "weaknesses": "- One question about the approach in line 140: In Remark 3.3 the authors mentioned about the overall computational complexity to calculate min-SWGG by random search for L times. I wonder if there is any upperbound for it when the dimension d is high? Or is there any results showing the possible order of relation of  L and dimention d, or other quntities?\n\n- For the second row of Figure 2, I notice that for Gaussian 500d, min-SWGG (optim) performs the best but for the left one, min-SWGG (optim) may have inferior behaviors. What might be the issue? Could you maybe elaborate on it a little bit?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comment regarding the behavior of min-SWGG when $d$ varies. It is indeed an interesting question, and we do believe that min-SWGG is a particularly interesting approximation in this context. First, we recall that, when $d > 2n$, equality between $W_2^2$ and min-SWGG holds (Prop. 3.2).\n\n- **Behavior of the number of random directions with the dimension.** We expect that, as $d$ increases, a larger number of projections $L$ will be required to achieve a decent approximation. Empirically, we also observe that within a broad range of scenarios, it is sufficient to take $\\mathcal{O}(L^{d-1})$ directions, similar to SWD [2] or max-SW [1]. A deeper investigation of this behavior is deferred to future work. This behavior serves as motivation for designing an optimization scheme through gradient descent.\n\n- **Variability of min-SWGG optimization with dimension in gradient flow experimentation.** You are correct: when $d$ is small, it can be observed that min-SWGG (optim) converges a little more slowly than min-SWGG (random search). This is due to the fact that min-SWGG (optim) optimizes a smooth and non-convex surrogate of min-SWGG (see eq. 16). As such, the quality of the minimum found by descent depends on the choice of the initialization. Empirically, we find that solutions provided by this surrogate may differ from those of min-SWGG (random search), even though they are close. The gradient flow experiment is run for 2000 iterations, which accounts for the final difference.\n\n[1] Deshpande, I., Hu, Y. T., Sun, R., Pyrros, A., Siddiqui, N., Koyejo, S., ... & Schwing, A. G. (2019). Max-sliced wasserstein distance and its use for gans. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 10648-10656).\n\n[2] Zhang, J., Ma, P., Zhong, W. and Meng, C. . Projection-based techniques for high-dimensional optimal transport problems. Wiley Interdisciplinary Reviews: Computational Statistics, 15(2):e1587, 2023.\n"}, {"review_id": "NC6nJY4p1C", "reviewer": "Reviewer_CJnA", "summary": "This paper proposes an approximation to the squared Wasserstein distance between probability measures (typically required in high dimensional space) based on the sliced Wasserstein paradigm. The general idea is to project points onto a line where computing Wasserstein distances becomes significantly simpler (a typical case involves only permutations and sorting). The authors build up their main construction - min SWGG, by leveraging the properties of prior works like Max SW and projected sliced Wasserstein distance (PWD) and derive a tighter upper bound for the squared Wasserstein distance (W2) in comparison to PWD leading to the definition of min-SWGG. To put it very simply min-SWGG is closely related to the PWD, where the minimum is chosen instead of the average over all possible angles.   \n\nThe authors then relate the min-SWGG formulation to Wasserstein Generalised Geodesics - which involves a third measure (called pivot) in order to approximate the actual Wasserstein distance. By choosing the pivot measure to lie on a line,  this connection enables a more tractable way to optimize for the best angle/plane to compute min-SWGG. \n\nExperiments are demonstrated for (1.) Image Color Transfer (2.) PointCloud Matching (3.) Empirical demonstration of min SWGG optimization. The results demonstrate a proof of concept (i.e. examples showing the min-SWGG can be computed with different options quite reasonably) and some cases of good accuracy and faster computation", "questions": " - I am curious to visualize the difference between the transport plan obtained using min-SWGG in comparison to the optimal transport plan (i.e. corresponding to WD). This could potentially be visualized on the Pointcloud example. \n- How do the other SW distances (SW, max-SW, PWD etc.) compare in figure 3 (left)?\n- What is the evaluation for some other metric in the point cloud example, for eg the chamfer distance, L2 error after alignment etc. Is there a specific reason to report only the sinkhorn divergence? ", "limitations": "See Weaknesses for technical limitations. I am not an expert, but I think this paper has no direct negative societal impact. \n\nOverall, I am inclined positively on this paper. The new definition and approximation are derived nicely and interesting connections are made to the Wasserstein Generalised Geodesics framework. However, the practical impact (even amongst competing optimal transport techniques) is not equally impressive, and at this point unclear if it is as widely applicable. Put together, I vote a weak acceptance, with an intention to re-assess more carefully after the rebuttal.  \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Overall, I found this paper to be very comprehensive in its core formulation of min-SWGG. This paper appears to rate highly in its theoretical contributions - (1.) The definition of a new OT approximation with interesting bounds to the actual WD and PWD (2.) Connecting min SWGG to the Generalized Wasserstein Geodesic using a pivot measure that lies on a line thereby showing a path for computational tractability (3.) Proofs of metricity, weak convergence, computational and topological properties etc.\n- The paper is written well with a good introduction and fairly self contained background", "weaknesses": "- The practical aspect of this paper is sort of underwhelming. It would have been very convincing to demonstrate on truly high dimensional applications. Most experiments are very synthetic, and despite a modest experimental section, I am still grasping for situations where min-SWGG outperforms SWD and perhaps WD in terms of computability, quality of distances and transport maps, barycenters etc.\n- To this aid, despite the commentary on the use of cumulative distributions in the supplementary (enabling transport plans instead of maps), I could not place any impactful demonstration. That being said almost all of the narrative is based on matching uniform distributions having equal number of points and it's unclear how to generalize from here. \n- Generally, most figures could do with a more descriptive caption. Especially Figure 4 which I am finding really hard to parse. What is the box with Gaussian 500d indicate? Which are the source and target distributions? What is the message of this experiment? (I suspect it is that with enough iterations, the optimization of min-SWGG provides lower W2 distances - please clarify)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and provide some answers to the questions and provide feeback about the reported weaknesses.\n\n- **The practical aspect of min-SWGG is underwhelming.** In the paper, we conducted several experiments in a wide set of scenarii, with the aim to stress the interest of min-SWGG. We first aimed at illustrating some properties of min-SWGG, e.g. i) study of the random search and optimization scheme (Sec. 5.1), ii) study of the runtimes wrt competitors (Sec. 5.1), iii) study of its weak convergence property (Sec. 5.2). We also provided some results in different contexts, such as color transfer and pan sharpening (Sec. 5.3, E.4 and E.6), point clouds registration (Sec. 5.4) and computing distances between datasets (Sec. E.7). We showed that the optimization scheme is relevant in high dimensional settings (5.1 and 5.2), that its computation is fast wrt competitors (Sec. 5.1 and 5.4) and that it comes with a tranport plan (which is not the case for SWD, Sec. 5.3 and 5.4). It is true that we did not elaborate on a flagship application, and we hope that future studies will allow illustrating the relevance of min-SWGG in a wider set of contexts. \n\n\n- **Visualize the transport plan of min-SWGG.** We propose to include examples of the transport plan in the ICP context in the final version. Meanwhile figure 1 (of the rebuttal's pdf) illustrates the transport plan of min-SWGG and plain OT on two examples of Gaussian or bimodal distributions.\n\n- **Evolution of SW, max-SW, PWD,.. in figure 3.** It is entirely feasible to incorporate the competitors into the figure. However the differing orders of magnitude tend to deteriorate the readabiliy of the figure. The attached Table 3 in the PDF accompanying the main author's rebuttal offers an illustration of this magnitude difference in a distinct yet related setup.\n\n- **Regarding the ICP experiment.** Tables 1 and 2 (of the rebuttal's pdf) provide additional results for the ICP experiment (with $n=500$ and $n=3000$) and show that min-SWGG performs favorably when considering square Frobenius or Chamfer distance.\n\n"}, {"review_id": "dHFShpJKvn", "reviewer": "Reviewer_LrDA", "summary": "The paper introduces a variant of slicing of the Wasserstein distance that keeps the optimal transport map property (in particular, existence of an optimal transport map). The typical formulation of slicing loses the Monge map as each slice comes with its own map and there is no natural way to combine maps coming from different slices. As in the Wasserstein case, the variant of the sliced optimal transport distance introduced here is efficient to compute, and performs similarly (both theoretically and in practice) to the sliced Wasserstein distance.", "questions": "(a) Connected to (1) in the weaknesses section: can you give sufficient and/or necessary conditions for existence of minimizers in Definition 4.1?\n(b) What would you do if minimizers do not exist?", "limitations": "There was no discussion on limitations of the method, although a few directions for further work was proposed in the conclusions.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea is very nice. A major advantage of sliced distances are their numerical efficiency but the big drawback is the lack of maps. By being able to define optimal transport maps the authors have removed a significant disadvantage, whilst keeping the main advantage.", "weaknesses": "(1) More theoretical background/justification, such as when do minimizers in Definition 4.1 exist would be helpful.\n(2) The distance defined in eq. (13), since it can be written as the square root of \\int_{R^d} \\| T^{\\nu\\to\\mu_1}(x) - T^{\\nu\\to\\mu_2}(x)\\|^2 d \\nu(x), is the linearized Wasserstein distance. The authors should connect to the literature on linearized optimal transport distances.\n(3) There were a MANY grammatical and spelling errors in the paper, including misspelling Wasserstein (line 48). The paper needs a very careful readthrough. This is my reason for scoring the paper as a 2 in presentation. I felt the explanations were otherwise quite good, and I would be happy to give a higher score once corrections have been made.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and for the positive evaluation of our paper. We now provide detailed answers to your questions.\n\n- **Existence of minimizer in Definition 4.1.** The existence of $\\mu_\\theta^{1\\to2}$ is always guaranteed, whenever $\\mu_1,\\mu_2$ are two empirical probability measures. This follows from the fact that the Wasserstein mean (aka McCann interpolant with $t=1/2$) is always explicit in this case (you can refer to [1] Remark 7.1 for example). We propose to include a reference to this property in the background section of the final version.\n\n- **Link with the linearized OT.** You are correct; min-SWGG is indeed a linearized version of the Wasserstein distance where the ground measure $\\nu$ is chosen carefully. We provided a brief overview of this property in Section C ('Linear Optimal Transport') of the supplementary material. We propose to strengthen this discussion with more literature on linearization. It would be interesting to elaborate on the importance of the ground measure in approximating the Wasserstein distance using the $L^2(\\nu)$ distance. For instance, when the ground measure is chosen to be the Wasserstein mean of the two distributions the distance obtained through linearization equals the true Wasserstein distance.\n\n- **Grammatical and misspelling errors.** We apologize for the English errors that appear throughout the paper. We are committed to ensuring thorough proofreading in the final version. We have already addressed some issues using online tools and intend to have the paper reviewed by a native English speaker if it is accepted. \n\n[1] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5-6), 355-607.)"}]

Author rebuttal:
We thank the reviewers for their constructive comments and answer their questions below. We hope our clarifications address the reviewers' questions. 

Reviewers 5WTB and CJnA discussed the fact that the min-SWGG formulation is derived in the restricted $\mathcal{P}_2^n(\mathbb{R^d})$ setting and that the extension to the general $\mathcal{P}_2(\mathbb{R^d})$ setting is not clear. We propose a general answer to clarify this aspect.

We chose to derive the full article in the $\mathcal{P}_2^n(\mathbb{R^d})$ setting for sake of readability. Solving OT for generic 1D distributions is based on the generalized quantile function (as stated in A.2, see also [1], remark 2.30). Since min-SWGG relies on solving the 1D OT problem between the projected distributions (see eq. 8), it can be straightforwardly extended to generic distributions. In the final version, we propose to  make this more explicit by providing thorough details on the construction of the general version of min-SWGG (i.e. the setting where $\mu_1 \in \mathcal{P}_2^{n_1}(\mathbb{R^d})$ and $\mu_2 \in \mathcal{P}_2^{n_2}(\mathbb{R^d})$ with $n_1\neq n_2$), along with the corresponding code. 

Additionally, we provide some figures and tables regarding the questions and propositions of the reviewers in the following pdf file.

Thank you again for your time and expertise put in reviewing this paper.

[1] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5-6), 355-607.

Meta-review: All reviewers viewed this work positively and highlighted the practical/theoretical value of the simple formulation here.  This paper is a clear "accept" and will find a clear audience at NeurIPS.

Please make sure the camera ready version of the paper addresses reviewer concerns and incorporates promised additions/changes from the rebuttal phase.
Decision: Accept (spotlight)