LCOT: Linear Circular Optimal Transport
Authors: Rocio P Diaz Martin
Ivan Vladimir Medri
Yikun Bai
Xinran Liu
Kangbai Yan
Gustavo Rohde
Soheil Kolouri
Venue: ICLR 2024 poster (2024)
Keywords: Optimal Transport
Circular Measure
Probability Metrics
Primary area: general machine learning (i.e., none of the above)
TL;DR: The paper proposes a new metric, called LCOT, for probability measures supported on the unit circle that is computationally efficient, has an explicit linear embedding, and is rooted in the Circular OT metric.

Abstract: The optimal transport problem for measures supported on non-Euclidean spaces has recently gained ample interest in diverse applications involving representation learning. In this paper, we focus on circular probability measures, i.e., probability measures supported on the unit circle, and introduce a new computationally efficient metric for these measures, denoted as Linear Circular Optimal Transport (LCOT). The proposed metric comes with an explicit linear embedding that allows one to apply Machine Learning (ML) algorithms to the embedded measures and seamlessly modify the underlying metric for the ML algorithm to LCOT. We show that the proposed metric is rooted in the Circular Optimal Transport (COT) and can be considered the linearization of the COT metric with respect to a fixed reference measure. We provide a theoretical analysis of the proposed metric and derive the computational complexities for pairwise comparison of circular probability measures. Lastly, through a set of numerical experiments, we demonstrate the benefits of LCOT in learning representations from circular measures.

Published as a conference paper at ICLR 2024
LCOT: LINEAR CIRCULAR OPTIMAL TRANSPORT
Rocío Díaz Martín" Ivan Medri Yikun Bai* Xiran Liu', Kangbai Yan', Gustavo K. Rohde Soheil Kolouri 13
'Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA. DDppartment of Computer Science, Tennessee State University, Nashville, TN 37209, USA. 'Department of Computer Science, Vanderbilt University, Nashville, TN 37240, USA. "Department of Biomedical Engineering, Department of Electrical and Computer Engineering, University of Virginia, Charlottesvillle, VA 22908, USA.
"(rocio.ee P. diaz martin, k kangbai yaieaaaeeaa...e....e............ edu 3 ((ykkun myyiuunbbi,, xinran. oat.aaa........oaaaa.ooooooooooe
soheil
2 Pimedriee i Cettrri@tstttte..mmmm edu, " "gustavevvi
ABSTRACT
The optimal transport problem for measures supported on non-Euclidean spaces has recently gained ample interest diverse applications involving representation learning. In this paper, focus on circular probability measures, i.e., probabil- ity measures supported on the unit circle, and introduce a new computationally efficient metric for these measures, denoted Linear Circular Optimal Transport (LCOT). The proposed metric comes with an explicit linear embedding that al- lows one apply Machine Learning (ML) algorithms to the embedded measures and seamlessly modify the underlying metric for the ML algorithm to LCOT. We show that the proposed metric is rooted in the Circular Optimal Transport (COT) and can be considered the linearization of the COT metric with respect to fixed reference measure. We provide theoretical analysis of the proposed metric and derive the computational complexities for pairwise comparison of circular proba- bility measures. Lastly, through a set of numerical experiments, we demonstrate the benefits of LCOT in learning representations of circular measures.
INTRODUCTION
Optimal transport (OT) (Villani 2009 Peyré et al. 2019) is mathematical framework that seeks the most efficient way of transforming one probability measure into another. The OT framework leads geometrically intuitive and robust metric the set of probability measures, referred to as the Wasserstein distance. It has become an increasingly popular tool machine learning, data analysis, and computer vision (Kolouri al., 2017 Khamis et al. 2023). OT's applications encompass generative modeling (Arjovsky et al. [217]] Tolstikkii et al. [017 Kolouri et al. 2018)), domain adaptation (Courty et al. al. 2017 Damodaran al.) (2018), transfer learning (Alvarez-Melis & Fusil 2020: Liu et al. 2022), supervised learning (Frogner et al. 2015), clustering (Ho et al. 2017). image and pointcloud registration (Haker al.) 2004; Bai et al. 2022; Le et al. 2023). and even inverse problems (Mukherjee et al. (202]). among others. Recently there has been an increasing interest OT for measures supported on manifolds (Bonet al., 2023] Sarrazin & Schmitzer 2023). This surging interest is primarily due to: 1) real-world data is often supported on a low- dimensional manifold embedded in larger-dimensional Euclidean spaces, and 2) many applications inherently involve non-Euclidean geometry, e.g., geophysical data or cortical signals in the brain.
In this paper, we are interested efficiently comparing probability measures supported on the unit circle, aka circular probability measures, using the optimal transport framework. Such probability measures, with their densities often represented as circular/rose histograms, are prevalent in many applications, from computer vision and signal processing domains to geology and astronomy. For instance, in classic computer vision, the color content of an image can be accounted for by its hue
'These authors contributed equally to this work.
1 Acknowledges support from ONR N000142212500 and NIH GM130825.
'Acknowlegges partial support from the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001 12190135 and HR001 10001120000 2090023, and the Wellcome LEAP Foundation.

---

Published as a conference paper at ICLR 2024
in the HSV space, leading to one-dimensional circular histograms. Additionally, local image/shape descriptors are often represented via circular histograms, as evidenced in classic computer vision papers like SIFT (Lowe, 2004) and ShapeContext (Belongie et al., 2000). In structural geology, the orientation of rock formations, such as bedding planes, fault lines, and joint sets, can be represented via circular histograms Twiss & Moores (1992). In signal processing, circular histograms are com- monly used to represent the phase distribution of periodic signals (Levine et al. 2002). Additionally, a periodic signal can be normalized and represented
circular probability density function (PDF),
Notably, a large body of literature exists on circular statistics (Jamalamadaaa & SenGupta (001). More specific to our work, however, are the seminal works of Delon et al. (2010) and Rabin et al. (2011), which provide a thorough study of the OT problem and transportation distances on the circle (see also Cabrelli & Molter (1998)). OT on circles has also been recently revisited in various papers (Hundrieser et al. [022 |Bonet et al. 2023 Beraha & Pegoraro 2023] Quellmalz et al., 2023), further highlighting the topic's s timeliness. Unlike OT on the real line, generally, the OT problem between probability measures defined on the circle does not have closed-form solution. This stems from the intrinsic metric on the circle and the fact that there are two paths between any pair of points a circle (i.e., clockwise and counter-llockwise) Interestingly, however, when one of the probability measures is the Lebesgue measure, i.e., the uniform distribution, the 2- Wasserstein distance on the circle has closed- form solution, which we will discuss in the Background section.
We present the Linear Circular OT (LCCOT), a new transport-based distance for circular probability measures. By leveraging the closed-form solution of the circular 2-Wasserstein distance between each distribution and the uniform distribution on the circle, our method sidesteps the need for opti- mization. Concisely, we determine the Monge maps that push the uniform distribution to each input measure using the closed-form solution, then set the distance between the input measures based on the disparities between their respective Monge maps. Our approach draws parallels with the Linear Optimal Transport (LOT) framework proposed by Wyag et al. (013)) and can be seen as an extension of the cumulative distribution transform (CDT) presented by (Park et al. 2018) to circular probabil- ity measures (see also, Aldroubi et al. (2022 (02T)). The idea of linearized (unbalanced) optimal transport was also studied recently in various works (Cai et al.. 2022 Moosmüller & Cloninger, 2023 (Sarazin & Schmitzer 2023; Cloninger et al. 2023). From geometric perspective, we pro- vide explicit logarithmic and exponential maps between the space of probability measures on the unit circle and the tangent space at a reference measure (e.g., the Lebesgue measure) Wang et al. (013); Cai et al. (2022); |Sarrazin & Schmitzer (2023). Then, we define our distance in this tangent space, giving rise the terminology 'Linear' Circular OT. The logarithmic map provides linear embedding for the LCOT distance, while the exponential map inverts this embedding. We provide a theoretical analysis of the proposed metric, LCOT, and demonstrate its utility in various problems.
Contributions, Our specific contributions in this paper include 1) proposing computationally ef- ficient metric for circular probability measures, 2) providing theoretical analysis of the proposed metric, including its computational complexity for pairwise comparison of a set of circular mea- sures, and 3) demonstrating the robustness of the proposed metric in manifold learning, measure interpolation, and clustering/classiicatiio of probability measures.
2
BACKGROUND
2.1
CIRCLE SPACE
The unit circle S can be defined as the quotient space
g² RRZ = {(x + n: n E x x (0,1))
The above definition is equivalent to [0, 1] under the identification 0 = 1. For the sake of simplicity in this article, we treat them as indistiguuishabe. Furthermore, we adopt a parametrization of the circle as [0, 1). designating the North Pole as 0 and adopting a clockwise orientation. This will serve as our canonical parametrization.
Let denote the absolute value on R. With the aim of avoiding any confusion, when necessary, we will denote it by IR. Then, metric on S can be defined as
x - ylsi == minglr - uIR, 1 |r - U1R
F, E 1)
or, equivalently, as
yle I
min x y klR. kez
2

