Couple two spaces that have no common ground metric

Ordinary transport needs a cost between a point of one space and a point of the other. When the two live in different spaces – a graph and a point cloud, say – no such cost exists, and the only thing that can be compared is the pattern of within-space distances. The resulting objective is quadratic in the plan, so it is minimised by repeatedly linearising it and running Sinkhorn on the linearisation.

Usage

Otgws(Cx, Cy, a, b, epsilon, max_iter = 20, inner_iter = 200)

Arguments

Cx

Within-space distances of the first space, n by n, symmetric.

Cy

Within-space distances of the second space, m by m.

a, b

Marginals.

epsilon

Entropic strength, positive.

max_iter

Outer linearisations.

inner_iter

Sinkhorn sweeps per linearisation.

Value

List with T, cost, GW, n, m, iters.

Details

The Gromov objective is not convex, so what the iteration returns is a stationary point. When the two spaces share a symmetry and the plan is started at \( b'\), which is itself symmetric, the iteration cannot break the tie and settles on the symmetric average of the two optima rather than on either of them.

Formula: min_T sum_ijkl |Cx_ik - Cy_jl|^2 T_ij T_kl - eps H(T), solved by T^{l+1} = argmin <T, -Cx T^l Cy> - eps H(T) – Peyre and Cuturi (2019) eq. (10.27)-(10.28), p. 176; Peyre, Cuturi and Solomon (2016)

References

Peyre, G., Cuturi, M. and Solomon, J. (2016). Proceedings of Machine Learning Research 48:2664-2672 (ICML).

Examples

Cx <- as.matrix(dist(1:3)); Cy <- as.matrix(dist(c(10, 11, 12)))
r <- Otgws(Cx, Cy, a = rep(1 / 3, 3), b = rep(1 / 3, 3), epsilon = 0.05)
round(r$T, 3)   # the identity coupling: same pattern of distances
#>       [,1]  [,2]  [,3]
#> [1,] 0.162 0.010 0.162
#> [2,] 0.010 0.314 0.010
#> [3,] 0.162 0.010 0.162