8 Chain Rule Optimal Transport
197
and
H D (m 1 : m 2 ) = min
P∈U (α,β)
P, W ,
where A, B = tr(A
B) is the Fröbenius inner product of matrices, and tr(A) the
matrix trace. This OT can be calculated using the network simplex in O(d
3 log d)
time. Cuturi [8] showed how to relax the objective function in order to get fast
calculation using the Sinkhorn divergence:
S D (m 1 : m 2 ) = min
P∈U λ (α,β)
P, W ,
(8.6)
where
U λ (α, β):={P ∈ U (α, β) : KL(P : αβ
) ≤ λ}.
The KLD between two k × k matrices M = [m i, j ] and M
= [m
i, j ] is defined by
KL(M : M
) :=
i, j
m i, j log
m i, j
m
i, j
,
with the convention that 0 log
0
0
= 0. The Sinkhorn divergence is calculated using
the equivalent dual Sinkhorn divergence by using matrix scaling algorithms (e.g., the
Sinkhorn–Knopp algorithm). Because the minimization is performed on U λ (α, β) ⊂
U (α, β), we have
H D (m 1 , m 2 ) ≤ S D (m 1 , m 2 ).
Notice that the smooth (dual) Sinkhorn divergence has also been shown experimentally to improve over the EMD in applications (MNIST classification; [8]).
8.3.1 CROT Upper Bounds on Distance Between Statistical
Mixtures
First, let us report the basic upper bounds for MCOT mentioned earlier in Property 8.3.
The objective function is upper bounded by:
H (m 1 , m 2 ) ≤
k 1
i=1
k 2
j=1
α i β j D( p i , q j ) ≤ max
i∈[k 1 ], j∈[k 2 ]
D( p i , q j ).
(8.7)
Now, when the conditional density distance D is separate convex (i.e., meaning
convex in both arguments), we get the following Separate Convexity Upper Bound:
197
and
H D (m 1 : m 2 ) = min
P∈U (α,β)
P, W ,
where A, B = tr(A
B) is the Fröbenius inner product of matrices, and tr(A) the
matrix trace. This OT can be calculated using the network simplex in O(d
3 log d)
time. Cuturi [8] showed how to relax the objective function in order to get fast
calculation using the Sinkhorn divergence:
S D (m 1 : m 2 ) = min
P∈U λ (α,β)
P, W ,
(8.6)
where
U λ (α, β):={P ∈ U (α, β) : KL(P : αβ
) ≤ λ}.
The KLD between two k × k matrices M = [m i, j ] and M
= [m
i, j ] is defined by
KL(M : M
) :=
i, j
m i, j log
m i, j
m
i, j
,
with the convention that 0 log
0
0
= 0. The Sinkhorn divergence is calculated using
the equivalent dual Sinkhorn divergence by using matrix scaling algorithms (e.g., the
Sinkhorn–Knopp algorithm). Because the minimization is performed on U λ (α, β) ⊂
U (α, β), we have
H D (m 1 , m 2 ) ≤ S D (m 1 , m 2 ).
Notice that the smooth (dual) Sinkhorn divergence has also been shown experimentally to improve over the EMD in applications (MNIST classification; [8]).
8.3.1 CROT Upper Bounds on Distance Between Statistical
Mixtures
First, let us report the basic upper bounds for MCOT mentioned earlier in Property 8.3.
The objective function is upper bounded by:
H (m 1 , m 2 ) ≤
k 1
i=1
k 2
j=1
α i β j D( p i , q j ) ≤ max
i∈[k 1 ], j∈[k 2 ]
D( p i , q j ).
(8.7)
Now, when the conditional density distance D is separate convex (i.e., meaning
convex in both arguments), we get the following Separate Convexity Upper Bound: