Partial Wasserstein Adversarial Network for Non-rigid Point Set Registration
Authors: Ziming Wang
Nan Xue
Ling Lei
Gui-Song Xia
Venue: ICLR 2022 Poster (2022)
Keywords: partial Wasserstein discrepancy
partial distribution matching
point set registration

Abstract: Given two point sets, the problem of registration is to recover a transformation that matches one set to the other. This task is challenging due to the presence of large number of outliers, the unknown non-rigid deformations and the large sizes of point sets. To obtain strong robustness against outliers, we formulate the registration problem as a partial distribution matching (PDM) problem, where the goal is to partially match the distributions represented by point sets in a metric space. To handle large point sets, we propose a scalable PDM algorithm by utilizing the efficient partial Wasserstein-1 (PW) discrepancy. Specifically, we derive the Kantorovich-Rubinstein duality for the PW discrepancy, and show its gradient can be explicitly computed. Based on these results, we propose a partial Wasserstein adversarial network (PWAN),  which is able to approximate the PW discrepancy by a neural network, and minimize it by gradient descent. In addition,
it also incorporates an efficient coherence regularizer for non-rigid transformations to avoid unrealistic deformations. We evaluate PWAN on practical point set registration tasks, and show that the proposed PWAN is robust, scalable and performs more favorably than the state-of-the-art methods.


Published as a conference paper at ICLR 2022
PARTIAL WASSERSTEIN ADVERSARIAL NETWORK FOR NON-RIGID POINT SET REGISTRATION
Zi-Ming Wang, Nan Xue, Ling Lei, Gui-Song Xia*
CAPTAIN
Wuhan University
ABSTRACT
Given two point sets, the problem registration is to recover a transformation that matches one set to the other. This task is challenging due to the presence large number of outliers, the unknown non-rigid deformations and the large sizes of point sets. To obtain strong robustness against outliers, formulate the registration problem as a partial distribution matching (PDM) problem, where the goal is to partially match the distributions represented by point sets in metric space. To handle large point sets, we propose scalable PDM algorithm by utilizing the efficient partial Wasserstein-1 (PW) discrepancy. Specifically, we derive the Kantorovich-Rubinster its gradient can be explicitly computed. Based on these results, we propose a partial Wasserstein adversarial network (PWAN), which is able to approximate the PW discrepancy by a neural network, and minimize by gradient descent. In addition, it also incorporates an efficient coherence regularizer for non-rigid transformations to avoid unrealistic deformations. We evaluate PWAN on practical point set registration tasks, and show that the proposed PWAN is robust, scalable and performs more favorably than the state-of-the-a methods.
duality for the PW discrepancy, and show
INTRODUCTION
Point set registration is fundamental task in many computer vision applications, such as object tracking (Gao Tedrake, 2018), shape retrieval (Berger al., 2017) and contour matching (Avots et al., 2019). As illustrated in Fig. 1, given two point sets representing two partially overlapped shapes, ie., a reference set and source set, the goal of this task to recover an appropriate transformation that matches the source set to the reference one. It is challenging due to the following factors: I) The point sets may contain a fraction of outliers which do not have valid correspondences in the other point set, such the noise points and the points in the non-overlapped region of the shapes. 2) The number points consisted in the point sets may be huge. 3) The deformation of point sets is generally unknown and can be non-rigid.
(a) Input sets
(b) Result DM
(c) Result
(d) Ground truth
Figure 1: An example of non-rigid point set registration using the distribution matching (DM) formulation (Hirose, 2021a) and the proposed partial distribution matching (PDM) formulation.
The registration problem is generally solved in the distribution matching (DM) framework, where the point sets are regarded as probability distributions, and are aligned by minimizing discrepancy between them. To reduce the influence of outliers, practical registration methods utilize the robust
"Corresponding authors

---

Published as a conference paper at ICLR 2022
back propagution
To
concstamation
mass/deetance dlvesboid
Transformatio
vansformed disvrbbtioon
PWv-loss
Reffrrncoo diserbuliona
Potential Network
back propagution
(a) The pipeline of the proposed PWAN
PWAN
(b) The convergence of the (potential, registration)
Figure 2: An overview of PWAN. The transformation To and the network f are trained adversarially.
discrepancies, such as Kullback-Leibler divergence (Myronenko & Song, 2010; Hirose, 2021a) and L2 distance (Jian & Vemuri, 2011). Thus they are able greedily align the largest possible fraction of points while being tolerant of small number of outliers. However, for point sets that are dominated by outliers, the greedy behaviors of these methods easily bias toward outliers, and lead degraded registration results. An example is shown in Fig. 1(b).
To obtain stronger robustness against outliers, we propose to formulate the registration problem in novel partial distribution matching (PDM) framework, where we only seek to partially match the distributions. Comparing to the DM based methods, the PDM formulation more robust against outliers. For example, in Fig. (cc), the PDM formulation find more natural solution where only fraction of points are well matched.
However, existing solutions for PDM problems generally require to compute the correspondence between distributions (Chizat et al., 2018; 8; Chapel et al., 2020), thus they are intractable for registration problems which involve large scale distributions. To handle this issue, propose efficient solver for large scale PDM problem. Our method utilizes the partial Wasserstein-1 (PW) discrepancy (Figalli, 2010), which can be efficiently optimized without computing the correspondence. Specifically, derive the Kantorovich- -ubiinsehbnn (KR) duality (Villani, 2003) for the PW discrepancy, and show that its gradient can be explicitly computed via its potential. Based on these results, we propose partial Wasserstein adversarial network (PWAN), which approximates the potential by neural network, and the unknown transformation can trained in an adversarial way with the network. We also incorporate a coherence regularizer for the non-rigid transformation to enforce its smoothness. We note that PWAN generalizes the popular Wasserstein generative adversarial net (WGAN) (Arjovsky et al., 2017) to the PDM problem. An illustration of the proposed PWAN is presented in Fig. 2.
The contribution of this work is summarized as follows.
Theoretically, we derive the KR duality for the partial mass PW discrepancy, present its differentia- bility property, and show its gradient be efficiently computed. We further provide qualitative description the KR potentials. More details can be find in Appx. A.3.
Based the KR formulation of mass-type (partial mass) PW discrepancy and the closely related distance-type PW discrepancy, we propose a scalable method, called PWAN, for large scale PDM problem. The well-known WGAN is special case of our method in the DM setting.
We apply PWAN to point set registration task, where point sets are regarded as discrete distributions. We experimentally show that PWAN exhibits stronger robustness against outliers than the existing methods, and can register point sets accurately even when they are dominated by outliers, such as when they contain a large fraction of noise points, when they only partially overlapped.
2 RELATED WORK
There is large body of literatures point set registration problem (Besl & McKay, 1992; Zhang, 1994; Chui & Rangarajan, 2000; Myronenko & Song, 2010; Maiseli et al., 2017; Vongkulbhisal et al., 2018 8:; Hirose, 2021a) a). The existing methods can be roughly categorized into classes, iee, the
2

---

Published as a conference paper at ICLR 2022
correspondence-base methods and the probabilistic methods. This section only discusses the latter class which is the most related to our method. More discussions can be found in Appx. F.1.
The probabilistic methods solve the registration problem a DM problem. Specifically, most of these methods smooth the point sets as Gaussian mixture models (GMMs), and then align the distributions via minimizing the robust discrepancies between them. Coherent point drift (CPD) (Myronenko & Song, 2010) and its variants (Hirose, 2021a) are well-known methods is this class, which minimize Kulbback-Leibler (KL) divergence between the distributions. Other robust discrepancies, including Le distance (Ma et al., 2013; Jian & Vemuri, 201 1), kernel density estimator (Tsin & Kanade, 2004) and scaled Geman Geman-MeClure McClure estimator (Zhou et al., 2016) have also been studied.
The proposed PWAN is related to the existing probabilistic methods because it also regards point sets as distributions. However, it has two major differences from them. First, PWAN directly processes the point sets un-normalized discrete distributions instead of smoothing them to GMMs, thus it is more concise and natural. Second, PWAN solves PDM problem instead of the DM problem, as only requires to match a fraction of distributions, thus it is more robust outliers.
Some recent works have been devoted to the PDM problem using the Wasserstein-type discrepancy. Bonneel & Coeurjolly (2019) proposed fast algorithm based on the sliced Wasserstein metric for special PDM problem, where a small distribution is fully matched to the large one. Various entropy regularized partial unbalanced discrepancies (Chizat et al., 2018; Séjourné et al., 2019; Chapel et al., 2020) have been utilized for the PDM problem. However, they are generally not scalable to large distributions they require compute the correspondence between distributions, or rely on the mini-batch sampling techniques (Fatras et al., 2021). Thus they are not suitable for the registration problem considered in this paper. The distance-type PW discrepancy used in our paper has been utilized for imaging problem (Lellmann et al., 2014: Schmitzer & Wirth, 2019), but these methods do not directly apply to distributions continuous space. More discussions of the related computational approaches of Wasserstein type discrepancies can be found in Appx. B.
3 PRELIMINARIES ON PARTIAL WASSERSTEIN- DISCREPANCIES
This section introduces the major tools used in this work, i.e., two types of PW discrepancies between measures: the partial-mase Wasserstein- discrepancy (Figalli, 2010; Caffarelli & McCann, 2010) and the nounded-distanee Wasserstein-11 discrepancy (Lellmann et al., 2014; Bogachev, 2007). For simplicity, we call them the mass-type and the distance-rype PW discrepancy respectively.
Given two discrete distributions a En.xx azd2, and Σnjer byōy, a compact metric space Ω C R", where is the Dirac function, and a = [a,]%_ E R2, and = [b,]%=1 E IR are the associated mass vectors, the mass-type PW discrepancy (Figalli, 2010) Larm is defined as optimal transport problem which seeks the minimal cost of transporting at least m (m I min(]aa]h, [(bl)) unit mass from a to 3 where the cost of the transportation equals the distance. Formally, LM, is defined as
min xel'm (a.
Σ Ti.j ((.,1))). i.j
where d is the metric defined in Q, π E RR is the transport plan, ,i, encodes the amount of mass transported from x; to Vj. The feasible set I', (a, (3) is given by I'm mm, B) { a, 1''1, < b, 1 2 m).
R x1, <
The other PW discrepancy used in this work is the distance-type PW discrepancy (Lellmann et al., 2014) LDD, which is Lagrangian of L... with the mass constraint softened:
(D,
min TETa(o,8)
Σ Tis (d(x,, Uz) h), 8.3
Note that LD, bounds the maximal transport distance by h.
In the special complete transport problem where all mass is transported, i.e., when ||a/]] ||6| I1- m = |||]| for LM.m. or h 2 diam(()) for LD both C,.. and LD.s become equivalent to the well-known W distance W1 (also known the earth move distance), which, according
3

---