---

Published as a conference paper at ICLR 2024
where for the second formula 2, y R are understood representatives of two classes of equiv- alence in R/Z, but these two representatives 2, y do not need to belong to [0, 1). It turns out that such metric defines a geodesic distance: is the smaller of the two are lengths between the points x, y along the circumference (cf. Jammalamadaka & SenCuppta (200T), where here we parametrize angles between O and instead of between 0 and 2m. Besides, the circle S! can be endowed with a group structure. Indeed, as the quotient space R/Z it inherits the addition from I modulo Z. Equivalently, for any x, y E [0, 1), we can define the operations +,
I crtyFI,
if if (0,1) otherwise.
(x.
2.2 DISTRIBUTIONS ON THE CIRCLE
Regarded as set, S' can be identified with [0, 1). Thus, signals over S' can be interpreted 1- periodic functions on R. More generally, every measure E P(S!) can be regarded as a measure on R by
p(A+ n) = (AA), for every A S [0, Borel subset, and n E Z.
(2)
Then, its cumulative distribution function, denoted by Fu, is defined
Fv) = v)(0,v)) = L." du, Vy E (
(3)
and can be extended to function on IR by
Fy + 12) =- F2 (v) +n, Vy [0, n nE
Figure 2 shows the concept of F₁. and its extension to R.
In the rest of this article, we do not distinguish between the definition of measures on S or their periodic extensions into R. as well as between their CDFs or their extended CDFs into R.
functioonn Definition 2.1. [Cumulative distribution function with respect to a reference point] Let μ E P(S and consider reference point 2o E St. Assume that S is identified [0, 1) according canonical parametrization. By abuse of notation, also denote by To the point in [0, 1) that corre- sponds the given reference point when considering the canonical parametrization. We define
Fy (v) Fu + 8) Fy (zo).
The reference point To can be considered as the "origin" for parametrizing the circle [0, 1) starting from Tg. That is, To will correspond 0, and from there, we move according to the clockwise orientation. Thus, we can think of zo in the above definition as "cuttiig point": A point where we cut S' into a line by Zu and so we can unroll PDFs and CDFs over the circle into R. See Figures
23
08
10
1 and
370
Figure 1: Visualization of densities (blue and ange) on S' and after unrolling them to [0, 1) by considering a cutting point 2o. The blue density is the uniform distribution on St, represented as having height over the unit circle in black.
Besides, note that (0) Fu.ro (1) to emphasize that in the new system of coor- dinates, or in the new parametrization of S1 as
and by the 1-periodicity of μ. This
[0, 1) starting from Fu, the new origin Ty plays the role of O. Finally, notice that if Zo is the North Pole, which corresponds to 0 in the canonical parametrization of the circle, then F2 = Fp-
Definition 2.2. The quantile function u.50 [0, + [0, 1] is defined as F (v) == inf
Fa,zo (x) > y}.
2.3 OPTIMAL TRANSPORT ON THE CIRCLE
2.3.1 PROBLEM SETUP
Given μ. P E P(S)), ). let c(x, v) == h(22 ylss) ) be the cost of transporting a unit mass from x to on the circle, where h R - R4, is convex increasing function. The Circular Optimal Transport
3

---

