194
F. Nielsen and K. Sun
When the ground distance D is clear from the context, we write H ( p, q) for a
shortcut of H D ( p, q). A similar definition was introduced by [55] termed “Markov
construction.” In our work, the CROT is defined with respect to a distance metric on
the manifold C of conditional densities (information-geometric distance) rather than
a section of the distance metric on the space of (x, y).
A key property of CROT is stated as follows:
Property 8.2 (Metric properties) If D(·, ·) is a metric on C, then H D ( p, q) is a
metric on X and a pseudometric on Y × C.
The proof is given in Property 8.2. Notice that H D is a metric on X but only a pseudometric (satisfying non-negativity, symmetry, triangle inequality, and H D ( p, p) = 0,
∀ p ∈ Y × C instead of the law of indiscernibles of metrics) on the product manifold
Y × C.
Since
r (y, z)dydz = 1 and since r (y, z) = p(y)q(z) is a feasible transport solution, we get the following upper bounds:
Property 8.3 (Upper bounds)
H D ( p, q) ≤
y
z
p(y)q(z)D
p(x|y), q(x|z)
dydz
≤ max
y,z
D
p(x|y), q(x|z)
.
(8.2)
The CROT distances unify and generalize two distances met in the literature:
Remark 8.4 (CROT generalizes Wasserstein/EMD) In the case that p(x|y) = δ(x −
y) (Dirac distributions), we recover the Wasserstein distance [60] between point sets
(or Earth Mover Distance, EMD; [54]), where D(·, ·) is the ground metric distance.
Note that point sets can be interpreted as discrete probability measures.
The Wasserstein distance W p (for p ≥ 1, with W 1 introduced by [62]) follows
from the Kantorovich’s [26, 27] relaxation framework of Monge’s [34] original
optimal mass transport formulation.
Remark 8.5 (CROT generalizes MCOT) When both p(y) and q(z) are both (finite)
categorical distributions, we recover the distance formerly defined by [33] that we
termed the MCOT distance.
CROT is a nontrivial generalization of both the Wasserstein distance and the
MCOT, because CROT gives a flexible definition on the OT. Given a joint distribution
p(x 1 , . . . , x n ), one can consider a family of distances, depending on how the random
variables x 1 , . . . , x n split, and how the ground distances D are selected. For example,
one can define D to be CROT and we have a nested CROT distance. In the simplest
case, let
F. Nielsen and K. Sun
When the ground distance D is clear from the context, we write H ( p, q) for a
shortcut of H D ( p, q). A similar definition was introduced by [55] termed “Markov
construction.” In our work, the CROT is defined with respect to a distance metric on
the manifold C of conditional densities (information-geometric distance) rather than
a section of the distance metric on the space of (x, y).
A key property of CROT is stated as follows:
Property 8.2 (Metric properties) If D(·, ·) is a metric on C, then H D ( p, q) is a
metric on X and a pseudometric on Y × C.
The proof is given in Property 8.2. Notice that H D is a metric on X but only a pseudometric (satisfying non-negativity, symmetry, triangle inequality, and H D ( p, p) = 0,
∀ p ∈ Y × C instead of the law of indiscernibles of metrics) on the product manifold
Y × C.
Since
r (y, z)dydz = 1 and since r (y, z) = p(y)q(z) is a feasible transport solution, we get the following upper bounds:
Property 8.3 (Upper bounds)
H D ( p, q) ≤
y
z
p(y)q(z)D
p(x|y), q(x|z)
dydz
≤ max
y,z
D
p(x|y), q(x|z)
.
(8.2)
The CROT distances unify and generalize two distances met in the literature:
Remark 8.4 (CROT generalizes Wasserstein/EMD) In the case that p(x|y) = δ(x −
y) (Dirac distributions), we recover the Wasserstein distance [60] between point sets
(or Earth Mover Distance, EMD; [54]), where D(·, ·) is the ground metric distance.
Note that point sets can be interpreted as discrete probability measures.
The Wasserstein distance W p (for p ≥ 1, with W 1 introduced by [62]) follows
from the Kantorovich’s [26, 27] relaxation framework of Monge’s [34] original
optimal mass transport formulation.
Remark 8.5 (CROT generalizes MCOT) When both p(y) and q(z) are both (finite)
categorical distributions, we recover the distance formerly defined by [33] that we
termed the MCOT distance.
CROT is a nontrivial generalization of both the Wasserstein distance and the
MCOT, because CROT gives a flexible definition on the OT. Given a joint distribution
p(x 1 , . . . , x n ), one can consider a family of distances, depending on how the random
variables x 1 , . . . , x n split, and how the ground distances D are selected. For example,
one can define D to be CROT and we have a nested CROT distance. In the simplest
case, let