Published as a conference paper at ICLR 2022
the Sattoroviic-Rubinsttrr duality (Kantorovich, 2006), can be equivalently expressed as
(), sup
Σ a BEE
Σ bes(ss)
fELip(
where Lip(S2) represents the Lipschitz-1 function defined on Q. We called equation (3) the KR form of Wi, and f the potential. Equation (3) exploit WGAN (Arjovsky et al., 2017) to efficiently compute W1, where f is approximated by neural network. More detailed preliminaries can be found in Appx. A.
4 THE PROPOSED APPROACH
In this section, we present the details of the proposed PWAN. We first formulate the registration problem Sec. 1. Then we present an efficient method to solve the problem in Sec. 4.2 and 4.3. We finally summarize algorithm in Sec. 4.4.
4.1 PROBLEM FORMULATION
Let Y = -1 S Ω and X {z; - Ω be the source and reference point sets, where ? R a closed bounding box of the points. The corresponding reference and source distributions are Σy,er byōy, respectively, where a,, bj R are the mass assigned to
Σx,ex Ex agdu, and each point and fixed to be 1 in this work. Let To + S2 denote a differential transformation parametrized by and Sg = Ev,er by (v,) denote the transformed B. Our goal is to align 39 to
by solving
min C(a, Ba) + C(To).
(4)
where discrepancy Lar, (1) or LD (2), which measures the dissimilarity between Bo and a, and C is the coherence energy that enforces the spatial smoothness of To.
4.2 REGISTRATION WITH THE PW DISCREPANCIES
In practical registration problems, 3p and may contain large number of outliers non-overlapping points that should not be matched to the other set. Therefore, in order to avoid biased results, is important for a registration method to allow the matching of only fraction of points.
The use La. and LD., in problem (4) naturally leads to desirable partial matchings. To see this, express them in their respective primal forms, and formulate problem (4)
Σ TT. d( Tu())) C(T)) + const,
(5)
where const a constant not relevant to and E Raxr represents the correspondence ma- trix given by the solution of the primal form of LM, (a,, (8) (I) (a, BB) (2). A toy example of the correspondence π is shown in Fig. 3. As can be seen, π only establishes the cor- respondence between a fraction of points that are close to the other set within the mass threshold v or the distance threshold h, while omitting all other points. Therefore, minimizing (5) is simply to align these corresponding point pairs subjecting to the coherent constraint C. In other words, LM.m and LD provide two ways to control the ratio of matching based on mass or distance criteria.
dlstumoe 0.9
maN
mass
6
(a) L
(b) LD,0.9
Figure 3: The computed correspondence ı be- tween a (blue) and Bp (red).
Note that according to the Lagrange duality, for each (a,, Bo, m), there exists a h², such that the solu- tion и of LD, (a. .88) recovers to that of Lm (a,, 3g). However, the minimization of LM (a, 38) in problem (5) is generally not equivalent to that of LD (a, (8) with any fixed h, because the corresponding h* depends on Sg which varies during the optimization process.
4

---

Published as a conference paper at ICLR 2022
Although formulation (5) can indeed handle the partial alignment problem, it is computationally intractable for large scale point sets, because requires to solve for a matrix и of shape X r in linear programing in each iteration. Therefore, natural question is whether it is possible to avoid the computation of æ by exploiting the KR duality of M. and LD and re-formulate them a similar way as Wi (3).
The answer is affirmative for both L and LD As for LD its KR form is already known in Bogachev (2007); Lellmann et al. (2014); Schmitzer & Wirth (2019), and we further show that it is valid to compute its gradient under a mild assumption.
Theorem 1. LD, (3 can be equivalently expressed as
Ca, 8) sup
Σ axf(r))) E hmg. felip(()) -AS$S0 xEE
(6)
D₁EY
The optimizer of problem (6) exists. Let f denote an optimizer of problem (6). When To is Lipschitz w.r.. 0, LD.((o, Ba) is continuous w.r.l. 0, and is differentiable almost everywhere. Furthermore, we have
VoLD.Mla = - b.Vof(To().).
BREY
As for L.. we derive its KR form based on that of L. and show that its gradient can also be computed under a mild assumption.
Theorem 2. LMs m (a, (3 can be equivalently expressed as
(a,
sup MEL, -h$$50
Σ (a.s(z;)) Σ byf(us) + h(m - mp)-
(8)
#1EX
B₁EY
The optimizer of problem (8) exists. Let (f, denote optimizer of problem (8). When Te
Lipschitz w.r.t. 0, 2a, 3o) is continuous w.r.t. 0, and is differentiable almost everywhere.
Furthermore, we have
VoLsm Bo)
Σ (Voo)T)) WEY
The proofs of both theorems can be found Appx. D.3.
With the aid of Theorem and 2, we can optimize LD., and LM.. efficiently. Specifically, we represent the potentials of CD,, and CM.m using neural networks fw. satisfying -h S fweh S where h E IR.. To compute Lm.m (oo, Bo), we update (w. h) to maximize
Lo
Σ Eaffns
Σ
byff.n h(m m2) -GP(fu.N) (10)
x:EX
BEEY
and to compute La, Bo). we update {w} to maximize
LossD,
Σ X
anfum
Σ b GP((w.t))
(1I)
ByEY
where GP(f) = R max 2017), and K is the strength of the penalty. Then, with the trained network fw.s, the gradients VoLs, (a, 38) and VoLD, (a,, 3o) can be computed via back-propagane their respectively losses to 8, thus 0 can be updated via gradient descent.
(+)))) is the gradient penalty (Gulrajani et al.,
To show our neural approximations of the PW discrepancies are sufficiently precise, we present a simple example numerically comparing the primal and KR form in Tab. 2 and Fig. 9 in the appendix.
4.3 OPTIMIZE THE COHERENCE ENERGY
This section discusses the optimization of the coherence energy, which ensures that the whole 3a remains spatially smooth in the matching process. First of all, we define the non-rigid transformation To parametrized by 0 = (A, V) as
To( yj A + Vy2
(12)
5

---

Published as a conference paper at ICLR 2022
where yj E RIx3 x3 represents the coordinate of point V, E EY, A R3x3 is the linear transformation matrix, / E R1x3 is the translation vector, V E [R"x3 is the offset vector of all points in Y, and Vj represents the j-th row of V. Despite its simplicity, To includes several useful transformations as its special case. For example, when V = 0 and A E SO(3), Te becomes the rigid transformation. and when = and 0, Ta becomes the "drift" transformation in Myronenko & Song (2010). Note that To is Lipschitz w.r.t 9 (Proposition 7 in the appendix), thus it satisfies the requirement of Theorem and 2, i.e., is valid to be used in our registration method.
Now define the coherence energy similar to Myronenko & Song (2010), Le., enforce that V varies smoothly in space. Formally, let G E R=*" be a kernel matrix, egg,, the Gaussian kernel Gp(i,) e- /p, and a be positive number. The coherence energy is defined as
C(T)) X XTr((V G,)
(13)
where E R+ is the strength of constraint, I is the identity matrix, and Tr(.) is the trace of matrix. Since the matrix inversion (oI + Gp) approximate it via the Nyström method (Williams & Seeger, 2000), and obtain the gradient
1 is computationally intractable for large scale point sets, we
@C(Te) av
(2 -o - t "2"""""'Q""""
(14)
where Q RR Rexk a diagonal matrix, and < r. Note the computational cost of (14) is only O(r) if we regard constant. The detailed derivation is presented in Appx. F.3.
4.4 THE ALGORITHM AND ANALYSIS
With the methods detailed in Sec. 4.2 and Sec. 4.3, we can finally solve problem (4) efficiently. Formally, formulate problem (4) as the following mini-max problem
min max Loss(a, B0; wi) C(Ta),
(15)
where Loss = M.. (10) and w {w, h). or Loss = LossD, (11) and {w], and we solve it by alternatively updating fw,h and Te-
An illustration of our method is shown in Fig. 2. The detailed algorithm is presented in Alg. For clearness, we refer to PWAN based on LMM. and LD mass-type PWAN (m-PWAN) or distance-type PWAN (d-PWAN) respectively.
Algorithm 1 PWAN for point set registration
Input: reference set source set Y. transform Te, potential network fw,h, network update fre- quency u, training type ("mass" or "distance"), mass threshold m, distance threshold h. training step T, coherence parameters (X, P.P)), o)) Nyström parameter k.
Output: the learned 0.
if training type "mass" then
w + -w, h); m + Tı; else if training type "distance" then
L M. defined in (10)
w +- (w); h +- h; L + Loss defined in (11)
end
for t 1, . do
Obtain the transformed distribution Bg.
for - 1, 1..... do
Compute /L/ /w by pack-propggating L through W.
Update w by ascending the gradient OL/Ow.
Potential learning
end for
Compute aC 00 using (A, p. o, k) according to (14). Compute 0L/00 by back-propagating L through 8.
Update by descending the gradient Ö(T. + C)/a0.
D Registration
end for
To provide an intuitive explanation why solving problem (15) can lead to partial alignment, we first visualize the learned potential toy example in Fig. As be seen, the potential of PWAN

---

Published as a conference paper at ICLR 2022
attains the upper or lower bound (0 -h) in regions, thus the gradient within these regions is strictly 0, i.e., the potential is strictly "flat" these regions. This observation formally stated and proved in Proposition 11 and 12 in the appendix.
Due to the existence of flat regions, PWAN can automatically discard fraction of points during the registration process. Specif- ically, if we omit the coherent energy. in each iteration Alg. 1, PWAN moves Bg along the gradient of potential. Therefore, PWAN only moves the fraction of points with non-zero gradi- ent, while leaving the points with zero gradients (in flat regions) fixed. For the case in Fig. 4, only the lefimost 3 points in Se will be moved leftward in current iteration, while others will stay fixed. In other words, PWAN seeks to match a fraction of points instead of the whole point sets.
Potential
Flat region
Flat region
Figure 4: The learned potential on toy 1-dimensional point sets.
More discussions can be found in Appx. F.4.
5 EXPERIMENTS AND ANALYSIS
In this section, we experimentally evaluate the proposed PWAN on point set registration tasks. After describing the experiment settings in Sec. 5.1, first present toy example to highlight the robustness of the PW discrepancies in Sec. 5.2. Then we compare PWAN against the state-of-the-a methods Sec. 5.3, and discuss its scalability in Sec. 5.4. We finally evaluate PWAN on two real datasets in Sec. 5.5. More experimental results are given in Appx. F.
5.1 EXPERIMENT SETTINGS
As shown in Fig. 5, we three synthesized datasets in our experiments: bunny, armadillo and monkey. The bunny and armadillo datasets are from the Stanford Repository (Standford), and the monkey dataset from the internet. The number of points in these shape are 8, 171, 106, 289 and 7, 958 respectively. Following Hi- rose (2021b), we artificially deform these sets, and we evaluate the registration results via the mean square error (MSE).
Figure The synthesized datasets used in our experiments. The source point sets (blue) are syn- thesized by bending the reference point sets (red) in non-linear manner.
We use a 5-layer point-wise multi-layer perception as our network (Fig. 10 in the appendix), and the parameters used in the experiments are given in Appx. F.5.
5.2 COMPARISON SEVERAL DISCREPANCIES
To provide an intuition of our PDM formulation for registration, we compare the PW discrepancy with two representative robust discrepancies used in DM based registration methods, i.e., KL diver- gence (Hirose, 2021a) and L2 distance (Jian & Vemuri, 201 1), on a toy 1-dimensional example. For now, we do not consider the coherence energy.
We construct the toy point sets X and Y shown in Fig. 6(a), where we first sample equi-spaced data points in interval [0, 3). then we define Y by translating the data points by distance I, and define X by adding outliers record four discrepancies: KL, L2, LM,10 and LD.2 between X and Y as a function of t, and present the results from Fig. 6(b) to Fig. 6(c).
narrow interval [7.8, 8.2] to the data points. For N = (1, 10, 10 }. we
As can be seen, there exist two alignment modes in this experiment, i.e., = 0 and t 6.5, which respectively correspond to the correct aligmment and the degraded alignment where Y is matched to outliers. When the number of outliers is small, e.g., N 1, all discrepancies admit deep local minimum t = 0. However, as for KL and L2 divergence, the local minimum t gradually vanishes and they gradually bias toward 6.5 as N increases. In contrast, LMM10 and L.D.2 2 do not suffer
7

---