Published as a conference paper at ICLR 2024
cost between j and v is defined
/ cx, dy(x,))))
COI(() =- inf rET(AN)) xs1
(5)
where [' is the set of all transport plans from μ to v, that is, Y T' 1/) is such that y P(S! x x having first and second marginals μ and v, respectively. There always exists a minimizer y" o and it is called Kantorovich optimal plan (see, for example, (Santambrogio (2013 Th. 1.4)).
When h(x))
|, for 1 S p < co, we denote COTa(:;)) = (OTp(s)): and (. defines
a distance on P(S"). In general,
M: MENEr / - - du(x),
COTI(HUU) inf
(6)
and minimizer M :3! S of the right-hand side of among all maps M that pushforward to y might not exist. this work, we will consider the cases where a minimizer M does exist, for example, when the reference measure
absolutely continuous with respect to the Lebesgue measure on S² (see McCann (2001); Santambrogio (2015). In these scenarios, such map M is called optimal transportation map or a Monge map. Moreover, as μ,, v E P(S can be regarded as measures on R according to equation 2 we can work with transportation maps M R - R that are 1-periodic functions satisfying Mμ =
Proposition 2.3. Two equivalent formulations COTr are the following:
[ h(] h(1F M:mo (x) F.zo (2)(R) ) dx
=oE(0.1) COI
inf
-
(7)
inf aER Jo M(FFF (x)) -F a))R dx.
When there exist minimizers Teut and O' of equation and equation respectively, the relation between them is given by
Ou Fy (F((ic FI(eue))-
(9)
Moreover, if μ = US)) and h(x) = |x/2, it can be verified that anw is the antipodal of E(v), i.e.,
aup Teut Fu(xeu)) = B(v) 1/2.
(10)
The proof of equation 8 Proposition 2.3 provided in Delon et al. (2010) for the optimal coupling
for any pair of probability measures on $1 For the particular and enlightening case of discrete probability measures on S1, we refer the reader to Rabin et al. (2011). In that article, equation is
introduced. Finally, equation 10 given for example in Bonet al. (2023 Proposition 1).
'The pushforward M μ is defined by the change of variables f p(v) dM dM = (xM()) du(x), for
every continuous function yp s' +
Nuv weto.
Figure Left: The density of a probability measure, μ. Middle: visualization of the periodic extension to R of CDF, Fy., of measure j [0, 1) ~ S!. Right: Visualization of F Facagg given in Definition 2.T where the parameterization of the circle is changed; now, the origin the point zi-
4

---

Published as a conference paper at ICLR 2024
Proposition 2.3 allows to the optimization problem of transporting measures supported on the circle as an optimization problem on the real line by looking for the best "cutting point" so that the circle can be unrolled into the real line by 1-periodicity.
Remark 2.4. In general, if strictly convex, the minimizer of equation g is unique (see Ap-
pendix A.2). but there can be multiple minimizers for equation 7 (see Figure 8 in Appendix [A.
and equation 9.. However, when a minimizer Icut of equation exists, it will lead to the optimal
transportation displacement on circular domain (see Section 2. below).
2.3.2 A CLOSED-FORM FORMULA FOR THE OPTIMAL CIRCULAR DISPLACEMENT
Let Tout be minimizer of equation 7 that is,
COTA(u, = S. h(IF (2) Pu.te. (I)) dr.
(11)
From equation [1] one can now emulate the Optimal Transport Theory on the real line (see, for e.g.. [Santambrogio (0115)): The point Feut provides a reference where one can "cut" the circle. Subsequently, computing the optimal transport between μ and boils down to solving an optimal transport problem between two distributions on the real line.
We consider the parametrization of 8 as [0. 1) by setting Teut as the origin and moving along the clockwise orientation. Let us use the notation and the notation E [0. 1) for the canonical parametrization. That is, the change of coordinates from the two parametrizations is given by x = Σ + Teutt Then, if μ does not give mass to atoms, by equation] 11 and the classical theory of Optimal Transport the real line, the optimal transport map (Monge map) that takes a point to a point ÿ is given by
[0, 1) for the points given by such parametrization,
F Fu F pezees リ
(12)
That is. 12 defines a circular optimal transportation map from j to y written in the parametrization that establishes Teut as the "origin." " If want to refer everything to the original labeling of the circle, that is, if we want to write equation 12 with respect to the canonical parametrization, we need change coordinates
T Teat
(13)
y Feut
Therefore, closed-form formula for an optimal circular transportation map in the canonical coor- dinates is given by
Mz := F- V. Far (x Ieut) + Feut y,
[0, 1),
(14)
and the corresponding optimal circular transport displacement that takes x to y is
(x
F=11 FF (a Feur) (x 100-xent Ient), x E [0,
(15)
In summary, we condense the preceding discussion in the following result. The proof is provided
in Appendix IA.] While the result builds upon prior work, drawing from Bonet al. (2023); (Rbii) Rabin
al. (201 1); Santambrogio (2015), it offers an explicit formula for the optimal Monge map.
Theorem 2.5. Let μ.v P. Assume that μ is absolutely continuous with respect to the Lebesgue measure on S¹ (that is, it does not give mass to atoms).
1. If Feat is minimizer of equation 7 then equation 14 defines an optimal circular trans- portation map. (We will use the notation M for the Monge map from p. to V.)
2. If Og minimizes equation 8 then
(y(() = F (F2(r) - app.))
(16)
3. If Do, I1 are two minimizers of equation 7 then
F-1 Fp.20 .o) + Fo Fu Fu.n, (x x1) +
Vz (0,1).
4. If the cost function strictly convex, the optimal map defined by the formula equation 14 is unique. (The uniqueness is as functions on St, or functions on R up to modulo Z).
5. If also v does not give mass to atoms, then (M My
Having established the necessary background, are now poised introduce our proposed metric. In the subsequent section, we present the Linear Circular Optimal Transport (LCOT) metric.
5

---

Published as a conference paper at ICLR 2024
3 METHOD
3.1 LINEAR CIRCULAR OPTIMAL TRANSPORT EMBEDDING (LCOT)
By following the footsteps of Wang et al. (2013), starting from the COT framework, we will define an embedding for circular measures by computing the optimal displacement from fixed reference measure. Then, the I. -is-tattece on the embedding space defines a new distance between circular measures (Theorem 3.6
Definition 3.1 (LCOT Embedding). For fixed reference measure μ E P(S!) that is absolutely continuous with respect to the Lebesgue measure on S', we define the Linear Circular Optimal Transport (LCOT) Embedding of a target measure E PPS)) with respect to the cost C for a strictly convex increasing function h R + -.,,b by
Tuth (x) == == Purtecs (Fp(x - -Feut)) - (x -eeut) = F (F) - (.r,)) - J, x x [0, 1), (17)
where Teat is any minimizer of equation 7 and O'p.e is the minimizer of equation g
The LCOT-Embedding corresponds to the optimal (circular) displacement that comes from the prob- lem of transporting the reference measure μ to the given target measure v with respect general cost COT((s))) (see equation 16 from Theorem 2.5 and equation 15).
Definition 3.2 (LCOT discrepancy). Under the settings of Definition 3.1 define the LCOL- discrepancy by
LCOT,MMVI == S(' min
( (t) 152 (u (t) + kla)) du(t), V2,02 E P(S)). EP()).
REZ
In particular, when h(.) = PP, for 1 <p< < 50, we define the LCOT,pp u.p distance as
13 Ada) = L.'
(min i (t) (200)-52hhh
LCOTup(11; v2) = uihh h Gig si 1
122 (t) + klxt dp(t)
REE
where 1P(Ss,dp) == {f S + 11fllc((4,dd) ( ((t) dult))
1/8 coo. (18)
If J US), we use the notation TP((S)) = TP(S1, dp).
The embedding y + i as outlined by equation 17 is consistent with the definition of the Logarithm
function given in (Sarrazin & Schmitzer 2023 Definition 2.7) (we also refer to Wang et al. (2013)
for the LOT framework). However, the emphasis of the embedding in this paper is on computational
efficiency, and closed-form solution provided. Additional details are available in Appendix 67.
Remark 3.3. If the reference measure is μ Un', given a target measure v E P(S)), we denote the by V. Due to Theorem 2.5 and equation 10 the expression 17 reduces to
Dut of v with respect to the cost COT2(:s)) ()) (i.e., h(x) = |x simply
[xx = F x Ex- + +2) x.
x x 10,
(19)
In this setting, we denote LCOT,.(it) simply by LCOT(..). That is, given vs, V2 E P(S)).
LCOT()), = 11 - T2l (281) - (1)1)()11))))))) -Z2(t) + klxt)
dt.
(20)
KEz
All our experiments are performed using the embedding D given by 19due due to the robustness of the closed-form formula 10lfor the minimizer o.,. of equation 8 when h( = | and μ US!).
Remark 3.4. Let μ. E PP(S)) be absolutely continuous with respect to the Lebesgue measure on S!, and h R + R, a strictly convex increasing function. Given v E P(S)).
COTH(H, (-' (1DM))(t)))) dt = S(' h (1D - pm (t)ss)) di = LCOTp,,
In particular,
COT2(1, = =100(,,))100(000)) -0000100 - I.C.T(,,

---

Published as a conference paper at ICLR 2024
Proposition 3.5 (Invertibility of the LCOT-Embeddingg Let P(S') be absolutely continuous with respect to the Lebesgue measure on S! h R + R4 a strictly convex increasing function, and let v E P(S'). Then,
V (Tu.i + id) #
We refer to Proposition A.2 in the Appendix for more properties of the LCCTT-Emeedding.
Theorem 3.6. Lei E P(S be ubsolutely continuous with respect to the Lebesgue measure on S and let h(x) = |xl". for < < co. Then LCOT p.pl::)))) is a distance on P(S)). In particular, LCOT(:.))) is distance on P.
3.2 LCOT INTERPOLATION BETWEEN CIRCULAR MEASURES
Given a COT Monge map and the LCOT embedding, we can compute a linear interpolation between circular measures (refer to Wang et (2013) for similar approach on the Euclidean setting). First, for arbitrary measures a, E P the COT interpolation can be written as:
COT ((1 ([1-t)id, t)id + tM") Pi
[0, 1].
(21)
Similarly, for fixed reference measure /4 E P(S!), we write the LCOT interpolation as:
1.COT = ((1- Pt
() () + id) + 1(0 + id)) ,r,
t E [0,1],
(22)
where we have Pi = P interpolations between the reference measure μ and two arbitrary measures V and 1/2 for COT and LCOT. As can be seen, the COT and LCOT interpolations between and v;s coincide (by definition), while the interpolation between vi and V/2 is different for the methods. We also provide an illustration of the logarithmic and exponential maps to, and from, the LCOT embedding.
a and pل = P = v. In Figure 3 we show such
11
- 0.00
0.25
0.50
0.75
t 1.00
LDE
Viteraition
LOOT
Embedding
A-0
Machine learning algorithms are applied in the Euclidean embedding
COT
LCOT
Figure 3: Left: Illustration of the LCOT embedding, the linearization process (logarithmic map), and measure interpolations. Right: Pairwise interpolations between reference measure f and measures "1 and U2 using formulas in equation (COT) and equation 22 (LCOT).
We refer to Appendix A.5.I for real data application.
3.3 TIME COMPLEXITY OF LINEAR COT DISTANCE BETWEEN DISCRETE MEASURES
with N1, N2 sorted points, the binary search algorithm requires O(N, + log(L/e) computational time find an e-approximate solution for avi.oy. If M is the least common denominator for all probability masses, an exact solution can obtained in ((N, N₂) In .). Then, for a given e > and K probability measures, {uk) each with N points, the total time pairwise compute the COT distance is O(K"N In(1/e)). For LCOT, when the reference μ is the Lebesgue measure, the optimal ap..z has closed-form solution (see equation 100) and the time complexity for computing the LCOT embedding via equation 19 is ON.. The LCOT distance calculation between v; and v/ according to equation 20 requires O(N) computations. Hence, the total time for pairwise LCOT distance computation between К probability measures, {rk) each with N points, would O(K2N +
According to (Delon et al. 2010 Theorem 6.2), for discrete measures
K N). See Appendix A.3 for further explanation.

---

Published as a conference paper at ICLR 2024
To verify these time complexities, evaluate the computational time for COT and LCOT algo- rithms and present the results in Figure We generate random discrete measures, { k=1 each with N samples, and for the reference measure, 14, we choose: 1) the uniform discrete measure, and 2) a random discrete measure, both with Nn = N samples. To calculate Oyr. we considered the two scenarios, using the binary search Delon al. (20T0) for the non-uniform reference, and using equation I0 for the uniform reference. We labeled them as, "uniform ref." and "non-uniform ref." Then, in our first experiment, we K and measured the wall-clock time for calculating COT and LCOT while varying N E {100, 200, 20000). For our second experiment, and for N (500, 1000, 5000), we vary K E {2, 4, ...... 64) and measure the total time for calculating pairwise COT and LCOT distances. The computational benefit of LCOT is evident from Figure
10a
Icot, K-2, untorm
N-600
Icoe, ren-riioo
loot. No.00, untoomm
100
loot. N-500, non-unflom
001. No1000
vellclock
10-1
loot, No 1-1000. uniform
loot. N--000. non-unitom ref.
10-2
N-5000
loot. N-5000 unfform
10-3
loot. N-5000, non-unform
500
3k
20k
100
40
50
N: size
numberr
Figure 4: Computational time analysis of COT and LCOT, for pairwise comparison of K dis- crete measures, each with N samples. Left: Wall-clock time in seconds for K = 2 and N {100, 200, .... 20000}. Right: Wall-clock time in seconds for N {500, 1000, 5000), and K E {2, 6,..., 64]. Solid lines are COT, dotted are LCOT with a uniform reference and dash- dotted are LCOT with non-uniform reference.
EXPERIMENTS
To better understand the geometry induced by the LCOT metric, we perform Multidimensional Scal- ing (MDS) Kruskal 1964) on family of densities, where the discrepancy matrices are computed using LCOT, COT, OT (with a fixed cutting point), and the Euclidean distance.
Experiment 1. We generate three families of circular densities, calculate pairwise distances between them, and depict their MDS embedding in Figure [5] In short, the densities are chosen as follows; we start with two initial densities: (1) von Mises centered at the south pole of the circle (μ=0.5), (2) a bimodal von Mises centered the east (І=00255) and west (μ=0.75) ends of the circle. Then, we create 20 equally distant circular translations of each of these densities to capture the geometry of the circle. Finally, we parametrize the COT geodesic between the initial densities and generate 20 extra densities on the geodesic. Figure 5 shows these densities in green, blue, and red, respectively. The representations given by the MDS visualizations show that LCOT and COT capture the geometry of the circle coded in the translation property in intuitive fashion. In contrast, OT and Euclidean distances do not capture the underlying geometry of the problem.
Experiment 2. To assess the separabilityy properties of the LCOT embedding, we follow similar experiment design as in Landler et al.) (202T). We consider six groups of circular density functions as in the third row Figure unimodal von Mises (axial: 0"), wrapped skew-normal, symmetric bimodal von Mises (axial: 0 and 180%), asymmetric bimodal von Mises (axial: 0" and 120%), symmetric trimodal von Mises (axial: 0%, 120 and 240%), asymmetric trimodal von Mises (axial: 0º, 240 and 225"). We assign a von Mises distribution with a small spread (k = 200) to each distribution's axis/axes introduce random perturbations of these distributions. We generate 20 sets of simulated densities and sample each with 50-100 samples. Following the computation of pairwise distances among the sets of samples using LCOT, COT, OT, and Euclidean methods, we again employ MDS to visualize the separability of each approach across the six circular density classes mentioned above. The outcomes are presented in the bottom row of Figure 5 It can be seen that LCOT stands out for its superior clustering outcomes, featuring distinct boundaries between the actual classes, outperforming the other methods.
In last experiment, consider the calculation of the barycenter of circular densities. Building upon Experiments and 2, we generated unimodal, bimodal, and trimodal von Mises distributions. For each distribution's axis/axes, we assigned Mises distribution with
Experiment 3.
8

---

Published as a conference paper at ICLR 2024
small spread (k 200) to introduce random perturbations. These distributions shown in Figure 6 (left). Subsequently, we computed both the Euclidean average of these densities and the LCOT barycenter. Notably, unlike COT, the invertible nature of the LCOT embedding allows us directly calculate the barycenter as the inverse of the embedded distributions' average (see Appendix [A.4).
The resulting barycenters illustrated in Figure 6 As observed, the LCOT method accurately
recovers the correct barycenter without necessitating additional optimization steps.
Uniniodafyon
Transition from
Betributions
Unimodal Simodal
Distributions
with LCOT distance
MDS COT d staance
MDS with GT distance (cut at
MDS with Euclidean distance
Wra.oped Skew Norm
von Mises Trimodal Symmettic
Mises Trimodal Asymmetric
Bimodal Symmetric
Binodal Asymmetric
MDS with LCOT distance
MDS with COT distance
MDS with OT distance (cut at 0)
MDS with Euclidean disaacce
Venmioes
Vonmices Bimedal Symmetric Vonmises Simodal Asymmetiic
Vonmites Trinddal Symmetric
Vonm Thimeda: Asymmetric
Wrapped
Figure 5: MDS for embedding classes probability densities into Euclidean space of dimension 2 where the original pair-wise distances (COT-distance, LOT-distance, Euclidean or L distanne are preserved as well possible.
Mises
B-MMuial
TriMMalll
Eucildean Barycanter
LCOT Barycanter
000
Figure 6: The LCOT barycenter compared to the Euclidean mean.
CONCLUSION AND DISCUSSION
In this paper, we present the Linear Circular Optimal Transport (LCOT) discrepancy, a new met- ric for circular measures derived from the Linear Optimal Transport (LOT) framework Wang et al. (013)) et al. 6216); Park et al. (2018); Cai et al. (2022); Aldroubi et al. (2022); Moosmüller Cloninger (002)) The LCOT offers 1) notable computational benefits over the COT metrie, particularly in pairwise comparisons of numerous measures, and 2) linear embedding where the ||< between embedded distributions equates to the LCOT metric. We consolidated scattered and introduced the LCOT metric and embedding, validating LCOT as a metric Theorem 3.6 In Section 3.3 we assess LCOT's computational complexity for pairwise comparisons of K circular measures, juxtaposing it with COT. We conclude by showcas- ing LCOT's empirical strengths via MDS embeddings on varied circular densities using different metrics.
results on circular OT into Theorem and

---

Published as a conference paper at ICLR 2024
REFERENCES
Akram Aldroubi, Shiying Li, and Gustavo Rohde. Partitioning signal classes using transport transforms for data analysis and machine learning. Sampling theory, signal processing, and data analysis, 19(6); 2021.
Akram Aldroubi. Rocio Diaz Martin, Ivan Medri, Gustavo K Rohde, and Sumati Thareja. The signed cumulative distribution transform for 1-d signal analysis and classification. Foundations of Data Science, 4: 163, 2022.
David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21428-22 22239,,,,, 2020.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pp. 214-223. PMLR, 2017.
Yikun Bai, Bernhard Schmitzer, Mathew Thorpe, and Soheil Kolouri. Sliced optimal partial trans- port. arXiv preprint arXiv:2212.080453 2022.
Serge Belongie, Jitendra Malik, and Jan Puzicha. Shape context: A new descriptor for shape match- ing and object recognition. Advances in neural information processing systems, 13, 2000.
Mario Beraha and Matteo Pegoraro. Wasserstein principal component analysis for circular measures. arXiv preprint urXiv:2304.02-D0 2023.
Clément Bonet, Paul Berg, Nicolas Courty, François Septier, Lucas Drumetz, and Minh-Tan Pham. Spherical Siced-Wasserstein. ICLR, 2023.
Carlos A Cabrelli and Ursula M Molter. A linear time algorithm for matching problem on the circle. Information processing letters, 66(3):161-164, 1998.
Tianji Cai, Junyi Cheng, Bernhard Schmitzer, and Matthew Thorpe The linearized hellinger- kantorovich distance. SIAM Journal on Imaging Sciences, 15(1):45-83, 2022.
Alexander Cloninger, Keaton Hamm, Varun Khurana, and Caroline Moosmüller. Linearized Wasser- stein dimensionality reduction with approximation guarantees. arXiv preprint arXiv:2302.07373. 2023.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution op- timal transportation for domain adaptation. Advances in Neural Information Processing Systems, 30, 2017.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Proceedings of the European conference on computer vision (ECCV), pp. 447-463, 2018.
Julie Delon, Julien Salomon, and Andrei Sobolevski. Fast transport optimization for Monge costs on the circle. SIAM Journal on Applied Mathematics, 70(7):223--2258, 2010.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learn ing with a Wasserstein loss. Advances in neural information processing systems, 28, 2015.
Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent. Optimal mass transport for reg- istration and warping. International Journal of computer vision, 60:225-2400 2004.
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung- Multilevel clustering via Wasserstein means. In International conference machine learning, pp. 1501-1509, PMLR, 2017.
Shayan Hundrieser, Marcel Klatt, and Axel Munk. The statistics circular optimal transport. In Di- rectional Statistics for Innovative Applications: A Bicentennial Tribute to Florence Nightingale, pp. 57-82. Springer, 2022.
Rao Jammalamadaka and Ashis SenGupta. Topics in circular statistics, volume 5, world scientific, 2001.
10

---

Published as a conference paper at ICLR 2024
Abdelwahed Khamis, Russell Tsuchida, Mohamed Tarek, Vivien Rolland, and Lars Petersson. Earth movers in the big data era: A review of optimal transport in machine learning. arXiv preprint arXiv:2305.055000 2023.
Soheil Kolouri, Akif B Tosun, John A Ozolek, and Gustavo K Rohde. A continuous linear optimal transport approach for pattern analysis in image datasets. Pattern recognition, 51:453-462, 2016.
Soheil Kolouri, Se Rim Park, Matthew Thorpe, Dejan Slepcev, and Gustavo K Rohde. Optimal mass transport: Signal processing and machine-learning applications. IEEE signal processing magazine, 34(4):43-59, 2017.
Soheil Kolouri, Phillip E Pope, Charles E Martin, and Gustavo K Rohde. Sliced Wasserstein auto- encoders. In International Conference on Learning Representations, 2018.
Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to nonmetric hypothe- sis. Psychometrika, 29(1); 1964.
Lukas Landler, Graeme D Ruxton, and E Pascal Malkemper. Advice on comparing two independent samples of circular data biology. Scientific reports, 11(1):20337, 2021.
Tung Le, Khai Nguyen, Shanlin Sun, Kun Han, Nhat Ho, and Xiaohui Xie. Diffeomorphic de- formation via sliced Wasserstein distance optimization for cortical surface reconstruction. arXiv preprint arXiv:2305.17555 2023.
Joel Levine, Pablo Funes, Harold B Dowse, and Jeffrey Hall. Signal analysis of behavioral and molecular cycles. BMC neuroscience, 3(1):1-25, 2002.
Xinran Liu, Yikun Bai, Yuzhe Lu, Andrea Soltoggio, and Soheil Kolouri. Wasserstein task embed- ding for measuring task similarities. arXiv preprint arXiv:2208. 11726, 2022.
David G Lowe. Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60:91-110, 2004.
Robert J McCann. Polar factorization of maps riemannian manifolds. Geometric & Functional Analysis GAFA, 1 113): 2001.
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.
Subhadip Mukherjee, Marcello Carioni, Ozan Öktem, and Carola-Bibiane Schönlieb. End-to-end reconstruction meets data-driven regularization for inverse problems. Advances in Neural Infor- mation Processing Systems, 34:21413-21444441 2021.
Se Rim Park, Soheil Kolouri, Shinjini Kundu, and Gustavo K Rohde. The cumulative distribution transform and linear pattern classification. Applied and computational harmonic analysis, 45(3): 616-641, 2018.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ Machine Learning, 116-66):355-677 2019.
Michael Quellmalz, Robert Beinert, and Gabriele Steidl. Sliced optimal transport on the sphere. arXiv preprint arX1v22304.00092, 2023.
Julien Rabin, Julie Delon, and Yann Gousseau. Transportation distances on the circle. Journal of Mathematical Imaging and Vision, 41:147- -17,, 2011.
Santambrogio. Optimal Transport for Applied Mathematicians. Calculus of Variations, PDEs and Modeling. Birkhäuser, 2015.
Clément Samazin and Bernhard Schmitzer. Linearized optimal transport manifolds. arXiv preprint arXiv:2303.1 /3901, 2023.
Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto- encoders. arXiv preprint 1rXiv: 2017.

