196
F. Nielsen and K. Sun
Notice that H D ( p, q) = H D (q, p) for an asymmetric base distance D.
Let us give some examples of jointly convex distances: ➀ The f -divergences
[47] I f ( p : q) =
p(x) f (q(x)/ p(x))dx (for a convex generator f (u) satisfying
f (1) = 0 and strictly convex at 1); ➁ The p-powered Wasserstein distances [48] W
p
p ;
➂ The Rényi divergences [61] for α ∈ [0, 1]; ➃ Bregman divergences [5, Exercises
2.3.29 and 2.3.30] provided that the generator F satisfies ∇
2 F(y) + ∇
3 F(y)(y −
x) (∇
2 F(x)∇
2 F)
−1
(y) where denotes the Löwner ordering of positive-definite
matrices. ➄ A generalized divergence related to Tsallis divergence [63].
A jointly convex function is separately convex but the converse is false. However,
a separately convex bivariate function that is positively homogeneous of degree one is
jointly convex (but this result does not hold in higher dimensions; [10]). Conversely,
CROT yields a lower bound for jointly concave distances (e.g., fidelity in quantum
computing; [46]).
8.3 SCROT: Fast Sinkhorn CROT
Consider two finite statistical mixtures m 1 (x) =
k 1
i=1 α i p i (x) and m 2 (x) =
k 2
i=1 β i q i (x), not necessarily homogeneous nor of the same type. Let [k]:=
{1, . . . , k}. The MCOT distance proposed by [33] amounts to solve a Linear Program
(LP) problem.
By defining U (α, β) to be set of non-negative matrices W = [w i j ] with
k 2
l=1 w il = α i and
k 1
l=1 w l j = β j (transport polytope; [8]), we get the equivalent
compact definition of MCOT (that is a special case of CROT):
H D (m 1 , m 2 ) = min
W ∈U (α,β)
k 1
i=1
k 2
j=1
w i j D( p i , q j ).
(8.5)
In general, the LP problem (with k 1 × k 2 variables and inequalities, k 1 + k 2 equalities
whom k 1 + k 2 − 1 are independent) delivers an optimal soft assignment of mixture
components with exactly k 1 + k 2 − 1 nonzero coefficients
1 in matrix W = [w i j ]. The
complexity of linear programming [31] in n variables with b bits using Karmarkar’s
interior point methods is polynomial, in O(n
7
2 b
2
).
Observe that we necessarily have: max j∈[k 2 ] w i j ≥
α i
k 2
, and similarly that:
max i∈[k 1 ] w i j ≥
β j
k 1
. Note that H (m, m) = 0 since w i j = D i j where D i j denotes the
Krönecker symbol: D i j = 1 iff i = j, and 0 otherwise. We can interpret MCOT as
a Discrete Optimal Transport (DOT) between (non-embedded) histograms. When
k 1 = k 2 = d, the transport polytope is the polyhedral set of non-negative d × d matrices:
U (α, β) = {P ∈ R
d×d
+
: P1 d = α, P
1 d = β},
1 A LP in d-dimensions has its solution located at a vertex of a polytope, described by the intersection
of d + 1 hyperplanes (linear constraints).
F. Nielsen and K. Sun
Notice that H D ( p, q) = H D (q, p) for an asymmetric base distance D.
Let us give some examples of jointly convex distances: ➀ The f -divergences
[47] I f ( p : q) =
p(x) f (q(x)/ p(x))dx (for a convex generator f (u) satisfying
f (1) = 0 and strictly convex at 1); ➁ The p-powered Wasserstein distances [48] W
p
p ;
➂ The Rényi divergences [61] for α ∈ [0, 1]; ➃ Bregman divergences [5, Exercises
2.3.29 and 2.3.30] provided that the generator F satisfies ∇
2 F(y) + ∇
3 F(y)(y −
x) (∇
2 F(x)∇
2 F)
−1
(y) where denotes the Löwner ordering of positive-definite
matrices. ➄ A generalized divergence related to Tsallis divergence [63].
A jointly convex function is separately convex but the converse is false. However,
a separately convex bivariate function that is positively homogeneous of degree one is
jointly convex (but this result does not hold in higher dimensions; [10]). Conversely,
CROT yields a lower bound for jointly concave distances (e.g., fidelity in quantum
computing; [46]).
8.3 SCROT: Fast Sinkhorn CROT
Consider two finite statistical mixtures m 1 (x) =
k 1
i=1 α i p i (x) and m 2 (x) =
k 2
i=1 β i q i (x), not necessarily homogeneous nor of the same type. Let [k]:=
{1, . . . , k}. The MCOT distance proposed by [33] amounts to solve a Linear Program
(LP) problem.
By defining U (α, β) to be set of non-negative matrices W = [w i j ] with
k 2
l=1 w il = α i and
k 1
l=1 w l j = β j (transport polytope; [8]), we get the equivalent
compact definition of MCOT (that is a special case of CROT):
H D (m 1 , m 2 ) = min
W ∈U (α,β)
k 1
i=1
k 2
j=1
w i j D( p i , q j ).
(8.5)
In general, the LP problem (with k 1 × k 2 variables and inequalities, k 1 + k 2 equalities
whom k 1 + k 2 − 1 are independent) delivers an optimal soft assignment of mixture
components with exactly k 1 + k 2 − 1 nonzero coefficients
1 in matrix W = [w i j ]. The
complexity of linear programming [31] in n variables with b bits using Karmarkar’s
interior point methods is polynomial, in O(n
7
2 b
2
).
Observe that we necessarily have: max j∈[k 2 ] w i j ≥
α i
k 2
, and similarly that:
max i∈[k 1 ] w i j ≥
β j
k 1
. Note that H (m, m) = 0 since w i j = D i j where D i j denotes the
Krönecker symbol: D i j = 1 iff i = j, and 0 otherwise. We can interpret MCOT as
a Discrete Optimal Transport (DOT) between (non-embedded) histograms. When
k 1 = k 2 = d, the transport polytope is the polyhedral set of non-negative d × d matrices:
U (α, β) = {P ∈ R
d×d
+
: P1 d = α, P
1 d = β},
1 A LP in d-dimensions has its solution located at a vertex of a polytope, described by the intersection
of d + 1 hyperplanes (linear constraints).