Published as a conference paper at ICLR 2022
from this issue, i.e., the local minimum t 0 remains deep regardless of the value of N, and the local minimum = 6.5 is always shallower than the local minimum t 0.
The results show key advantage of PDM against DM for registration: When the number of remote outliers is large, the DM formulations (KL and L2) always tend to converge to the biased result, while the correct alignment of PDM formulation is not influenced by the remote outliers, and it is less likely to converge to the biased result.
outleers
v:
X:
(a) Experiment setting of the toy example.
W
Discrepancy
0.8
D.s
Discrepancy
0.8
Discrepancy
0.8
Discrepancy
0.8
0.4
0.4
0.4
0.0
0.0
0.0
0.0
6.5
6.5
6.5
6.5
(b) L2
(c) KL
(d) LM,10
(c)
Lp.2
Figure 6: Comparison of different discrepancies on toy point set.
5.3
EVALUATION OF THE REGISTRATION ACCURACY
We compare the performance of PWAN with four state-of-the-art methods: CPD (Myronenko Song, 2010), GMM-REG (Jian & Vemuri, 201 I), BCPD (Hirose, 2021a) and TPS-RPM (Chui & Rangarajan, 2000). We evaluate them on the following two artificial datasets.
Point sets with extra noise points. We first sample N 500 random points from each of the original and the deformed sets as the source and reference sets respectively. Then we add extra uniformly distributed noise points to the reference set, and we normalize both sets to mean 0 and variance 1. We vary the number of outliers from 100 to 600 at an interval of 100, Le.. the outlicr/non-oute outlier ratio varies from 0.2 to 1.2 at interval of 0.2.
Partially overlapped point sets. We first sample N 1000 random points from each of the original and the deformed sets the source and reference sets respectively. Then for each with a random plane, and we retain the points in one side of the plane and discard all points in the other side. We vary the retain ratio s from 0.7 1.0 an interval of 0.05 for both the source and the reference sets, thus the minimal ratios of overlapping area are (2s 1)/8 -0.57, 0.67, 0.75, 0.82, 0.89, 0.94 and accordingly, and the minimal corresponding mass is m (2s 1) 1000.
intersect it
We evaluate m-PWAN with m 500 (cquivalently d-PWAN with h = + in the first experiment, while we evaluate P--W with m z and d-PWAN with h 0.05 in the second experiment. We run all methods 100 times and report median and standard deviation of MSE in Fig. 7.
Fig. 7(a) presents the results of the first experiment. The median registration error of PWAN is generally comparable with PPS-RPM. and is much lower than the other methods. In addition, the standard deviations of the results of PWAN are much lower than that of TPS-RPM. This suggests that PWAN are more robust against outliers than baseline methods. Fig. 7(b) presents the results of the second experiment. Two types of PWANs perform comparably, and they outperform the baseline methods by large margin in terms of both median and standard deviations when the overlap ratio is low, while perform comparably with them when the data is fully overlapped. This result suggests the proposed PWAN can effectively register the partially overlapped sets.
5.4 EVALUATION OF THE EFFICIENCY
To evaluate the efficiency of PWAN, we first need to investigate the influence of its parameters. In particular, the most important parameter that affects the efficiency is the network update frequency u, which controls the tradeoff between the efficiency and effectiveness. Specifically, larger u leads to more accurate estimation of the potential and the gradient, while smaller u allows for faster estimations. We quantify the influence of using the bunny dataset and report the results in the left
8

---

Published as a conference paper at ICLR 2022
0.20
BCPD
0.20
BCPD
grannng CPO
0.15
CPD
0.15
grynregg
CPD
MSE
0.10
PMIAN
NSE
0.10
PAYAN
TPS-RP
MSE
0.10
PHIAN
0.05
0.05
0.05
0.00
0.00
-0.05
-0.05
0.05
0.10
0.2
0.4
0.6
0.8
1.0
1,2
-0.10
0.2
0.4
0.6
0.6
1.0
1.2
0.10
0.2
0.4
0.6
0.8
1.0
1.2
Outlier/Non-outier rabio
OutlierNNon-oulier ratio
Out Outier/Non-outtier ratio
(a) Evaluation robustness against noise points.
0.4
0.4
BEPD
BCPO
SCFO
CPO
CPO
CID
0.2
I-PAAN
6-PWAN
MSE
0.2
maNGAN
d-PWAN
MSE
0.2
miNsoNi
GPVANN
0.1
0.1
0.0
-0.1
1.0
0.9
0.8
0.7
0.6
-0.1
1.0
0.9
0.8
0.7
0.6
-0.1
1.0
0.9
0.8
0.7
0.6
Overlapping region ratio
Overlapping region ratio
Overlapping region ratio
(b) Evaluation of robustness against partial overlapping.
Figure 7: Registration accuracy of the bunny (left), monkey (middle) and armadillo (right) datasets. The error bars represent the medians and standard deviations of MSE.
panel of Fig. 8. As can seen, both MSE and the variance of MSE decrease as u increases, while the computation time increases proportionally with This result suggests that more accurate and stable results can be achieved the expense higher computational cost, i.e, larger u.
We benchmark the computation time of dif- ferent methods on a computer with two Nvidia GTX TITAN GPUs and an Intel i7 CPU. We fix u = 20 for PWAN. We sam- ple points from the bunny shape, where varies from 10 to x 10 PWAN the GPU while the other methods are run on the CPU. We also implement a multi-GPU version PWAN where the po- tential network is updated in parallel. We run each method 10 times and report the mean of the computation time in the right panel of Fig. As can be seen, BCPD is the fastest method when is small, and PWAN is comparable with BCPD when & near 10 In addition, 2-GPU version PWAN faster than the single GPU version, and it is faster than BCPD when q is larger than 5 x 10
2.5
350
10r
2.0
300
107
1.5
250
(8)
300
1.0
CRO
3.5
TPS-RPM
0.0
10
15
20
25
100
10a
10a
10"
10a
10
Network update trequency
Number of points
Figure 8: Scalability of our method.
5.5 EVALUATION ON REAL DATA
To demonstrate the capability of PWAN on handling point sets with non-artificial deformations, we evaluate it human face dataset (Zhang al., 2008) and 3D human dataset (DataSet). The details of this experiment are presented in Appx. F.9 and Appx. F.10.
CONCLUSION
In this paper, we formulate the point set registration task as a PDM problem, where point sets are regarded as discrete distributions and are only required be partially matched. In order to solve the PDM problem efficiently, we derived the KR form and the gradient for the PW discrepancy. Based on the theory, we proposed the PWAN method for PDM problem, and applied it to practical point sets registration task. We experimentally show that PWAN effectively handle the point sets dominated by outliers, including those containing large fraction of noise or being partially overlapped.
There are several issues need further study. First, the computation time of PWAN is still relatively high. A possible approach to accelerate PWAN to incorporate a forward generator network as in Sarode al. (2019) or to the discriminative training as in Vongkulbhisal al. (2018). Second, is interesting to explore PWAN other PDM problems, such as domain adaption (Hu et al., 2020), pose estimation (Kuhnke & Ostermann, 2019) and multi-label learning (Yan & Guo, 2019).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation China under Grant 61922065, Grant 62101390 390, Grant 41820104006, the Fundamental Research Funds for the Central Universities under Grant 2042021kf0033 and the National Post-Doctoral Program for Innovative Talents under Grant BX20200248.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan, arXiv: Machine Leurning, 2017.
Egils Avots, Meysam Madadi, Sergio Escalera, Jordi Gonzalez, Xavier Baro, Paul Pällin, and Gholamreza Anbarjafari. From 2d 3d geodesic-based garment matching. Multimedia Tools and 2019.
Applications,
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Itera- tive bregman projections for regularized transportation problems. SIAM Journal on Scientific 2015.
Computing, 37(2):A1111-A)
Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Gaël Guennebaud, Joshua A. Levine, Andrei Sharf, and Claudio T. Silva. A survey of surface reconstruction from point clouds. Computer Graphics Forum, (6(1):301-329) 2017.
P.J. Besl and H.D. McKay. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239-256 1992.
Vladimir Bogachev. Measure theory, volume 1. Springer Science & Business Media, 2007.
Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions on Graphics, 38(4):89, 2019.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1)222-45, 2015.
Luis A. Caffarelli and Robert J. McCann. Free boundaries in optimal transport and monge-amper ampere obstacle problems. Annals of Mathematics, 171(2):673-730 2010.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applications on positive-unllbeled learning. Advances in Neural Information Processing Systems, 33:2903-2911 2020.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavies Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-2600 2018.
Haili Chui and A. Rangarajan. A algorithm for non-rigid point matching. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. NR.0R066)2), volume 2, pp. 2044-2051, 2000.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pp. 2292-2300, 2013,
DataSet. Matching humans with different connectivity. URL htLptt////poffsscceeeee univr. htt//marinn sh shrec1 9/.
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced wasserstein distance. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3483-3491, 2018
Kilian Fatras, Younes Zine, Rémi Flamary, Rémi Gribonval, and Nicolas Courty. Learning with minibatch wasserstein: asymptotic and gradient properties. In AISTATS 2020-23rs 23nd International Conference Artificial Intelligence and Statistics, volume 108, pp. 1-20, 2020.
10

---

Published as a conference paper at ICLR 2022
Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch optimal transport; applications to domain adaptation. In International Conference on Machine Learning. pp. 3186-3197. PMLR, 2021.
Alessio Figalli. The optimal partial transport problem. Archive for Rational Mechanics and Analysis, 195(2):533-56, 2010.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia 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 Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-2 2021. URL http:////// / fmmlr.r..... rr org/ httppppppr/////// 20- 451 html.
Wei Gao and Russ Tedrake. Surfelwarp: Efficient volummetii single view dynamic reconstruction. In Robotics: Science and Systems XIV, volume 14, 2018.
Song Ge, Guoliang Fan, and Meng Ding. Non-rigid point set registration with global-local topology preservation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 245 251, 2014.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn di- vergences. In International Conference on Artificial Intelligence and Statistics, pp. 1608-1617.
PMLR, 2018.
Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1574-1583, PMLR, 2019.
Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye. A review on generative adversarial networks: Algorithms,, theory, and applications. CoRR, abs/2001.06937, 2020. URL
https://arxins http::///wwww.oo./..ooooooo aabs/////////////////////////a// 2001 06337.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. In NIPS'17 Proceedings of the 31st International Conference Neural Information Processing Systems, volume 30, pp. 5769-5779, 2017.
Eric Heitz, Kenneth Vanhoey, Thomas Chambon, and Laurent Belcour. A sliced wasserstein loss for neural texture synthesis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9412-9420, 9420, June 2021.
Osamu Hirose. A bayesian formulation of coherent point drift. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(7):2269- 22282 2021a.
Osamu Hirose. Acceleration of non-rigid point set registration with downsampling and gaussian process regression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(8): 2858-2865, 2021b.
Jian Hu, Hongya Tuo, Chao Wang, Lingfeng Qiao, Haowen Zhong, Junchi Yan, Zhongliang Jing. and Hemry Leung. Discriminative partial domain adversarial network. In European Conference on Computer Vision, pp. 632-648, 2020.
Bing Jian and B C Vemuri. Robust point set registration using gaussian mixture models. IEEE Transactions Puttern Analysis and Machine Intelligence, 3338):6633-1645, 2011.
L. V. Kantorovich. On the translocation of masses. Journal of Mathematical Sciences, 133(4): 1381-1382, 2006.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 191. 2014.
Soheil Kolouri, Yang Zou, and Gustavo K Rohde. Sliced wasserstein kernels for probability distribu- tions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
5258-5267, 2016.
11

---