---

Published as a conference paper at ICLR 2024
Robert Twiss and Eldridge M Moores. Structural geology. Macmillan, 1992.
Cedric Villani. Optimal transport: old and new. Springer, 2009.
Wei Wang. Dejan Slepëev, Saurav Basu, John A Ozolek, and Gustavo K Rohde. A linear optimal transportation framework for quantifying and visualizing variations in sets of images. Interna- jiona of computer vision, 101:254-269, 2013.
12

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1
PROOFS
Proof of Proposition 2.3 The proof of Proposition 2.3 is provided in Delon et al. (2010) for the optimal coupling for any pair of probability measures on S For the particular and enlightening case of discrete probability measures on S', we refer the reader to Rabin et al. 2011).
For completeness, notice that the relation between 2g and hols by changing variables, using 1- periodicity of μ and v and Definition 2.2 (see (onect et al. 22033 Proposition I)):
J. h(F p.zo (x) Fu (z) dr
M1(F -0) (xo()) (Fol-+ xx0) Fx(z))) do
h((FF - -E(()))) - (F& - Fx(x)) (x) (R) dx
h((FT Fa(oo) Fy (x Fu de
[ h(1F7 (x + Fx(0)) - Fu(xo)) - (z)la)
In particular, if h(z)= = |z|?, and μ Unif(S'), then
COT2(,,V) inf acR
(x FF (x + a) (x)
inf acR
1 a F- (x)) dr
(F)((x) (x)) - x dx 20 I' (F x) de + a²
inf aER
J0
FF (x) x dx 2a ( xdv(x)
1
inf aER
- - a²
1)
inf acR
FF (x)) (x:) - 2 dx 20
E(v)
+ a²
2
/ |F (x) - x dx 2 B(v) 1 2
apir
Therefore, in this case, the minimizer an of equation g unique and has the closed-form ap B(v) - 1/2.
We will show that, in general, the minimizer Otp,v of equation 8 is unique. Our arguments are based on the paper Delon et al. (2010). Specifically, the role played by the function (F*)-1 where 5 (x) F(x) + 9 in Delon et (2010) substituted by F F a) in our case
Proof of Remark 2.4
(i.e., our parameter a correspond to -B in the mentioned paper).
Our hypotheses are the following:
1. Let c(x, y) h(2= y/) for h IR. R4 strictly convex (for example h(x) |a<| with p > 1), or, more generally, l : R x R + IR satisfying the Monge condition or the (strict) cyclical monotonicity condition:
c(u1, v1) + c(u2, 02) < c(ui, v2) c(u2, v1) Vun
02, Un < U2-
(23)
13

---

Published as a conference paper at ICLR 2024
2. Let μ. be two probability measures absolutely continuous with respect to the Lebesgue measure on S!.
The idea of the proof will rely showing that the cost function
Cost(a) := f c(F) (2), (2)), c(FFT'(0),
F a:)) dx
(24)
strictly convex and continuous (as a function on a), and so has a unique global minimum (that we will denote by (.,.).
Let
(p,( = c(F, F,))
(25)
Under the above conditions, it holds that (.,((:.)) satisfies the Monge condition equation 23 Then, to prove strictly convexity of Cost(a) ) is sufficient to show that
a + a"
Cost(a') Cost(a")
Cost
(26)
2
Assume a' a and let a = a'
On the one hand, since 2
I Cu - a) de
Cost (a)
lta"-a
JanLa cuul2, σ dr
Caply a"" a.y a') dy.
where in the last line we used the change of variables xa" o and the fact that - a' Therefore,
2 Cost (a) = =/[- (,,(2,2- dz /''d (u a" -Q, a') dz.
(27)
On the other hand, by repeating the same idea we have,
Cost(a") = (' (nolExx- -aa dx
lta"
Cup(E, a") dr
Ja"aa
= S-" Cnely+ + aa - ax, a) dy.
and
Cost(a') + Cost(a") - //'² cuu(2,2- - dz /'' aaulz+a"-aa -ā,2 (a) de. (28)
Since u1(2) := < 2 a =: uz(x) and U1 (2) == - a' =: =: 02(2), we have that uz), + c(u2(2), (2)) < c(u, (2), v2(2)) + c(u2(2)) 0) (2))
because (.)) satisfies Monge condition equation 23 Thus, from equation 27 and equation 28 we obtain
Cost((a)= = S (u
J (n)()) (2()) dz
[ (u)((u 02(2)) dz + (' (u)(()(z)) 1n (2)) dz = Cost(a') + Cost(a"),
and equation 26 holds. The continuity of Cost(a) holds the integral in equation 24 is
finite for all a.
14

---

Published as a conference paper at ICLR 2024
Remark A.I. We mention that in the case that c(x.y) y) h(x y) for h(z) |z| (studied for example in Cabrelli Molte (1998); Hundrieser et al. (2022)) we have convexity but not strictly
convexity. However, the authors in Hundrieser al. (2022) prove that closed-formulle for mini- mizer Op, of equation
p. min arg min ( (F Fu)(() - uldt
UER
called the Level Median of the function Fj. Fv. To show that, is used the fact that in this case equation 8 takes the form
/ (F2(1) Fu(1) aldt. aek
COT((H
inf
Proof of Theorem 2.5
1. First, will show that the map My given by equation 14 satisfies (M v. Here μ and are the extended measures form S having CDFs equal to F₂ and F,, respec- tively, defined by equation 3 and 4 By choosing the system of coordinates ž E [0, 1) that starts at Tout (see Figure
then,
(z) = Fu.teu. o Fp. (7)
(see equation 12g Let Mary and Uxeut be the (1-periodic) measures on R having CDFs Fur and F. te respectively, i.e., Fu, (i) Pizeue ([0, 3)) (analogously for Vseuc ) That is, we have unrolled and from S! to R, where the origin IR corresponds to Feut E E!! (see Figure [). Thus, a classic computation yields
(Frdeuue F FF. #1llown (Frteene ) ((F ) (onm) (Frr (Fvideue #Lo' Uzent
where Lsi Uni denotes the Lebesgue measure on circle. We used that (Pu) Lg: μ does not give mass to atoms, and so, if we change the system of coordinates we also have (Fu ) = Lzr.
Finally, have to switch coordinates. Let
2 == T + Reut
(that is, =(x) .2). To visualize this, Figure 7 It holds that
(29)
(where we recall that v is the extended measure form S to IR having CDF equal to F, as in equation 3 and 4 Let us check this fact for intervals:
V Your (la, b]) =
Voeue (z ( bl)) ==(
Prene (la Teut: IeutI)
Fu. (b- Deut) - Fuzzouel (a Ieut)
(b) FA( (Fr(a) Fx(uuu)))
= =F((b) Fa(a)
vr(aab)).
Besides, it holds that
F Fp.zone (. 11 Unif(
(30)
in the sense that is the Lebesgue measure S! extended periodically (with period 1) to the real line, which we denote by Lgt. Let sketch the proof for intervals. First, notice that Fu.seaie (xr Leut) Fx(x) (went) and so its inverse + F- (y Jewt). Therefore.
(Fp. ( - H (la, b)) (IF) (a + Vent), F.- Feue)))
Fy, (F) (a xeat)) - F, (F F--1 1(b (b- Fewt)) h
15

---

Published as a conference paper at ICLR 2024
2 Tt + 2 cut
Cut
Tc
Figure 7: The unit circle (black) can be parametrized as [0, 1) in many different ways. In the figure, we marked in black the North Pole as O. The canonical parametrization of S identifies the North Pole with Then, also in black, we pick a point Zeut- The distance in blue that starts at equals the distance in red I that starts at Zeut plus the corresponding starting point Zeat. This allows us to visualize the change of coordinates given by equation 13
Finally,
(MH) (Fo (Fanooue Ieut) + Texet) # P
(2(F (Fpiteual Deua)))) # P
Za (F # (inueeul Teutt ) #
2# (Fedeene ) CBg
(by equation 30
24 Veeue
(by equation 29
Now, let us prove that My is optimal.
First, assume that j is absolutely continuous with respect to the Lebesgue measure on S! and let fμ denote density function. We will use the change variables
Fp. (x Ieue) Fx(x) FF (Zeut) du fa(x) dr.
So.
S' M(IMM())) x012)d((1) = [ h(( Viecu (Fpsteuete (x keutt) (xr Ien)) fu(z)dæ
4p(a))
1-Beuu
d F Meteeu (u) Mattoue (u) du
Rent
M(F Mileee (1) F=1 Pinteue (u)lz) du
COTA(H,P)
Now, let us do the proof in general:
S h(IM z/R) dp(x)
[' h(( h((Fr (F Dentt)) (x Fewet) (R) du((z)
he( 1o(FF Mitoou (v) - F-1
Misiout (v) dl FF ( - kent #1((8)
h(( Fileee (1) F-1
Mote (u)le) du
= COTI(H,
In the last equality we have used that F Fu.senee (- Dene) tf is the Lebesgue measure (see equation 30
16

---

Published as a conference paper at ICLR 2024
2. Using the definition of the generalized inverse (quantile function), we have
[f)
Fur (Frizone (xc Feutt) Ficut
inf Fur (x') > F P'iittut 1x Deut)} } + Deeut
inffx' Fo(x' + Feut) Fe(Fect) > F2(x) FF(eua))) + Feut
>inff(' Fo + Fcutt
> Fu(x) Fa((Fcut) F(Fcutt) Fout
iinf(x' Fy(x' + Fews) > Fu(x) auuu) + Teut
>inf(y Icat Fy(y) > Fx(x) apIi) + Feut
= =inf(y: Fo(v) Fa(#) (g + Tcut Veut
(P,(() a,,.).
3. This part follows from the previous item the right-hand side of equation 16 does not depend on any minimizer of equation] 7
4. From McCann 2001 Theorem 13), there exists unique optimal Monge map for the
optimal transport problem on the unit circle. Therefore, by using Remark 2.4 ME is the
unique optimal transport map from ja to v. For the quadratic case h(x) = - 2 we refer for example to Santambrogio (2015) Th. 1.25, Sec. 1.3.2)). Moreover, in this particular case, there exists function & such that (x) = r Vp(x),, where yp is a Kantorovich
potential (that is, solution to the dual optimal transport problem on S²) and the sum is modulo Z.
5. The identity (MØ)- = (ME) holds from the symmetry of the cost equation 5 that one should optimize. Also, it can be verified using equation and the fact that from equation On2 -.
MD a (x = FT- (F - -ap,)) - (he,p)
= =F (Fa(1) - O2p.v + (...)) = I.
Proposition A.2 (Properties of the LCOT-Embedding). Let a E P(S)) be absolutely continuous with respect to the Lebesgue measure on S) and let P(S").
1. puh O.
2. Da. (x) E 11-0.5,0.5) for every x (0,
3. Let 11,12 E P(81) with vi that does not give mass to atoms, then the map
M == (6g t. 07 mibh o ((1 uhh + id)- id, satisfies My V/ (however, not necessarily an optimal circular transport map).
(31)
Proof of Proposition A.2
1. It trivially holds that the optimal Monge map from the distribution to itself is the identity id, or equivalently, that the optimal displacement is zero for all the particles.
2. It holds from the fact of being the optimal displacement, that is,
/ h() x/31) du(x)) / h(lpuh (z))as) d((())
COTA(,,
inf
M: M.
and from the fact that l2lg is at most 0.5.
3. We will use that Dusk My id, and that (MK)- My:
17

---

Published as a conference paper at ICLR 2024
M(x) (62 07 (1 My (x) + x
(ME - M o MY (I) +
MM a My (2) - x +
Mr o (x).
Finally, notice that
(M Mt )4 #4 = (M+)) # ((ME) = (Mz)) )
Now, we will proceed to prove Theorem 3.6 LCOTpp((:-)11 endows P(S') with metric-space structure. The proof based on the fact that we have introduced an explicit embedding and then we have considered an L d.--distnce. It will follow that we have defined kernel distance (that is in fact positive semidefinite).
By having this result, it is worth noticing that
Proof of Theorem 3.6 From equation 20 it is straightforward to prove the symmetric property and non-negativity.
11 = 12, by the uniqueness of the optimal COT map (see Theorem 2.5 Part 3), we have 0j uhh
D2 u.A. Thus, (VI, ;2) O.
For the reverse direction, L. = 0, then
h(min [1 kEZ
u.h (x) 1. (x) + kl}) =0
/ a.s.
Thus,
6 M. (x) E 02 u.h (x)
- a.s.
(where 1 stands for the equality modulo 2). That is,
M (x) 1 u.h (x) - r 1 By uhh (x) + x M7 (x)
a.s...
Let C 10, denote the set of x such that the equation above holds, we have ((S) = (((s)) (S))
0. Equivalently, for any (measurable) B C St, 4(B n) = BB). Pick any Borel set A C CS!, we have:
21 (A) 1 ((M)))
= (MM()))
=M((
=M((MP))
=A((A)
(32)
where the first and last equation follows from the fact M M are push forward mapping from μ to U1, 12 respectively.
Finally, we verify the triangular inequality. Here will use that h(x) |x, for $ p co. Let V1, P3 E ).
( (151()) (10)00))) (t))ss )r du((t)
1/2
(171(1) - (,(1)s: + +1((()) - (t)))) du(t) 1/8
(f. (1()) - (0)) au(t)
1/p (f. (8s(t) (t) du(t)
1/P
I.OOTp,(MI 1/) LCOOT 1/p
where the last inequality holds from Minkowski inequality.
18

---

Published as a conference paper at ICLR 2024
A.2 UNDERSTANDING THE RELATION BETWEEN THE MINIMIZERS OF EQUATION AND EQUATION
We briefly revisit the discussion in Section equation 2.3.1 specifically in Remark equation 2.4 concerning the optimizers Ficut and Op, of equation and equation respectively.
Assuming minimizers exist for equation 7 and equation we first explain why we adopt the ter- minology "cutting point" (Zeus) for minimizer of equation 7 and not for the minimizer au of equation g On the one hand, the cost function presented in 7 is given by
Cost(zo) == h(1 M100 (z) - F (x)) dz.
(33)
We seek to minimize over Tu E [0, 1) S', aiming to find an optimal that affects both CDFs Fμ and Fp. By looking the cost for each fixed Zy, we change the system of reference by adopting To the origin. Then, once an optimal is found (called Fewr), leads to the optimal transportation displacement, providing a change of coordinates to unroll
CDFs of μ and into R and allowing
the use the classical Optimal Transport Theory on the real line (see Section equation 2.3.2 and the proofs in Appendix equation A.I). On the other hand, the cost function in is
Cost(a) =- [ (x (x))l))
and the minimization runs over every real number a. Here, the shift by a affects only of the CDFs, not both. Therefore, it will not allow for consistent change in the system of reference. This why we do refer to as cutting point in this paper, but we do refer to the minimizer of equation 7 as Teut-
Finally, Figure X below is meant to provide visualization of Remark 2.4 that is, show through an example that, when minimizers for 7 and equation g do exist, while one could have multiple minimizers of the minimizer of unique.
Densities on the circle
Cost as funtion of Xe
8
4-
Target density, v Uniform density,
Cost [ F' F. Dd
2-
0
0.0
0.2
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Xo
Cost function of
Close formula for the optimal
Cost
11 ix
(x
F,lx) F,0x)
optimal a
optimal
-0.2-
-0.4
-0.2
0.0
0.2
0.4
0.0
0.2
0.4
0.6
0.8
1.0
x
Figure 8: Top left: Uniform density, μ4, and random target density on $1, Top right: The circular
po transportation cost fo | (z)- F=11 (2 dr is depicted as a function of the cut, un. showing that
the optimization in equation ( can have multiple minimizers. Bottom right: Following equation 9 we depict the difference between the two CDFs, F2 (x) FF((), for each x E [0, 1) $ As can be seen, for the optimal cuts (dotted red lines), the difference is constant, indicating that the optimal for equation i unique. Bottom left: The optimizer for the circular transportation cost in equation unique, and given that y the uniform measure, has a closed-for form solution E(v) 2.
19

---

Published as a conference paper at ICLR 2024
A.3 TIME COMPLEXITY OF LINEAR COT
In this section, we assume that we are given discrete or empirical measures
First, mention that according to (Delon al. 2010, Section 6), given two non-decreasing step functions and G represented by
[II,..., XN,,, (z1),....... ..... [[]
and
[[y..... .rah [G(y)).... G(y)),,
the computation of an integral of the form
(dr- dr
requires ON1 + N2) evaluations of a given cost function c(:s))
Now, by considering the reference measure 1 Uni will detail our algorithm for comput- ing LCOT(rI, Let us assume that V1, P2 are two discrete probability measures on St having N1 and N2 masses, respectively. We represent these measures v4 E m2622 (that is, has mass my at location 2r for j 1,...,,Nri Ni. and analogously for v2) as arrays of the form [ Nx [mi....,m's
== 1,2.
Algorithm to compute LCOT:
1. For i = 1,2, compute O',,, = B(()) - 1/2.
2. For 1, 2, represent Fe, (-) + api, as the arrays
(ef....,.y..
..y. [c.
where
c= + m,j. for ...... N,. ci = m 0ppe
3. Use that
F, F (p..)) = (F(()) axx)
and the algorithm provided in (Delon et al. 2010 Section 6) mentioned above with F Fz, (-) + an,, and G = F2, (.) + anm to compute
LCOT(VI, v2) 1 12 1
{ (F (x: (ppi)) - x)) (Fiz(( (x app,z) - xx) 1sg dr
(Foz (F (-) + amn (x) + ap,uz) ) (x)lg. dx
G
Each step requires O(N1 + N2) operations. Therefore, the full algorithm to compute LCOT of order ON1 + N2).
A.4 LCOT BARYCENTER
Although the following definition holds for any non-atomic reference measure E P(S)), for simplicity, we consider the reference measure as = USt.
Given N target measures vi...., UN PP(S),, ) as LCOT((s)) :) is distance, their LCOT barycenter defined by the measure vú such that
1/3 argmin
N Σ ICOTs(V,U)) arg
Σ D D3 11A
N
It is worth mentioning that for some applications, the L.CTT framework can be also used for continuous densities, in the case of the CDT et al. (0018.
20

---

Published as a conference paper at ICLR 2024
In the embedding space, it can be shown that the minimizer of
N
argming
1
Dy
N
given by the circular mean
Σ レi= sin ( (x))
v(x) = circle mean mean((( (1))
UN (x))) =
arg tan
2T
Σi=1 cos (TT)
For each [0, 1), the last value is the average of the angles {2Th (z)..... ... 2TVN (z)), which is then normalized to fall within the range [-0.5, 0.5) By using the closed formula for the inverse of the LCOT Embedding provided by Proposition 3.5 the LCOT barycenter between
go back to the measure space obtaining
VN as
(D + id) #1.
(34)
In our experiments, use the expression equation
34
A.5 EXTRA FIGURES AND EXPERIMENTS
The following Figure is from an experiment analogous to Experiment but for different family of measures (Figure Left). We include have intuition of how the LCOT behaves under translations and dilations of an initial von Mises density.
300
Standard deviation, 0.05
NOS OT distance
MDS Euclidean distance
Figure 9: MDS for embedding classes of probability densities into an Euclidean space of dimension where the original pair-wise distances (COT-distance, LOT-distance, Euclidean L I2-distance) are preserved as well as possible.
A.5.1 LCOT-INTERPOLATIONN REAL DATA APPLICATION
Hue transfer experiment: In Figures 10 and 12 we interpolate the hue channel between pairs of images using LCOT interpolation (given by equation 22) and COT interpolation (given by equa- tion 2T). Given pair of images, one is considered as source and the other as the target. Each image of M x N pixels is represented using Hue, Saturation, and Value channels (HSV). We com- pute censity-normaliied histogram of the Hue values across all pixels and consider this histogram as circular density. Each bin represents at the same time color variety (Hue value) and a point (angle) in the circle. Thus, displacements in the circle correspond to color conversions. Each inter- polation (LCOT COT) provides curve of color conversions parametrized between O (source) and = 1 (target). For three different pairs images, Figures I0 and [ depict color-converted images using steps / 0.25, 0.5, 0.75 for each interpolation type.
21

---

Published as a conference paper at ICLR 2024
Image
1n
Targe Image
CoT
Figure 10: LCOT and COT color interpolations.
Image
Target
LCOT
Figure 11: LCOT and COT color interpolations.
bw0.25
b=0.75
LCDT
Figure 12: LCOT and COT color interpolations.
22

---

Published as a conference paper at ICLR 2024
A.5.2 LCOT FOR HUE-BASED IMAGE RETRIEVAL
Given a data set of 100 flower images represented using hue, saturation, and value channels (HSV), use the hue channel for image retrieval. For this, the hue information of image is used as a primary feature for searching. We extract the hue component from the images of the data set and compute density-normalized histograms of the hue values across all pixels. We consider these histograms as circular densities { (similarly to A.5.1)
For LCOT comparison and retrieval, we compute the LCOT transforms {0.),- Given a new query image, compute its hue histogram denoted Then, we perform LCOT-matching that is, we embed the input image in LCOT space by computing so that we can calculate N squared Euclidean distances || l (i.e., the obtained LCOT-distance values in ascending order. In Figure 13 we show the four closest and furthest images recovered using this technique.
computing I.CO22 V/) for i = 1,.... N). We sort
In Figure we repeat the same experiment but using classic COT-matching for the same data set. As before, given a query image, we first compute hue histogram denoted by d. Then, we perform N COT-distances COT2(a, v4),, for i = ,,... N, and We sort the obtained COT-distance values.
Closect images retrived using LCOT distance
Query Image
imuges using disence
Figure 13: LCOT-approade for Hue-based image retrieval. The leftmost image is the original query image. In the upper row, we retrieve the 4 closest images in Hue space according to LCOT, while the bottom shows the 4 furthest images with respect to LCOT-distance.
Clirund retreued CCT didtanze
Quary Image
Furthest images retneved using COT distance
Figure 14: COT-distance for Hue-based image retrieval. The leftmost image is the original query image. In the upper row, we retrieve the 4 closest images in Hue space according to COT-distance, while the bottom shows the 4 furthest images with respect to COT-distance.
In both figures, the retrieval of images with similar color content is evident. The advantage of using LCOT over COT is that when using COT each new image requires to solve N new circular optimal transport problems whereas LCOT only requires to solve one followed by N Euclidean distance calculations for comparison and sorting. For M queries when using the COT approach (N for each query) but only solve N + COT problems when using LCOT (N for pre-procsssing the data one per query).
have to compute MN COT distances
23

---

Published as a conference paper at ICLR 2024
A.6 UNDERSTANDING THE EMBEDDING DIFFERENTIAL GEOMETRY
Our embedding v + V as given by equation equation 17 aligns with the definition of the Logarithm
function presented in (Sarrazin & Schmitzer 2023 Definition 2.7). To be specific, for μ4, g and the Monge mapping M. the Logarithm function as introduced in Sarrazin & Schmitzer (2033 expressed as:
P2(S') v log, CoT (v)(()) L (
Here, the tangent bundle of st is represented as
TS' = (1,,
where (St) denotes the tangent space at the point E St. The space (3) :T3; (4) is the set of vector fields on S' with squared norms (based on the metric on TS', ), that are y-integrable. The function (vector field) logp COT (p) is defined as:
log,
COT
(v) = (S 3 x (x. Ux)) E TS
where Ug (S') is the initial velocity of the unique constant speed geodesic curve + T (x).
The relation between log,, Si, the spaces T, (S!) and can be parameterized by R and [0, 1). respectively. Then, the unique constant speed curve x MK (I)) is given by:
COT (v) and i' in equation 19 can be established as follows: For any æ in
(t) = + ((M x), Vt E [0, 1].
Then, the initial velocity is My (3) ) - r. Drawing from equation 15 Theorem 2.5 and Proposition A.2
find ((x) (x) for all æ in S1, making 1 and log Tog (v) equivalent.
However, it is important to note that while log, COT is defined for a generic (connected, compact, and )omplete manifold, it does not provide a concrete computational method for the embedding log, COT Our focus in this paper is on computational efficiency, delivering closed-form formula.
Regarding the embedding space, in Sarrazin & Schmitzer 2023 the space L ,TS::l ()) is equipped with the L induced by TS. Explicitly, for any J belonging to L L' ;))
1 - /.'' [l = / 1x
where l=: represents the parameterizing gl and T,(3) (8') as [0, 1) and R, respectively, this squared norm becomes [fxx) Consequently, L2 75 :)) becomes an inner product space, whereby the expression (polariza- tion identity) [|ʃ + g|l² 11 1|g|| establishes an inner product between f and g.
square in the tangent space (S!) of the vector f(x). By
However, in this paper, the introduced embedding space T,2 du.) presented in equation 18 space uses the T,2-norm on the circle, defined for each f in (S) du) as:
This
/ [5()) du.
| (s):dd))
Unlike the previous space, this does induce an inner product (in fact, |- not norm). As such, throughout this paper, term our embedding "linear embedding" rather than "Euclidean embedding".
In Sarrazin & Schmitzer (2023). the Riemannian manifold is not necessarily compact. However, the mea- sures μt, have compact support For brevity, have slightly overlooked this difference.
24


Reviews:
[{"review_id": "3CknYtfre2", "reviewer": "Reviewer_5tYi", "summary": "This work studied the optimal transport on the unit circle. Since in the optimal transport on the circle, $x_\\text{cut}$ in Eqs. (7) and (9) is not obtained in the closed-form, the optimal transport on the circle does not have a closed-form solution. This work proposed its approximated variant, LCOT, such that LCOT has the closed-formued solution. Then, this work showed that in the special case, LCOT became equivalent to the original optimal transport on the circle (Remark 3.4) and evaluated the effectiveness of LCOT in the synthetic data.", "questions": "1. Could the authors explain the definition of LCOT, including Eq. (17) and equations in Def. 3.2, more intuitively?\n2. Remark 3.4. claimed that the COT and LCOT are equivalent. Can it be proved that the barycenter under COT and LCOT are also equivalent?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. In Fig. 4, this work demonstrated that the LCOT can be computed much faster than the original optimal transport on the circle, which is consistent with the theoretical analysis.\n2. The relationship between the original optimal transport on the circle and the LCOT is discussed in Remark 3.4.", "weaknesses": "1. The intuitive interpretation of LCOT, including Eq. (17) and equations in Def. 3.2, is not clear to the reviewer.\n2. The authors claimed that \"invertible nature of the LCOT embedding allows us to directly calculate the barycenter\" in Sec. 4, but the algorithm is missing. It is important for future research to show detailed algorithms in this paper.\n3. In Fig. 4, the unit (e.g., seconds, mili seconds) is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fn8ANP2vg9", "reviewer": "Reviewer_Hihy", "summary": "Standard OT metrics are well studied on data sample points having Euclidean structure, e.g. Wasserstein and Gromov-Wasserstein distances. Recently, the OT community addresses gained ample interest in OT metrics on non-Eculean spaces. This paper investigates OT between measures supported on the unit circle, aka circular probability measures. The paper starts with a background on circular OT by defining probability measures with 1-periodicity. This gives the CDF function with respect to a reference point. Proposition 2.3 is quite interesting since it expresses the COT between circular probability as an optimization problem on the real line by searching cutting points $x_{cut} \\in [0,1)$. Using classical optimal transport on the real line, we can construct the Monge map between data points on the circular probability measures. \n\nThis work proposes LCOT a new discrepancy between circular probability measures, allowing to embedding the origin measures by computing their Monge map with respect to a fixed reference measure (uniform or Lebesgue measure). If the cost function is the $p$-power of the absolute value, then LCOT is a proper distance and coincides with the $L_p$ norm on the unit circle endowed with the reference measure.", "questions": "### Related work\nMissing related work: \"The Statistics of Circular Optimal Transport\" by Hundrieser et al. 2022.\n### Minor Typos\n- Page 6: Definition 3.2 ``(LCOT distance):``  I think should be (LCOT discrepancy)\n- Page 7: Caption of Figure 4: \"Left: Wall-clock time for $K=2$ and $N \\in \\{100, 200, \\ldots, 20000\\}$\"\n- Page 9: first line of conclusion \"distance\" --> \"discrepancy\n- Page 10: References: wasserstein --> Wasserstein", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Paper easy to follow and well written.\n- Proposing a novel linearization of the circular OT metric (LCOT) by embedding the origin measures via a Monge displacement with respect to reference measures. \n- LCOT outperforms classical COT in terms of computational complexity.  \n- Extensive numerical experiments comparing COT and LCOT (with different reference measures) on simulated datasets.\n- The proofs sound good to me.", "weaknesses": "- There is a backbone result in the paper which is the uniqueness of $\\alpha_{\\mu, \\nu}$ (see Remark 2.4). There is an empirical showing of this uniqueness in Figure 8, Appendix A.2. However, I am still not convinced, since in Equation (8) one can get different cutting points, and using Equation (9), this may give different $\\alpha_{\\mu, \\nu}$. Probably, the result is trivial but I think it deserves to be proved.\n- As it can be seen in Figure 4, the LCOT with non-uniform reference measure is slower than the LCOT-Uniform. Is there any constant depending on the choice of the reference measure that can be added to the complexity of LCOT?\n- The experiments are conducted on simulated data, I think the application of LCOT in real data in one of the detailed domains (see Paragraph 2 in the introduction) would add more importance to this approach. I am not aware of the existence of such benchmark data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MFwxKFdE5C", "reviewer": "Reviewer_8oTS", "summary": "This paper proposes a new computationally efficient metric in order to compare circular probability measures by extending the Linear Optimal Transport framework to the circle. The authors leverage a closed-form for the Monge map between the uniform distribution and another arbitrary probablity measure to provide a closed-form for the Linear Circular Optimal Transport metric with reference the uniform measure. Then, they study theoretically the metric and apply it to different experiments with a comparison with the Circular Optimal Transport distance.", "questions": "In my opinion, the paper would really benefit from an experiment on real data. For now, the experiments are informatives, but do not make me specially see in which scenario I would benefit to apply the linear framework. Thus, finding an application where the computations of multiple pairwise OT distances on the circles is required, seems to be very important in my opinion.\n\nSome references seems to be missing. Notably, in [1, 2], derivations of the Monge map on the circle where made.\n\n[1] Beraha, Mario, and Matteo Pegoraro. \"Wasserstein Principal Component Analysis for Circular Measures.\" arXiv preprint arXiv:2304.02402 (2023).\n\n[2] Quellmalz, Michael, Robert Beinert, and Gabriele Steidl. \"Sliced optimal transport on the sphere.\" arXiv preprint arXiv:2304.09092 (2023).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, the paper is nicely written and very clear. It proposes a new metric and show its benefit compared to the previous Circular Optimal Transport distances.\n\n- Very well written and clear\n- New efficient metric on the circle with a theoretical analysis\n- Experiments which show the behavior of LCOT in comparison with COT: runtimes, comparison of the distances through a MDS and barycenter computation which cannot be directly done with COT.", "weaknesses": "- The paper is pretty incremental as it feels like a specification of the Linear OT framework in the particular case of the circle, which relies heavily on previous works such as [1, 2] for the Linear OT framework and [3] for the closed-form on the circle.\n- The experiments are only on toy data.\n\n[1] Sarrazin, Clément, and Bernhard Schmitzer. \"Linearized optimal transport on manifolds.\" arXiv preprint arXiv:2303.13901 (2023).\n\n[2] Wang, Wei, Dejan Slepčev, Saurav Basu, John A. Ozolek, and Gustavo K. Rohde. \"A linear optimal transportation framework for quantifying and visualizing variations in sets of images.\" International journal of computer vision 101 (2013): 254-269.\n\n[3] Bonet, Clément, and Paul Berg, and Nicolas Courty, and François Septier, and Lucas Drumetz, and Minh-Tan Pham. \"Spherical Sliced-Wasserstein\". International Conference on Learning Representations (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)