Published as a conference paper at ICLR 2022
Felix Kuhnke and Joemn Ostermann. Deep head pose estimation using synthetic images and par- tial adversarial domain adaption for continuous label spaces. In 2019 IEEE/CVF International Conference Computer Vision (ICCV), pp. 10164-10173, 2019.
Jan Lellmann, Dirk A. Lorenz, Carola-Bibiane Schönlieb, and Tuomo Valkonen. Imaging with kantorovich-rubintein discrepancy. Siam Journal on Imaging Sciences, 7(4):2833-2859, 2014.
Jiayi Ma. Ji Zhao, Jinwen Tian, Zhuowen Tu, and Alan L. Yuille. Robust estimation of nonrigid transformation for point set registration. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2147-2154, 2013.
Baraka Maiseli, Yanfeng Gu, and Huijun Gao. Recent developments and trends in point set registration methods. Journal of Visual Communication and Image Representation, 46(46):95 2017.
Paul Milgrom and Ila Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2): 583-601, 2002.
Andriy Myronenko and Xubo Song. Point registration: Coherent point drift. IEEE Transactions on Putlern Analysis and Machine Intelligence, 32(12):222--2275 2010.
Vinit Sarode, Xueqian Li, Hunter Goforth, Yasuhiro Aoki, Rangaprasad Arun Srivatsan, Simon Lucey, and Howie Choset. Pernet: Point cloud registration network using pointnet encoding, 2019.
Bernhard Schmitzer. Stabilized sparse scaling algorithms for entropy regularized transport problems.
SIAM Journal on Scientific Computing, 41143:A1443AA144 2019.
Bernhard Schmitzer and Benedikt Wirth. A framework for wasserstein-l-tyie metrics. Journal of
Convex Analysis, 26(2):353-396, 2019.
Standford. The stanford 3d scanning repository.
[Online]. Available:
http://graphics..ot http:/icsttttoooodddddd//aa///ne
Thibault Séjoumé,, Jean Feydy, François-Xavis Xavier Vialard, Alain Trouvé, and Gabriel Peyré. Sinkhorn divergences for unbalanced optimal transport. arXiv preprint A9 12958, 2019.
T. Tieleman and G. Hinton. Lecture 6.5-RmsProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Yanghai Tsin and Takeo Kanade. A correlation-baser approach robust point set registration. In European Conference on Computer Vision, pp. 558-5588885 0098-66,6000 2004.
Cédric Villani. Topics in optimal transportation. Number 58. American Mathematical Soc., 2003.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Jayakorn Vongkulbhisal, Benat Irastorza Ugalde, Fernando De la Torre, and Joao P. Costeira. In- verse composition discriminative optimization for point cloud registration. 2018 IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2993-3001, 2018.
Christopher K. L. Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems 13, volume 13, pp. 682-688, 2000.
Yan Yan and Yuhong Guo. Adversarial partial multi-label learning. arXiv preprint 17X66:190..06717. 2019.
Li Zhang, Noah Snavely, Brian Curless, and Steven M Seitz. Spacetime faces: High-resolution capture for modeling and animation. In Data-Driven 3D Facial Animation, pp. 248-276 188-276. Springer, 2008.
Zhengyou Zhang. Iterative point matching for registration of free-form curves and surfaces. Interna- tional Journal of Computer Vision, (3(2):119-152 1994.
Qian- Yi Zhou, Jaesik Park, and Vladlen Koltun. Fast global registration. European Conference on Computer Vision, pp. 766-782, 2016.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
In this appendix, we provide theoretical justifications of our algorithm and more experimental results.
We first present more general introduction of the optimal transport problem and fix the notations in Sec. A. Then we introduce existing computational approaches of optimal transport problem in Sec. B. We derive our formulation in Sec. C and the gradient in Sec. D. We further discuss the properties of our formulations in Sec. E. Finally, we present more details for the main text in Sec F.
A PRELIMINARIES
This section introduces the optimal transport (OT) problem and fix the notations for later sections.
A.1 OPTIMAL TRANSPORT
OT a classic problem dating back to Monge and Kantorovich. requires to solve the following transportation problem: let be the distribution of warchouses storing some raw materials, and / be the distribution of factories requiring these matcrials. Assuming the total mass of materials stored in the warehouse is ma, and the total mass of materials required by the factories is m,g How to transport at least m (m I min(m... m,)) mass materials from a to 3 so that the total cost is minimized?
Formally, let Ω be compact metric space and MM (S2) be the set of non-negative measures defined on Q. Define the source and target measures o, B E MM+ (22, and continuous cost function e: Ω x Ω R+ OT seeks solve the following optimization problem
/ c(x, (x. v),
L. () =
inf m (). Jan
(16)
where I'm (m, are the set of non-negative measures defined Ω x Ω satisfying
(A x Q) S a(A),
(l x A) < ((A) and ( x Q2) 2 m
for all measurable set A C Ω. For ease of notations, we abbreviate ma = al.)), mg = ((2) and m(x)= = (52 !2).
In the complete OT problem, it is generally assumed that m. = m2 = m, i.e., the source and the target distributions contain equal mass of materials, and all materials should be transported. However, the more general partial optimal transport (POT) problem (Figalli, 2010; Caffarelli & McCann, 2010) only requires m S min(ma, ma). i.e., the source and target distributions may contain different mass of materials, and only a partial of mass is required to transported.
A.2 PARTIAL WASSERSTEIN-1 DISCREPANCY
In this paper, we focus on a specific POT problem where the cost function is distance in the metric space Ω, i.e., c(z, y) d(x, y). where d is the distance function defined in Ω. In this case, we called m. the mass-type partial Wasserstein-1 (PW) discrepancy.
In the complete OT case, this type of OT problem defines the Wasserstein-1 metric, which is also known as the earth move distance (EMD) between distributions. According to the Kantorovich- Rubinstein duality (Kantorovich, 2006), the Wasserstein-1 metric can be equivalently expressed as
I I -
/ fdB.
Wi (a, 3) sup JELip(R)
(17)
Note that this formulation offers more efficient implement of Wasserstein-1 metric than the primal form (16), as it only requires to solve for a function with local constraint in 52 instead of a transport plan with global constraints in Ω Ω.
Several methods have been proposed to generalize (17) to the unbalanced OT (Chizat et al., 2018; Schmitzer, 2019), i.e., OT problems with extra regularizers. See Schmitzer & Wirth (2019) for uni- fied framework of this type of generalizations. Amongst these generalizations, KR metric (Lellmann al., 2014 4) is closely related to the POT problem (16) considered in this paper, it can be regarded
13

---

Published as a conference paper at ICLR 2022
Lagrangian of problem (16) where the mass constraint is soften. Specifically, the primal form KR metric with parameter h > 0 defined as
h S d(z, y)d y) hm((x) + + (mx mg). =ETo(a.D)
(R, 3)
inf
(18)
It is important notice that the KR metric has natural explanation that requires find optimal plan whose transport distance does not exceed h. This can be seen by re-writing problem (18) as KR, (a, B3 inf f [(d(x,)) y) h)d y) + const, and noticing that if d(r, y) > h, then the solution T² to problem (18) should satisfy x² (I, y) = 0.
Importantly. the KR metric is known to have an equivalent form (Lellmann et al., 2014; Schmitzer Wirth, 2019)
/ fda -f fd9.
KR (a, B)
sup fELip(())
(19)
ifls
which is very similar to (17). We called formulations (17) and (19) KR forms, and the solution to KR forms potentials.
A.3 THEORETICAL CONTRIBUTIONS
The main theoretical contributions of this work summarized follows.
We present the KR form of La.m in Proposition 3 in Sec. C.
We prove the differentiability of the KR form of L.. and derive its gradient in Sec. D.
We characterize of the potential of the KR form of LMM in Sec. E. The main result is Proposi- tion 11.
A.4 NOTATIONS
(2, d): metric d associated to a compact metric space Q. For example, Ω can be a closed cubic in R and d can be the Euclidean distance.
C(()): the set of continuous bounded function defined on Ω equipped with the supreme norm.
-Lip(1) C C(2):: the set of 1 1-Lipschitz function defined on Ω.
-M(X): the space of Radon measures on space X.
=/. The marginal of л on its first variable. Similarly, 22 represents the marginal of æ on its second variable.
Given function F: X
IR U +oo, the Fenchel conjugate of F is denoted as F* and is given by:
F" (x')
= sup
< I, x > -x(),, Vx" E X
(20)
=EX
where X is the dual space of X and
< > is the dual pairing.
B EXISTING COMPUTATIONAL A APPROACHES OF OT PROBLEM
The computation of OT problem is an active field in machine learning. In this section, we briefly discuss three major classes of approaches and relate our method to the existing ones.
One class of the most well-developed OT solver is based on the entropic regularizer. This class of approaches relax the primal problem by adding an entropy regularizer the transport plan, then solve the relaxed problem via the Sinkhorn algorithm (Cuturi, 2013). However, the direct application of the Sinkhorn algorithm has two drawbacks. First, the entropic bias introduced by the regularizer always leads undesired behaviors. Second, the computational cost is high for large scale problems, since the Sinkhorn algorithm iteratively updates the whole transport matrix. Some works have been devoted address these two issues. To get rid of the bias, Genevay et al. (2018; 2019) proposed the Sinkhorn divergence as an unbiased version of the entropic OT. To improve the efficiency, Schmitzer (2019) proposed some acceleration techniques such muti-scale computing, and Fatras al. (2020)
14

---

Published as a conference paper at ICLR 2022
proposed to consider the mini-batei OT problem to avoid the computation of the complete transport plan. The generalization of this type of approaches to unbalanced or partial OT problem was studied in Benamou et al. (2015); Chizat et al. (2018); Séjoumé et al. (2019); Fatras et al. (2021).
The second class of approaches solve the sliced OT problem (Bonneel et al., 2015; Kolouri et al., 2016). They avoid computing OT problems in high dimensional space by projecting the distributions onto random 1-dimensional lines, and solving a 1-dimensional OT problem each time. Due to their simplicity and efficiency, this class of approaches have been applied several fields in computer vision, such as generative modelling (Deshpande et al., 2018) and texture synthesis (Heitz et al., 2021). Recently, Bonneel & Cocurjolly (2019) proposed an algorithm for special case of partial sliced OT problem, where small distribution is completely matched to fraction of a large distribution. However, this method does not handle the general partial sliced OT problem.
Our method belongs to the third class of approaches which focus specific type of OT problem: the Wasserstein- type problem. The foundation of this type of approach is the Kantorovich- Rubinsteei duality (17), which allows to efficiently compute Wasserstein-1 I distance by learning Lipschitz function. This property was directly exploited the popular Wasserstein GAN model (Arjovsky et al., 2017). Some works (Lellmann et al., 2014; Schmitzer & Wirth, 2019) generalized this duality to the unbalanced Wasserstein-1 I type problem and applied them to imaging problems, but the exact d) has not been considered. Our method completes
partial Wasserstein-1 problem ((6) with these approaches in a sense that we solve the exact partial Wasserstein-1 problem. Besides, unlike the existing works (Lellmann et al., 2014; Schmitzer & Wirth, 2019) which only handle the distributions in discrete image space, our method handles distributions in the continuous space, thus it is more suitable for applications in machine learning such point sets registration.
C OUR FORMULATIONS
In this section, we derive the KR formulation of Lm The main result is Theorem First of all, we derive the Fenchel-Rockafellar dual of M. Proposition 1 (Dual form of L.,.). Problem (16) can be equivalently expressed as
(a, (a,8). B).
sup [ f + / gdß + mhh (f.g
L. (a,
(21)
where the feasible set R is R (1. E C()) x ((O) ff 00 g 00 c(x,8) - f(x)) - ((v) 2 Vr E Ω
In addition, the infimum in Problem (16) is attained.
Proof. We prove this proposition via Bocchhll- duality, We first define space E: C(..) x
C(Q) x R. space F: C(¹ x 12), and linear operator A: + as
A(f.g,)) h) (z, y, h) + (x) + g(y) + h;; VS.g E C(2), VIER, Va,y e Ω.
(23)
Then we introduce a convex function H: F U +00 as
0
ifuz -c
H(u)=
(24)
+00
else
and L: E + R. U +oo as
[ fda + gd3 + hm
if 0. g 2 0, h 5
L()
(25)
+0
else
We can check when f = g 1 and = -1, H is continuous at A(f, g, h). Thus by Fenchel- Rockafellar duality, have
inf H(A(f.g. h)) L(f.g.h) = sup tEM(UxA)
-H' - -L'(Am))
(26)
(
15

---

Published as a conference paper at ICLR 2022
We first compute the Fenchel dual H*(-7) and L (' in the night-hand side of (26). For arbitrary
т E MMi x Q), we have
H (-T))
(-u)dT H(w)}
sup
F
| (-u)drr) u(x, 2 -((,,)) v(r,w) EQxx)
sup WEF
sup
udvt u(z,)) - c(a,y), v(r =2x1
uEF
It is easy to that if is non-negative measure, then this supremum is cdnt otherwise it is +oo. Thus
[f (d if MM Ω)
H-
(27)
1+00
else
Similarly, have
L T)
(f..gh)),AT -II
sup (faA))E
A((fgg,)) -1/ - fda + / hmd0++mm)..
= sup (Sig.)E
{/ fd(( a) + / gil( - 9) h < 0} sup (fa.))E
If (a - 7 and (3 - THt) are non-negative measures, and T(2 x Q2) m 2 0, this supremum is 0,
otherwise is +00. Thus
10 if(a (() E (B -8-m2 - MM ( x(2 x ?) 2
L-(ATT== [+ +oo
(28)
else
In addition, the left-hand side of (26) reads
inf H(A(f, g, h)) + L(f.gh) (fa..)EE
inf (f.gi)eeR) [f sda+ / gd3 + hm f.g 2 0, h50, +())+(()) + h va,
{/ (/ / gds + hm f.g s 0, h 2 0, f(z) g(v) + + - 72
=- sup (f.g.hje
Finally, by inserting these terms into (26), we have
f [datt/ / gdd3+hm
f clz, v)d v),
sup (f f.950, f())+ (Sorr)))
inf TEM, (Qx() (a-s)) (0) x(Xx0)2m
which proves (21).
In addition,
also check right-hand side of (26) is finite, since always construct ym
ym 3, such that M4 x Ω), #1 = at1y S a, independent coupling al03] a & DTa)
22 :OO 3 < 3 and #(2 x Ω) Thus the Fenchel-Rockafelln duality suggests the infimum attained.
Then we define the following Lagrangian POT problem:
inf f c(x, (d - hm((T).
(a,
(29)
xETola,0)
16

---

Published as a conference paper at ICLR 2022
where h 0 is the Lagrange multiplier. When c(x, y) d(x, v), immediately obtain the KR form of this problem by reformulating the KR metric (18):
fda S. fdß hmg.
LD,
sup fELip(2) S -hSf50
(30)
Similar to Proposition 1, we derive the Proposition 2 (Dual form of LD,)). Problem (29) can be equivalently expressed as
dual form of LD.
/ fdx + gd3.
LD,
sup (1.))ER(N)
(31)
where the feasible set is (h) = (f.9) C(O)) S 0, s o, - f-))=))---------- f(x) ((v) 2 0, V,
(32)
In addition, the infinum in Problem (29) is attained.
Proof. This proposition can be proved in similarly to Proposition 1, so we omit the proof here. 17
Now, by comparing Proposition with Proposition 1, we can see that LD, and M. are related by
LM. sup / fda + J gdß mh (f.g.))
-uup LD + mh. AER,
(33)
Therefore, obtain the KR form of LM, by inserting (30) into (33).
Theorem 3 (KR form of L., When c(x,v) d(x, v), problem (16) can be reformulated as
/ fda / fdB + h(m ma)
LM (a, 3)
sup (ELip(9),eER -5150
(34)
5
or equivalently as
fda - / fdß - inf(f) mz).
CM (a,
sup fELAp(0).
(35)
Proof. We obtain equation (34) by inserting (30) into (33) and merging two supremums. As for equation (35), note that given a fixed f E C(S2) in problem (34), the optimal h is simply inl(f)
+oo. So we can replace by iff( in problem (34) to obtain problem (35).
For clearness, we define some functionals associated to LMSm and LD.b-
Definition (LMmm and LMM)). Define functional LMM associated problem (34)
L M.m (f,h)= = Ja fd(a - B) + h(m - mm)) h R+ f E Lip(S)) -h < f else,
(36)
-00
and functional LMm. associated to problem (35) as
(f) fdla 3) inf(ff((mmmm)))) mq) fe Lip(!)) 50
I a M.m -00
(37)
else,
Definition 2 (Ln,a)). Define functional Lp, associated to (30) as
(f) ( Ss fda -Ja fdz hmg f Lip(S). -h S5,, else
-00
17

---

Published as a conference paper at ICLR 2022
With this definition, (30) becomes
(D) = sup D, (f)
SEC(O)
Problem (34) and (35) become
(a.
sup FEC(O))AR
L (f, and (a,
sup FEC(S)
L
M, (f)
respectively.
We remark that the maximizer of a.. exists.
Proposition 3 (Existence of optimizer Schmitzer & Wirth (2019)). For a, E M+ and there exists f E C(2) such that (0, = L (f).
Finally, we summarize the formulations discussed in this section in Table 1. Note that we have two equivalent KR forms of M.... Although LMM has a simpler form without the extra variable h, contains the infimum which hard implemented in practice. Thus we mostly use MM in practical implementation.
Table I: Equivalent formulations of M. and LD
M.
CD.
inf / dx, y)) v)
inf /
Dxx
fux (x, hm(mt)
Primal 8.1. x 22) S a(A), AA,
s.t. ग (A x Q2 S (AA), VA,
T x A) < B(A), VA,
x *a A) s 3(A), VA.
(l2 x 12) N m,
sup ( fda / gd3 + mh (f.g.))
sup [ fda / gdB
nn
(f.g) Jn
Dual
s.1. (f.g. h) E (()) x C(.) R,
8.1. (f.g) E C(Ω) C((2),
7,0, 9 < 0, h 0
f < 0,
c(a.y) f(x) gvv) 2 0, Az,
c(x,y) f (z) g 2 0, Vx,y
sup fdl(a= B) hmm ma)
f.h nn
s.t. f E Lip( h 2 h 0
sup / fd(a - 3) -hm
f
KR
s.t. f E Lip(S?)
(c d)
sup
fil(a= 3) inf(f)(m m²)
- h h
|/
s.t. f E Lip(S)
f 0
D DIFFERENTIABLITTY
This section proves the diffcrentiability of both LD.b and LM.m in the KR form in Proposition 6 and Proposition 5. To this end, first need to show the potential of L.M. exists in D.1.
18

---

Published as a conference paper at ICLR 2022
D.1 EXISTENCE OF OPTIMIZERS
In this section, we prove that the maximizer of 0,,8 M, exists.
Proposition 4 (Fxistence of optimizers). For 0,, E M+) and m 0, there exists f C(22 and h E R such that L..m(a, (3) M. ( (f.h).
To prove this proposition, we need the following lemma.
Lemma (Continuity). M. is continuous C( R.
Proof. Let (n,,,n)) + (f, h)) in ((2)) R. Assume L M. (fnr hn) -00 when n is sufficiently
follows. For arbitrary 0, there exists N 0 such for arbitrary e >> 0, f -h - E, which suggests f 2 h. In addition. it is easy to see f I 0 and h 2 0. is also easy to see Lip(f) S 1 due to the closeness of Lip(S2). Thus according to the definition 36, we claim L Ad (f, > -c. Furthermore, since h fn < O, and fn - f. by dominated convergence theorem, have
large. We first check Mi (f. h)
that for N, hn + thus fn hn -h By taking - 0o,
| lim fnda = / fda,
lim 5
Snda
Jn n00
(38)
nn
-1 lim fn = 1 fdB. n-00
and lim
fnd
(39)
n 00000 52
Note we have h (m m2) + h(m - m2). We conclude the proof by combining these three terms and obtaining MMm (fn, hm) L (f h).
Proof of Proposition 4. If we can find a maximizing sequence (fn, hn) that converges to a.,9 (f,h) E C( x R, then Lemma suggests that LM.m(ax (a, = sup M, (f h)
limn-+00 L (fn. h,) LM (f. h)). which proves this proposition. Therefore, we only need to show that always possible construct such maximizing sequence.
Let (fn, hm) be maximizing sequence. We abbreviate max(fa) = maxzen(fn(a and min(f.) = min (fx()).. We first assume fr does not have any bounded subsequence, then there exists N 0, such that for all can simply collect a subsequence of fn bounded by diam(())). We can therefore construct fn = fn - (min(f, (fn) fn)) diam(s?)) and hn = hn + (min diam((1)). Note that max(fn) S diam((?) + diam((?) O, fn hn fn + hn 0, and fo Lip(O)). so Lav mm (fn, hm) - -c, and
N, min(fn) < -diam((?) (otherwise
min( (f) + di)m(())
L L Mm
(Fr, (un)
f Fnd(a- (3) hm m3)
| fnd(a- hm(m - ma) + (min(fx) - diam(9)))(m - m.) )
2 L M.m. (fn, hn), hin,
which suggests that (fn, hn) is better maximizing sequence than (fn, hn). Note fn uniformly bounded by diam({?) because 0 2 fr 2 min(f.) = di) As result, we can always assume construct hn
hn is also bounded by diam(S)). Because otherwise and it easy to show (fn, hn) is better maximizing sequence than (fn, h2). In summary, we can always find maximizing sequence (fn, h,),, such that both f. and h,, are bounded by di)m
min(fa) I diam(S!),
Finally, since f., is uniformly bounded and equicontinuous, fn converges uniformly (up to a sub- sequence) to continuous function f. In addition, hn has convergent subsequence since it is bounded. Therefore, we can always find a maximizing sequence (fn, h,) that converges to some h)) E C(Q) x IR, which finishes the proof.
19

---

Published as a conference paper at ICLR 2022
Remark The proof of Proposition 4 is an analogue of Proposition 2.11 in Schmitzer & Wirth (2019). The difference is that in our Proposition 4, besides f. we need to handle another variable h acting the lower bound of f. In contrast, Proposition 2.11 in Schmitzer & Wirth (2019) only handles the fixed h.
D.2 COMPUTATION OF GRADIENT
As we have proved the existence of the potential of CM... we can now consider the differentiability of m. in the KR form.
We consider transformation T IR x Ω - Ω parametrized by 0 E RR Let To(-) = T(O,-) and denote 8g (3) the corresponding purw-forward measure of 3. We show Proposition and 5 that, if To is Lipschitz w.r.t. 6, then the objective functions L,, 39) and Lasm (a, 3o) is differentiable w.r.t. 0, and the gradient can be computed explicitly.
Proposition 5 (Differentiability of mm. To Q S Lipschitz w.r.t. to 0, then Lm (a,, Bo) is continuous w.rll 0, and is differentiable almost everywhere. Furthermore, we have
VeCsm BB) Vef(To(z))d3.
(40)
where (f,h) h) is maximizer of LM
Proof. To begin with, for arbitrary 0, 0', we consider the following two-step procedure that transports m unit mass from a Sg. First, we transport m mass from to By according म, which is solution to Lm (a, Bg). Second, we transport m mass received in Be to Sgr according to plan x² defined as
(A) Bo(A)
T(Ax
B)
if (A > 0 else,
(A x B)
where (To(x). (z)) = 3(x). That is to transport all mass received at To(x) to the corresponding point To (z).. Thus we have
f 2(),2)d (x, S f( Jaxsa ((z,2)dT(2,2) = J.
Since To is Lipschitz w.r.t. 0, there exists constant A > 0, such that (z), To (x)) s 0 100-00 0'1) Therefore, the cost of the second step can be bounded as
I d(z, 2)d7 (2, 2) S m l'll. cost:
Denote cost the overall cost of this two-step procedure. We have
La m (a, 30) + m3All0 0'||-
By applying the gluing lemma (Villani (2009) 1ec.1) गे and n', construct transport plan स that transports unit mass from ग. to T. Denote cost2 Jaxn d(z, v)d y) the cost of स. On one hand, we have
C m (a, (g.) I cost2
according to the definition of L m- On the other hand, we have
cost2 I cost1.
Because for arbitrary x,, E Ω, the two-step procedure and स transport the same amount of mass between them. However, the cost of transporting a unit mass from is d(æ,,)) d(y, 2) for a E Ω for the two-step procedure, but is d(x, z) for म, which is cheaper according to triangle inequality. By combining these inequalities together, we have
Lasm (a, 3or) S cost2 Z costi LM.m Bo) + m1 0'11.
i.e.,
L. (a, 30r) S LMM Bo) m 0'11
20

---

Published as a conference paper at ICLR 2022
By switching 9 and 0' and repeating the argument, we have Ma, 30) S (a, 30r) + m - 0'1l
thus have
(a, (0) La, Bor m 0'1,
which suggests LM. (a, BB) is continuous w.r.t. 8, and Radamacher's theorem states that it is differentiable almost everywhere.
The sketch of the rest the proof is as follows. According to Proposition 4, the maximizer to the KR write VoLM, (a, 5o) - Vo Ia (To(2))) according
form of mm (a,, 3o) exists, thus to the envelope theorem (Milgrom & Segal, 2002). Then we prove
Ve / f(To(z))d3- / Vof(To(z))d3,
when the right hand side of the equation is well defined following Arjovsky al. (2017), which completes our proof.
Proposition 6 (Differentiability of CD..). If : - Ω is Lipschitz w.r.t. to 0, then CD (a, continuous w.z.. 9, and is differentiable almost everywhere. Furthermore, we have
(a, Bg)
is
VoLDala,3o) / Vof(To(z))
(41)
where f is a maximizer of LD
Proof. We first prove (a, Ba) is continuous w.r.t. 6. By definition, we have LD B)
KR, (a, B) - (m + mg). Thus by triangle inequality the KR metric, for arbitrary 0, 0' E Rd we have
(a, 3o) LD, (8
= <KRM(a,, (B0)
h (max + msa)) (KRn(a, Brr) (ma + mz
h
- (a,, BB)
(R,
<KR, (Bpr, (Ber, ,80)
(42)
Note that the second equality holds because T maintains the total mass, i.e., māg mās mg. In addition, we have
KR (3gr BB) & (Bgr d(TT(v) (v))dB(v))
By assumption, is Lipschitz w.r.t. 0, thus there exists constant A > 0. such that d(Ta(v), To (v)) < A 0'11. Thus (Bgr, 30) I m3Al(0 0'|l. Finally, we have
(a, BB) (D, ( < KR (3gr 38) I m3 0'1l.
which proves LDD (o. 3o) is continuous w.r.t. 0, and Radamacher's theorem states that it is differen- tiable almost everywhere.
The rest of the proof is similar to that of Proposition 5.
The main idea used in the proofs in this section is based on that in Arjovsky et al. (2017). However, a key difference is that unlike Wi. neither LM.m nor LD. is a metric, i.e., they do not necessarily satisfy triangle inequality, thus the differences cannot be bounded directly. This gap bridged by using the KR metric in Proposition 6, and by constructing a transportation plan in Proposition 5.
Remark
21

---

Published as a conference paper at ICLR 2022
D.3 APPLICATION TO POINT REGISTRATION
For point set registration task, we focus on the discrete distributions and re-state the previous results. We first present the proof of the main theorems in the main text.
Proof of Theorem I. The KR formulation of Lp.s is given in (30), and the existence of the optimizer is proved in Proposition 3. The gradient of LD. (ar, Ba) is derived in Proposition 6. Theorem is proved by applying these results to discrete distributions.
Proof of Theorem 2. The KR formulation of LM. is given in Theorem 3, and the existence of the optimizer is proved in Proposition 4. The gradient of (a, Bo) is derived in Proposition 5. Theorem is proved by applying these results discrete distributions.
Then we verify that the parametrized transformation To used in our paper satisfies the regularity assumption, i.e., it is Lipschitz w.r.t. the parameter 6.
Lemma 2. IfT: IRd x Ω - Ω is Lipschitz w.r.t. to its first variable, then for arbitrary y E Y, and 0, O' E Rd, there exists A such that
(TTo To A110 0'11-
Proposition 7. Given point set Y (m S Lei 0 = V) E R12-3r, where A E R3x3 a affinity matrix, E RR1x3 is a trunslation vector, V E R is the offset vectors for all points in Y. and V, represent the i-th V. For each point yi Y, define To(ys) y:A + V4, where :
V, represents the i-th row of V.T: IR d x Q 02 is Lipschitz w.r.t to its first variable.
Proof. Note for arbitrary A, there exists 8 > 0, such that ||A||2 S 6||A||, where || || is the
Frobenius norm. For arbitrary 0 = (A,t, 0 = (A, V) and yı E Y. we have
[[To():) To( 1I(A A)y, + + (V. 1/)12
< ||A A| + 1 2| + ||; V/ll2
s 8||4 /
1|0 0|1 + ||0 0|1
s 6110 01 1l + -10000112 + ||0 0|2
1 || + 2 8112.
which proves that T Lipschitz w.r.t. its first variable.
E PROPERTIES
This section answers two questions: 1) What are the connections between KR forms of CM,m and CD.A? 2) What does the potential of Lm.m looks like? We briefly discuss the first question in Sec. E. For the second question, the main result is Proposition 11 in Sec. E.2, where we show that for each point in and 3, the potential f either has gradient norm attains its maximum or minimum.
E. CONNECTIONS BETWEEN LM, LD AND W1
This subsection briefly discuss the relations between the KR forms L LD. a and Wi.
The following proposition presents a simple fact about the relation between LM and L. We omit all proves in this subsection as all results can be easily verified.
a..3 m For the fixed Proposition (Relations between LM and LD). Let f be a maximizer of
h* if) f also a maximizer of L... p.
Now we turn to the special cases of Lm.m and L To begin with, we define two useful functionals follows.
22

---

Published as a conference paper at ICLR 2022
Definition 3 (LP"). Define functional 0.0 Lp
Ja fd - fn fd3 I E Lip(O). f S 0, ma 2 mp
Lp LP (f)
11 -00
(43)
else,
and define Lr(a, 3) = sup LP
Definition (WT. Define the functional associated to Wasserstein-1 metric W1 as
So fda - Ja f Lip(S)), m. 2 mg
L a..3
W (f)
(44)
-00
else,
thus Wi can be expressed as Wi (a, B) sec(ia LW (f).
The following proposition describes the relations between LM LD, Lp and W1- Proposition (Special cases of L. and LDD.). (!) When ma 2 mg m. the maximizer of Lm also a maximizer of Lp.
(2) When m. 2 my and h 2 diam the maximizer of Ln, is also maximizer of Lp. (3) When m. ma, the maximizer of Lp also maximizer of W1.
We note Lp is for "semi-complete Wasserstein problem, where all mass of / is transported to Thus may be interesting on its own, for example in the template matching problem where the data points in an incomplete "data distribution" is matched to complete "model distribution".
Finally, we have the following straightforward corollary.
Corollary 1. (1) When ma = mg = m, M. equivalent to W1- (2) When m. my and h 2 diam(S2). LD,, is equivalent to Wi hm,g
E.2 PROPERTIES OF THE POTENTIALS
Consider W, as a special case of L. Its potential has the following property.
Lemma 3 (Potential of Wi (Gulrajani al., 2017)). Let f be a maximizer of W Then f has gradient norm (a + 3almmoss surely.
The main result of this subsection is the extension of this property to LMM.. in Proposition 11.
To begin with, we note that by definition, LM. 3) only transports a fraction of mass and discards the other. We called the transported mass "active" and the discarded mass "inactive". An important observation that, if we throw away some inactive mass, the solution to the problem will not be affected; and if we only focus on the active mass, we immediately obtain a solution to Wi. This is formally stated as follows.
Proposition 10. Let π be the solution to the primal form of (a, Define a' and B be measures satisfying
(A) S d'()) & a(A) and T2 < (A) S 3(A).
(45)
for an arbitrary measurable set A.
(1) x. is also the solution to the primal form of ma (a', 3') and W1 ( Tz. thus
Lms,m (a, B) Las,m (3',)")))))))))) Wi (
(46)
.9 (2) Let ff be maximizer of M.m- Then is also maximizer of L L and W
Proof. (1) Notice all admissible solutions to W1 (1 T2K are also admissible solutions to L.mm(a, 8). Then we can prove W1 x22) = L..( B) by contradiction. Similarly, we
prove Wi ( x Las (ax, B).
23

---

Published as a conference paper at ICLR 2022
(2) Note we have
La (f) = / Ida' { (inl(()) - f)d8' inf(f)m
fda+ I (inf(f) - f)d3 - inf M. (f) Lam 9), (47)
where the inequality holds because f S O. inl first part of this proof, we have Lm ,3) = Lss m. (a, (a.B) B), thus a' 3 (f) S (a'
S 0, a' S and 3' S B. According to the
M.m.
Mm (a, 3). By combining these two equalities, we conclude that L 8 M.m (f) Lmm (,',
LM (a, 3), i.e., f is a maximizer of a'.9 In addition, we have
M,m
fdr - / fd 2
fdn / fdu inf(ff(m m(m))))
W
(f) = 52
L M.m
(f) 2 L 0.8
M.m (f) = (a,
where the first inequality holds because - inf(f)(m m I O, and the second inequality holds following equation (47). According to the first part of this proof, we have (1 x
M. (a, 3), thus W i i (f) (T x LM,m 3). By combining these two equalities, -h
conclude Wi
Wi T3H)T Lm (a, B), ie., f is maximizer of W *
Thanks to Proposition 10 and Lemma 3, we can now characterize the potential of L.m active mass. This is formally stated the following corollary.
Corollary 2. Let be the solution to the primal form of Lm (a, and f be maximizer of M. Then f has gradient norm 1 (m) + ) -almost surely.
Now, in order to completely characterize the potential of LM.m. we only need to characterize the potential the inactive mass. In fact, find that the behavior of potential is rather simple the inactive mass, ie., it always attains its maximum or minimum. This is formally stated as follows.
Corollary 3 (Flatness on inactive mass). Let f be maximizer of M and π be the solution the primal form of L M. Let ag and is be non-negative measures satisfying
x4 a aa-as S and x 8 Bs S B. Then f = 0 a---alostt surely, and f = if((f) Bs-almost surely.
Proof. According to Proposition 10, we have La-ag. In other words, we have
8 M.m. M.m and f is maximizer of L as.p M,m
1 fda / f3 (m mg) / fdla as) / ff ff3-in(()(mm mm))
By cleaning this equation, obtain Jp fdds Since f < 0 and as is non-negative measure, we conclude that f = 0 oss-almost surely. The statement for 3s can be proved in a similar way. O
Finally, we can present a qualitative description for the potential of Lm.m by decompose mass a and 3 into active and inactive mass.
Proposition 11. Let f be maximizer of L ma, 9). There exist non-negative measures p. Va S and Vy < 3 satisfying + Va + V = a a++7 B, such that 1) f has gradient norm 1 p-almost surely 2) attains the maximum V. Va-almost surely, and 3) f attains the minimum ug-almost surely.
We note that similar conclusion holds for LD.
Proposition 12. Let be maximizer of (a. 3). There exist non-negative measures μ., Va S and V/ < 3 satisfying + Vo + V3 = a + B. such that 1) & has gradient norm p-almost surely 2) atlains the maximum Vg-almost surely, and 3) f attains the minimum vg-almost surely.
24

---

Published as a conference paper at ICLR 2022
Remark Given Proposition 11, important question is where the inactive mass. An direct observation is that if a region is far away from one of the measures, then all mass within this region easily identify some inactive regions where the potential attains its
is inactive. Therefore, maximum or minimum, ie., flat. We present the following straightforward propositions without proof. A practical example is shown in Fig. 9.
Corollary (Flat region). Let f denote maximizer of M.m Denote regions
Fa { supp(B)) - -inf(f)] and FB ==F=syydett yyldistly. supp(a)) - inf(ff).
Then f = 0 alsa aalmost surely, and f - inf(f) 81yg-almoss surely.
Corollary 5 (Flat region). Let denote maximizer of L Denote regions
Fa = (r]dist(s, 33)) > ht) and FB - yldistly, (o)dist((..upp(a))) > h). -almost surely, and h 815,-almost -almost surely.
Then = 0 -almooaloost
F MORE DETAILS OF THE MAIN TEXT
F.1 MORE DETAILS OF SEC. 2
Our method related to Wasserstein generative adversarial network (WGAN) (Arjovsky et al., 2017). which is popular method for large scale DM problems. A recent survey of the applications of WGAN can be found in Gui al. (2020). WGAN efficiently optimizes the Wasserstein- metric by approximating the KR potential using neural network. This technique is also used in our method. In this sense, our method directly generalizes WGAN to PDM problems.
F.2 MORE DETAILS OF SEC. 4.2
We present a simple example comparing the primal and the KR forms in Fig. 9. We show the correspondence obtained by the primal form in the 1-st row, where the black lines link the corresponding points. To estimate the KR forms, parametrize the potential function fw, by neural network shown in Fig. 10, and learn fwrk by maximizing (10) or (11). The 2-nd row visualizes the learned potential function fw,k- The corresponding gradient norms V fw,k are shown in the 3-rd row. V fwrhh are further visualized in the 4-th row, where the size of each point approximately proportional the gradient norm.
We further evaluate the precision of the estimated KR forms. For each setting, we compute LM.. LD. in the KR forms by inserting the learned potential fw. back into (10) (11) (without the gradient penalty term). To obtain the true values of M.mm and LD we compute their primal forms (1) and (2) using the POT tool box (Flamary al., 2021). The results are summarized Tab. 2. As can be seen, our estimated PW discrepancies are close to the true values with the averaged relative error less than 0.2%, which we think sufficiently precise for our application.
As for the efficiency, we note that the KR formulation is not advantageous in this data scale, i.e., tens of points, where the computation the exact primal form only takes less than 1 sec on a CPU, while the computation of the KR form takes a few minutes on a mid-end GPU (due to the requirement of learning the potential network). However, for large scale dataset, e.g., 10 which the primal form not handle because the transport map (of size 10t 10") does not even fit into the memory, the KR form can still apply (as validate our experiments) using a GPU with 12G memory.
Finally, we stress that since the implement of the KR form depends the underlying neural network, both the efficiency and precision naturally depend on the structure of the neural network. This is fundamentally different from the solvers of the primal form, such the Sinkhorn algorithm or the linear program, which are fixed pipelines. Therefore, is generally not possible to compare the efficiency and precision between the KR solvers and the primal solvers in rigorous way.
F.3 MORE DETAILS OF SEC. 4.3
To estimate the gradient of the coherence energy fast, we first decompose G as z QAQ" via the Nyström method (Williams& & Seeger, 2000), where h r, x and A E R is diagonal
25

---

Published as a conference paper at ICLR 2022
04
4.4
80
0.
f
-0.4
-1.4
-04
-04
-1.5
60
25
14
-55
0.0
05
1.0
-05
60
55
1.5
-0.1
0.
05
3.0
04
VV
0.0
86
M
-55
15
10
MV 04
64
M
0.4
-64
(a) LM.25 or LD.0.64 (b) LM or LD.1.0 (c) LM or Lp.5
(d) W4
Figure 9: Comparison between the primal and the KR forms of the PW discrepancies (blue)
and 3g (red). See text for details.
Table Precision of the estimated PW discrepancies for the "fish" shape in Fig.
MM225
Las.50
LM.78
Cp.0.648
Lp.1.99
LD.5
Wi
True value
0.1354
0.4191
0.8955
-0.0722
-0,2795
-4. 1040
1.0835
KR (Ours) 0.1352
0,4202
0.8994
-0.0724
-0.2791
-4.1004
1.0893
matrix. Then we apply the Woodbury identity to (oI + QAQ"))- and obtain
(oI+ QAQ")- o o " - -Q
As result, the gradient of the coherence energy can be approximated as
ac(Te)
2X + G)
av
F.4 CONNECTIONS BETWEEN PWAN AND WGAN
In practice, the only difference between PWAN and WGAN is the structures of the potential networks. This is summarized in Tab. 3. is easy to see that when m. = mg = m for L or m. = m and h > dSam(()) for LD,E. both d-PWAN and m-PWAN become WGAN.
Table Comparison between the potential networks of WGAN and PWAN.
input threshold Lipschitz negative & bounded lower bound h
WGAN
d-PWAN
distance mass
fixed learnable
m- PWAN
We note that PWAN has the following adversarial explanation. Let us call the points a real points, and those in Bo fake points. In the registration process, fu,h is trying discriminate real and fake
26

---

Published as a conference paper at ICLR 2022
points by assigning each of them score in range [-h, O). where real points have higher scores than fake points. fu.A is so certain of a fraction of points, that assigns the highest or lowest possible score (0 or -h) to them and does not change these scores easily. Meanwhile, To is trying to cheat fu.h by moving the fraction of fake points of which fuch is not certain to obtain higher scores. In addition, To is also trying move all fake points to keep the coherence energy low. The process ends when To cannot make further improvement on the fake points.
F.5 EXPERIMENTAL DETAILS
Data synthesis The data synthesis procedure mostly follows Hirose (2021b). Specifically, given the original point set X E Rrx3, the deformed point set Y E I2*3 is generated by:
y + +
(48)
where E is the Gaussian noise following (0, 0.02), and V E R is the random offset vectors. To ensure V varies smoothly in the space, we sample column vector Vj from distribution p:
p(u) = (o; 0, 0, GG)
(49)
where G R is Gaussian kernel defined as Gp(i, e e- lbx - To sample V from ditribution p. we compute V G U, where Rrx3 a random matrix, of which each element follows (0, 1), and G x QA computed via the Nyström method. We use À 10 or 50 and 2 in our experiments.
Network structure The network used in our experiment a 5-layer point-wise multi-layer percep- tron with skip connection. The detailed structure is shown in Fig. 10,
mip (32,64)
nx
mlp (64, 128)
X2LX
mip (1)
concate
The structure of the network used our experiments. The input is a matrix of shape (n,3) representing the coordinates of all points in the set, and the output is matrix of shape (n, 1) representing the potential of the corresponding points. mlp(z) represents a multi-layer perceptron (mlp) with the size For example, mlp(m, m, n) represents mlp consisting of two layer, and the size of each layer is y and n. We use Rel. u activation function in all except the output layer. The activation function I(r;h) max (arl, h. is added to the output clip the output to interval O].
Figure 10:
Parameters We train the network fw.h using the Adam optimizer (Kingma & Ba, 2014), and we train the transformation To using the R.Mpprpp optimizer (Tieleman & Hinton, 2012). The learning rates of both optimizers are set to 10-4
For experiments in Sec. 5.3, the parameters as set as follows: For PWAN, we set (p, A, o, T) (2, 0.01, 0.1, 2000). For TPS-RPM, we set T T_finalfac For GMM-REG, we set sigma- 0.5, 0.2, 0.02, Lambbda = .1, 02, .01, max_ fotu___unctio__vee evals 50, 50, 100 and level 3. For BCPD and CPD, we set (3, w)
500, frac = 1, and T'init 1.5.
2.0.
For experiments in Sec. 5.4, the parameters as set as follows: For PWAN, we set (p. X, o, T) (1.0, 10-3 1.0,, 3000). For BCPD and CPD, set (8, X, w) (3.0, 20.0, 0.1). We also test w 0.4 for these methods, but the difference is not obvious.
For experiments in Sec. F.9, the parameters as follows: For PWAN, set (p, 0, (0.5,5 10 -4 1.0, 3000). For BCPD and CPD, we set (3, w) = (3.0, 0.1).
For experiments in Sec. F.10, the parameters set follows: We use m-PWAN. we set (p. X, T) (1.0, 1 x 10 1.0, 3000). For BCPD and CPD, we set (3, A, w) = (0.3, 2.0, 0.1). We also tried = 0.6 but the results are similar (not shown in our experiments).
27

---

Published as a conference paper at ICLR 2022
We note the parameters for CPD and BCPD suggested in Hirose (2021a).
Parameter selection The parameters m in m-PWAN and h in d-PWAN control the degree of alignment. Specifically, increasing m or h will lead the registration of larger fraction of distributions. When m = 0 or h 0, PWAN does not align any point (the gradients are 0 for all points); When m min(m,. (,, ma} or = oo, PWAN seeks align the largest fraction of points. Therefore, choosing overly large m or h may lead to the biased registration (like DM method), while choosing overly small m or may lead to the insufficient registration where too few points are aligned.
For uniform point sets, the parameters m and h can both be determined easily. For d-PWAN, if the averaged nearest distance between points 8, then can be set near s. Because for the aligned point sets, the points that are farther from the overlapped region than distance are likely to be outliers, and the use of h = 8 can effectively discard those outliers. For m-PWAN, one needs to estimate the overlap ratio p of one point set, e.g., a, then can be set as pm.. We note this is how actually determined m and h in our experiments.
Refinement In our experiments, we find that a nearest-point-bast based refinement sometimes slightly improves the performance. Specifically, when the algorithm 1 is near convergence, we can optionally run few steps of the nearest-point-be vergence,
refinement. Specifically, since algorithm near con- safely assume that the point sets are sufficiently aligned. Therefore, each point is highly likely to correspond to its nearest neighborhood in the other set within the mass or distance threshold. other words, the correspondence matrix P E Tgyx can be written as
1
if = (x,) and d(ys. xz) S h else
Pi. = {0
(50)
for LD and
[1 iS yソ = NN,),) and x, E Nearest(m)
P.j = (0
(51)
else
for LM. where NN() is the nearest neighborhood function, and (eares((m) represent the nearest m points in X to Y. Thus we can slightly refine the result by switch the divergence term L to
L(a, Ba) = Σ Pajd(s To(
(52)
1.j
and update a few steps of the transformation To via gradient descent.
F.6 MORE DETAILS OF SEC. 5.2
The KL divergence and the L2 distance between point set X and Y are formally defined as
Lz(X,))= Σ
60 20)
1
6(0 yy 20)
2
6(0|z, My. 20),
(53)
gr
Ei EY
KL(X,Y)
1 log
w 1 (w
Σ
L
(54)
WEY
x,EX
where 6b-lu, r) is the Gaussian distribution with mean u and variance For simplicity, we set 1 and w = 0.2 for KL and Lz.
F.7 MORE DETAILS OF SEC. 5.3
We present more results of the experiments with 2000 in Fig. 1I and Fig. 12, and the corre- sponding quantitative results are shown in Tab. 4 and Tab. 5. We do not show the results of TPS-RPM on the second experiment, as it generally fails to converge. As can be seen, PWAN successfully registers the point sets in all cases, while all baseline methods bias toward to the noise points or to the non-overlane -verlaaald region when outlier ratio high, except for TPS-RPM which shows strong robustness against noise points comparable with PWAN in the first example.
28

---

Published as a conference paper at ICLR 2022
To obtain sense of the learned potential network fu.h. visualize the potential at the end of the registration process. The results are shown in Fig. 13 and Fig. 14. We represent the value of potential and the gradient norm at each point by colors, where brighter color indicates higher value. As be seen Fig. 14(c) and 13(c), the network assigns higher values to the points in a while assigning lower values the points in Bo- In addition, shown in Fig. 14(d) and 13(d), most of outliers, including noise points and the points in non-overlapping region, have low gradients, i.e., they are successfully discarded by the network.
(a) Initial sets
(b) BCPD
(c) CPD
(d) GMM-REG (c) TPS-RPM
(f) PWAN
Figure 11: An example of registering noisy point sets. The outlier/nonooutlerr ratios of the point sets shown here are 0.2 (Ist row), 0.6 (2nd row), 1.2 (3rd row) and 2.0 (4th row).
Table 4: Quantitative comparison of the registration results shown in Fig. 11 using MSE
OutlierNoonooutlier ratio
BCPD
CPD
GMM-REG
TPS-RPM
PWAN
0.2
0.011
0.0015
0.018
0.0032
0.0031
0.6
0.075
0.083
0.022
0.0026
0.0030
1.2
0.12
0.21
0.042
0.0033
0.0030
2.0
1.24
0.289
3.76
2.354
0.004
Table 5: Quantitative comparison of the registration results shown in Fig. 12 using MSE
Overlap ratio
BCPD
CPD
GMM-REG
d-PWAN
m-PWAN
0.57
0.18
0.92
0.32
0.017
0.015
0.75
0.028
0.45
0.043
0.0044
0.0090
1
0.00072
0.0025
0.0078
0.0037
0.0038
F.8 MORE DETAILS OF SEC. 5.4
We provide more details regarding the computation time of our method. We first sample 4 = r points from the bunny shape, where and the 2 GPU version of PWAN 100 steps, and report their computation time in Fig. 15, where GPU represents registering g points using M GPU. As can be seen, the majority of time is spent
10a 7 10a. We then run both the 1 GPU version
29

---

Published as a conference paper at ICLR 2022
(a) Initial
(b) BCPD
CPD
(d) GMM-REG
(c) d-PWAN
(f) m-PWAN
Figure 12: An example of registering partially overlapped point The overlap ratio of the point sets shown here are 0.57 (Ist row), 0.75 (2nd row) and (3rd row).
(a) Initial sets
(b) Registered sets
(c) Potential f
(d) V
Figure 13: Visualization of the learned potentials on point sets with extra noise points.
updating the network, and the parallel training effectively reduce the computation time for updating the network. addition, the gain of speed increase as the number of points, i.e., we get 1.3x speedup when 9 103, while the speedup is 1.9x when q 7 x 10a, which is close to the theoretical speedup value 2.
Finally, evaluate PWAN large scale point sets. We generate noisy and partially overlapped armadillo datasets as stated Sec. 5.3. We compare PWAN with BCPD and CPD, because they are the only baseline methods that scalable in this experiment. We present some registration results in
30

---

Published as a conference paper at ICLR 2022
(a) Initial sets
(b) Registered sets
(c) Potential f
(d) Vv
Figure 14: Visualization of the leamned potentials on partially overlapped point sets.
500
updating updading
100
Time
200
100
n6 nn-oo
7xx sGaU
Figure 15: Computation time of our method.
Fig. 16. As can be seen, our method handle both cases successfully, while both CPD and BCPD bias toward outliers.
More training details of PWAN is shown in Fig. 17, Fig. 18 and Fig. 19. As can be seen in Fig. 17()), 18(a) and (a),, the source sets are matched to the reference sets smoothly, Fig. 17(b), 18(b) and 19(b) suggest that at the end of the registration process, most of outliers are correctly discarded. Besides, Fig. 17(c), 18(c) and 19(c) implies that the norm of gradient of the network is indeed controlled below 1, i.e., indeed Lipschitz. In addition, both the training loss and the MSE decrease smoothly in the training process.
F.9 EXPERIMENT ON THE HUMAN FACE DATASET
We evaluate our method in the space-time faces dataset (Zhang et al., 2008), which consists time series of point sets sampled from real human face. Each face consists of 23, 728 points and the true correspondence between faces are known. We use the faces time and + 20 as the source and the reference set, where i 1.... 20. All point sets in this dataset are the same size and completely overlapped.
20.
The registration results shown in Tab. 6, where BCPD. We present the examples of the registration results Fig. 20. As can seen, PWAN successfully aligns the faces in different time points.
PWAN outperforms both CPD and
31

---

Published as a conference paper at ICLR 2022
Initial sets
BCPD
CPD
PWAN
(a) An example of registering noisy point sets. The source and refernece sets contain 8 x 10 and 1.76 x 10 points respectively.
d-PWAN (b) An example registcring partially overlapped point sets. The source and refernece sets both contain x 10 points.
Initial sets
BCPD
CPD
m-PWAN
Figure 16: Examples of registering large scale point sets.
(a) Registration trajectory. The registration process proceedes from left to right.
1.6
Max grad norm
Training Refine
0.8
1.0
MSF
10
20
2000
2000
Steps
Steps
(b) Visualization of the potential f (left) and it gra- dient [V (right) the final step.
(c) Statistics of the training process.
Figure 17: One example of registering the noisy "armadillo" datasets. The source and refernece sets contain 8 x 10a and 1.76 x 10 points respectively.
Table 6: Registration results of the space-time faces dataset.
BCPD
CPD
PWAN
0.0017 + 0.001 0.00049 + 0.0002 0.00032 + 0.000089
F.10 EXPERIMENT ON THE 3D HUMAN DATASET
We evaluate our method on challenging human shape dataset (DataSet), which taken from SHREC' 19 track called "matching humans with different connectivity". This dataset consists of 44 shapes, and we manually select pairs of shapes for our experiments. To generate a point set each shape, first sample 50000 random points from the surface of the 3D mesh and then apply voxel grid filtering to down-sample the point set to less than 10000 points. The description for the selected point sets presented in Tab. 7
32

---

Published as a conference paper at ICLR 2022
(a) Registration trajectory. The registration process proceedes from left to right.
1.0
1.5
Training Refine
0.8
0.6
1.0
MSE
0.0
1000 2000
2000
0
1000
2000 Steps
3000
Steps
(b) Visualization the potential (left) and gra- dient [ (right) at the final step.
(c) Statistics the training process.
Figure 18: One example of registering the partially overlapped "armadillo" datasets using d-PWAN.
Each point set consists of 7 10 points.
(a) Registration trajectory. The registration process proceedes from left to right.
(b) Visualization of the potential (left) and it gra- dient [V (right) at the final step.
Max grad norm
Training Refine
1.0
0.3
Loss
MSE
10
0.2
0.5
0.1
1000 2000 Steps
3000
1000
2000
3000
1000
2000
3000
Steps
Steps
(c) Statistics of the training process.
Figure 19: One example of registering the partially overlapped "armadillo" dataset using m-PWAN. Each point set consists of 7 10 points.
33

---

Published as a conference paper at ICLR 2022
(a) The aligned point sets (right) is obtained by matching the 1-st frame (left) to the 21-st frame (middle)
(b) The aligned point sets (right) is obtained by matching the 19-st frame (left) to the 39-st frame (middle)
Figure 20: Examples of our registration results on the human faces dataset. Zoom in to see the details.
Table 7: Point sets used for registration. no.m represents the m-th shape in the dataset (DataSet).
1no. no.42)
(no.18, 19)
(no.30, no.31) (6895, 6792) different pose different person
Size
(5575, 5793)
(6090, 6175) different pose
same pose different person
Description
same person
We conduct the following two experiments. In the first experiment, we evaluate our method on registering the complete point sets. In the second experiment, we evaluate our method the more challenging partial matching problem, where we generate incomplete point sets by manually cropping fraction of the no.30 and n point sets. We consider 3 types of partial matching problem, i.e match incomplete set to complete set, match complete set to incomplete set and match incomplete set to incomplete set. For both of these two experiments, we compare our method with CPD and BCPD, and we only present qualitative registration results, because we do not know the true correspondence between point sets.
The results of the first experiment is shown in Fig. 21. As can be seen, PWAN can handle both the local deformations (1-st row) and the articulated deformations (2-nd and 3-rd rows) well, and produces good full-body registration results. In contrast, although CPD and BCPD can handle local deformations relatively well (I-st row), they have difficulties aligning point sets with large articulated deformations, significant registration errors are observed near the limbs (2-nd and 3-rd rows).
The results of the second experiment is shown in Fig. 22. As can be seen, both CPD and BCPD fail in this experiment, the non-overlapping points are seriously biased. For example. in the 3-rd row, they both wrongly match the left arm to the body, which causes highly unnatural artifacts. In contrast, the proposed PWAN can handle the partial matching problem well, since it successfully maintains the shape of non-overlapping regions, which contributions to the natural registration results.
Finally, we note that although the proposed PWAN generally produces reasonable full-body registra- tion results, it has some difficulties handling the local details. For example, the hands in Fig. 21 and 22 generally not well aligned. This drawback might be alleviated by considering local constraints such as Ge et al. (2014) in the future. In addition, it is worth noticing that the aligned point sets in the second experiments are natural and do not exist in the original dataset. These results suggests the potential of our method in other practical tasks such as point set completion and point sets merging.
34

---

Published as a conference paper at ICLR 2022
(a) Source set
(b) Reference set
(c) PWAN (Ours)
(d) BCPD
(e) CPD
Figure 21: The results of registering complete point sets no.1 no.42 (I-st row), no. no.18 18 19 (2-nd row), and no.30 to no.31 (3-rd row). Our results are compared against BCPD (Hirose, 2021a) and CPD (Myronenko & Song, 2010). Zoom in to see the details.
Source set
(b) Reference set (c) PWAN (Ours)
(d) BCPD
CPD
Figure 22: Registering incomplete point sets no.30 no.31. We present the results of the complete to incomplete (1-st row), incomplete to complete (2-nd row) and incomplete to incomplete (3-rd row) registration. Our results compared against BCPD (Hirose, 2021a) and CPD (Myronenko & Song, 2010). Zoom in to see the details.
35


Reviews:
[{"review_id": "yb0BL3lC1Jt", "reviewer": "Reviewer_dwHk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n1) It's very nice to have a method to avoid the computation of dense matching matrix in an optimal transport framework;\n2) The mathematical derivations are extensive and seem to be correct.\n\nWeaknesses:\n\nI would say the experiments are only validated on very small-scale synthetic and real-world datasets. I would expect the following experiments:\n\n1) Experiments on the 3D Human dataset [Section 4.3, Non-rigid Point Set Registration with Global-Local Topology Preservation]\n\n2) For synthetic experiments, it would be better to use the modelnet40 dataset, which contains many different shapes. Only using three shapes [bunny, armadillo and monkey] to train and validate methods has the risk of over-fitting.\n\n3) For the limited real-world experiment on the face dataset [E.10], it would be better to give more details. For example, what's the overlapping ratio between pairwise point clouds? How does the proposed method perform under different overlapping ratios? \n\n4) It's unclear whether the proposed method would be open-sourced. Since this paper contains many equations, re-implementing it would be very hard.", "summary_of_the_paper": "This paper proposes a partial Wasserstein adversarial network to register two non-rigid point clouds.\n\nThe major contribution is deriving a dual optimization objective to avoid the computation of a dense matching matrix.\n\nExperiments on toy/synthetic datasets and one small-scale real-world face dataset show the effectiveness of the proposed method.", "summary_of_the_review": "Overall, It's very nice to have a method to avoid the computation of dense matching matrix in an optimal transport framework. However, the limited experiments have not convinced me of its effectiveness on real-world datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nw9Tjm6fmq", "reviewer": "Reviewer_U9Y7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "As to the strengths of the paper, the authors are able to make a novel contribution to a classic problem. It is pleasing that the point sets are modelled as discrete distributions without the need of making smoothing like GMM based methods for instance do. The theoretical part of deriving the KR duality for the two types of chosen discrepancies is clearly a strength of the paper even though it is a harder part of the paper to read.\n \nAs to the weaknesses, the paper is generally relatively easy to read, however the toughest part in math could be improved for clarity to help the reader with the intuition what is going on. Especially the part related to the adversarial learning and the approximation of PW discrepancy could be described better. The experimental evaluation is performed with rather simplistic datasets for which more realistic data set could be used to improve the presentation.", "summary_of_the_paper": "The paper proposes a method for registration of two point sets by formulating the problem as partial distribution matching problem. The authors utilise the partial Wasserstein (PW) discrepancy, and show how its gradient can be computed. They further propose a partial Wasserstein adversarial network that approximates the PW discrepancy. The authors evaluate the method against four method against two artificial datasets in which the method shows good results.", "summary_of_the_review": "In summary, the work can be seen as well founded paper with clear theoretic contribution equipped with a practical method based on neural formulation of the registration problem. Good results on the selected datasets, though an evaluation with a more complicated datasets would improve the presentation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "k2UqfXvXdT", "reviewer": "Reviewer_x4db", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": " ***Strengths***\n- The paper  considers point set registration problem consisting in\n in learning a non-rigid transformation that matches a transformed\nsource set to a reference one while avoiding noisy points or outliers that do have\ncorrespondences in the other set.  To ensure the robustness of the\nmatching a partial distribution matching is sought using partial\noptimal transport.  Specifically the partial Wasserstein-1 (PW), where only a portion of the probability mass is moved,  is\nconsidered.\n\n- Two equivalent formulations are proposed, the plain PW problem\n  coined $\\mathcal{L}_{M,m}$ with explicitly mass constraint and the\n  \nrelaxed version $\\mathcal{L}_{D,h}$. The main results of the paper\n  are the derivation of the Kantorovitch-Rubinstein dual of both\n  problems. The dual is a constrained optimization problem\n  that involves a potential function defined as a neural network (NN). By\n  relaxation of the Lipschitz constraint on the NN, the dual  is amenable to a\ngradient framework and hence, to a large scale computation. \n\n- Learning of $\\mathcal{T}$ by minimizing the PW discrepancy with a\ncoherence regularization  leads to a min-max problem similar to  the\none of the Wasserstein GAN. The overall optimization algorithm is\ngiven.\n\n***Weaknesses***\n- As stated in the appendix, the Kantorovitch-Rubinstein (KR)  dual of  $\\mathcal{L}_{D,h}$ straightforwardly\nderives from (Lellmann et al., 2014; Schmitzer & Wirth, 2019). \nBy convexity argument, there exist $h \\geq 0$ such that problem  \n\n$\\mathcal{L}_{D,h}$ yields to a solution of problem\n\n$\\mathcal{L}_{M,m}.$\n\nHence, the dual Kantorovitch-Rubinstein  form of\n$\\mathcal{L}_{M,m}$ should follow. In that regard, the KR dual\nderivations of both PW problems appear issued directly from the\naforementioned works. This renders the main theoretical results of the\npaper rather incremental. \n\n- The relaxation  of the Lipschitz constraint on the NN implies that\n  the obtained dual objective function (even if the dual problem is\n  optimized to fully convergence) no longer represents the PW\n  discrepancy but an approximation. Hence, the gradient computation is biased and results in the loss of theoretical guarantees on the\nretrieved solution $\\mathcal{T}$ of the point set registration problem (3).\n\n- The paper lacks theoretical analysis of the convergence rate, the time\n  complexity of the PW computation.  In the same\n  vein, it lacks the comparison of the primal and dual solutions\n  (computation time, precision  of the PW losses) or the empirical convergence illustration of Algorithm 1.\n\n- It is not explicitly stated that Algorithm uses stochastic\n  gradient to gain in scalability. Nevertheless the paper does not\n discuss  reference  [1] dedicated to unbalanced minibatch optimal\n  transport (UOT) that can be a good alternative to the proposed method. [1]\n  established theoretical properties of UOT in presence of outliers,\n  in terms of gradient regularity hence the convergence property. How\n  the proposed method connects to [1]?\n\n- The transformation $\\mathcal{T}$ defined as an affine-like\n  deformation model is not fully explained nor justified. \n\n***Other comments***\n- How the final point set registration is obtained ? Does it require computing\n  the optimal transport map ? If so, how is it derived from the\n  prima-dual equation?\n- Report the means and the variances of the performances (MSE, computation time)\n  over the runs. That helps the reading of the results.\n- In Eq. (9), write $\\mathcal{T}_\\theta(y_j)$ rather than $y_j$.\n- In EQ. (19) $\\mathbf{G}$ should rather be $\\mathbf{G}_\\rho$.\n- In section 5.2 the number of samples is sufficiently reasonable to\nallow to compare primal solutions to dual ones in term of performances\nand computation time. This might highlight the efficiency brought by\nthe use of the dual form and better illustrates the trade-off\nefficiency vs precision. \n  \n***Reference***\n\n[1] Fatras, Kilian, et al. \"Unbalanced minibatch optimal transport; applications to domain adaptation.\" International Conference on Machine Learning. PMLR, 2021.\n\n**After rebuttal**\n\nI read authors rebuttal. They address some of the  raised points by  the review (use or not of stochastic gradient to gain in scalability, confidence interval of reported performances, better justification of the transformation $\\mathcal{T}$, gradient computation when relaxing the Lipschitz constraint...). \n\nThe strong point of the paper is the  KR dual form derivation of $\\mathcal{L}_{M,m}$ and this is not sufficiently highligthed in the paper. The authors should consider emphasizing more on that and better  highlight the novelty of the theoretical  KR dual form. During the discussion, the authors clarify how their approach connects to mini-batch regularized Unbalanced OT as promoted in Fatras et al. (2021) that solves the UOT problem in the primal.  This is also a good point. \n\nOverall the paper is  rather dense with almost 46 pages, the appendices  included. Nevertheless, provided aforementioned facts, I update my rating of the paper from 5 to 6. \n \n", "summary_of_the_paper": "The paper deals with  non-rigid point set registration via partial\ndistribution matching. The problem is formulated as\ncomputing partial Wasserstein-1 (PW) discrepancy between distributions of\nthe reference point set and of the transformed source point set.  As a\nmain feature, the paper derives the Kantorovich–Rubinstein dual form\nof the PW problem hence, allowing to lift the method to a large scale\nsetting. Overall the proposed method results in a min-max\nproblem (similar to Wassertein GAN) to learn the transformation function which minimizes the PW\ndiscrepancy. Empirical evaluations complete the paper. ", "summary_of_the_review": "The paper proposes a theoretical and methodological framework to\nachieve robust  point set registration using scalable partial\nWasserstein based on the dual formulation. Their derivations somehow\nderive from existing works. To be efficient, the  algorithm\nrelaxes the\nLipschitz constraint hence, the overall algorithmic scheme lacks\ntheoretical  guarantees on the matched distribution. Also the paper\nlacks convergence, time complexity analysis of computing PW. Finally\nconnections to works related to minibatch unbalanced optimal\ntransport that can be competitors of the method are missing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dF0noYEK8Pa", "reviewer": "Reviewer_7kLR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n+ The paper theoretically derives the Kantorovich–Rubinstein duality for two types of the PW discrepancy, i.e., the distance-type and the mass-type discrepancy\n\n+ The paper propose PWAN, for large scale PDM problem. \n\n+ Experimental results on the point set registration task prove that the proposed PWAN is robust, scalable and performs more favorably\nthan the state-of-the-art methods\n\nWeaknesses:\n\n-  The paper is rather dense, which may to some extent not well self-contained.\n\n-  The paper only evaluated on the point set registration task, other related task such as 2D shape matching could be exploited.", "summary_of_the_paper": "This paper deals with the problem of non-rigid point set registration, where a method for large scale partial distribution matching (PDM) problem is proposed by utilizing the partial Wasserstein-1 (PW) discrepancy.  The paper theoretically derive the Kantorovich–Rubinstein duality for the PW discrepancy, and show its gradient can be explicitly computed. Based on these theoretical results, the paper proposed a partial Wasserstein adversaria network (PWAN), which approximates the PW discrepancy by a neural network, and learns the transformation adversarially with the network. Experimental results on point set registration tasks such that the proposed PWAN is robust, scalable and performs more favorably than the state-of-the-art methods.", "summary_of_the_review": "The theoretical contributions are justified with experimental evaluation on the point set registration task. The experimental evaluations could be more extensive, for example, other related tasks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JkeuJ6wGp5n", "reviewer": "Reviewer_y2JC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is interesting and deals with an important problem: how to deal with outliers when registering 3d shapes. \nThe transformation $\\mathcal{T}_\\theta$ is found by simultaneously find a global transformation and optimizing a partial optimal transportation distance.\nI have few concerns that should be clarified:\n- eq. (2) is a reformulation of eq. (1). If there is a reason to have the two formulations, it should be better highlighted. Otherwise, it would add some clarity to avoid considering equivalent formuations.\n- the dual of the partial optimal transport problem is described in [1]. If there is some novelty here, it should be emphasized. Otherwise, appropriate references should be cited.\n- the choice of the parameters $m$/$h$ is the key of the success of the method. It would be interesting to add a discussion about it. What happens if their values are under/over estimated? Is there any thumb rule to choose their values?\n- Section 5.2 is unclear. Is there any reason that the translated dataset should not match the outliers when t is large? What prevent PWAN to align dataset Y to outliers?\n\n\n[1] Caffarelli, L. A., & McCann, R. J. (2010). Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, 673-730.", "summary_of_the_paper": "Paper proposes PWAN, a method that can be seen as an extension of WGAN in the presence of noise.\nIt uses the partial formulation of the wasserstein metric, allowing discarding points that are noise or outliers. It relies on the dual formulation of the problem to derive an efficient algorithm to learn a transformation that maps the target points toward the source points. Extensive experiments on toy datasets and 3 point clouds show that the method performs well, even in the presence of noise. ", "summary_of_the_review": "An interesting paper deals with an important problem but lacks some appropriate references.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the authors proposes to use partial optimal transport to align point cloud in the presence of noise and partially observed data. To this end they express the partial Wasserstein Kantorovich-Rubinstein duality and use it to adapt the classical WGAN loss to partial OT. The optimal alignment between point clouds is then done by minimizing their proposed loss where the dual potential are modeled as deep neural network hence approximating the partial Wasserstein while being solved using mini-batches. Experiments show the interest of the method on a few well understood examples with ground truth from the Stanford repository. 

The paper had originally borderline scores with some reviewers concerned about the theoretical contribution. The authors did a very good reply that that greatly appreciated by the reviewers, the one with the lowest score deciding to increase it. The new numerical experiments on the 3D human dataset were also appreciated. The consensus during the discussion was that the paper is worth accepting but that the authors should take into account the comments form the reviewers and better explain their contribution on the KR duality.

For these reason the AC recommends to accept the paper but urges the authors to take into account the comments from the reviewers. In particular the authors should better highlight their theoretical contribution and explain the link and differences with unbalanced minibtach OT.
Decision: Accept (Poster)