Transport in a feature space, with the cost read off a kernel

Once the ground cost is the squared distance in a feature space, it never has to be formed there: \(||phi(x) - phi(y)||^2 = k(x,x) + k(y,y) - 2 k(x,y)\), so the kernel alone determines the cost, which is the -2 k(x,y) of the usual shorthand plus the two diagonal terms that keep it non-negative. Dropping them would shift every entry by a row and a column constant, which leaves the optimal plan alone but makes the reported cost meaningless.

Usage

Otker(X, Y, kernel = "gaussian", epsilon = 0.1, gamma = 1, max_iter = 200)

Arguments

X, Y: Two point clouds, given uniform weight.
kernel: Either "gaussian" or "linear".
epsilon: Entropic strength, positive.
gamma: Gaussian bandwidth parameter.
max_iter: Sinkhorn sweeps.

Value

List with EMD_approx, C, exact_cost, n, m.

Details

Formula: C_ij = k(x_i,x_i) + k(y_j,y_j) - 2 k(x_i,y_j), then T by Sinkhorn and EMD_approx = <T, C> – Genevay, Peyre and Cuturi (2018), Section 3.

References

Genevay, A., Peyre, G. and Cuturi, M. (2018). Proceedings of Machine Learning Research 84:1608-1617 (AISTATS).

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Otker(V, V)
#> $EMD_approx
#> [1] 7.174719e-06
#> 
#> $C
#>          [,1]     [,2]     [,3]     [,4]     [,5]     [,6]     [,7]     [,8]
#> [1,] 0.000000 1.264241 1.963369 1.999753 2.000000 2.000000 2.000000 2.000000
#> [2,] 1.264241 0.000000 1.264241 1.963369 1.999753 2.000000 2.000000 2.000000
#> [3,] 1.963369 1.264241 0.000000 1.264241 1.963369 1.999753 2.000000 2.000000
#> [4,] 1.999753 1.963369 1.264241 0.000000 1.264241 1.963369 1.999753 2.000000
#> [5,] 2.000000 1.999753 1.963369 1.264241 0.000000 1.264241 1.963369 1.999753
#> [6,] 2.000000 2.000000 1.999753 1.963369 1.264241 0.000000 1.264241 1.963369
#> [7,] 2.000000 2.000000 2.000000 1.999753 1.963369 1.264241 0.000000 1.264241
#> [8,] 2.000000 2.000000 2.000000 2.000000 1.999753 1.963369 1.264241 0.000000
#> 
#> $exact_cost
#> [1] 0
#> 
#> $n
#> [1] 8
#> 
#> $m
#> [1] 8
#> 
#> $method
#> [1] "Kernel-induced transport cost"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"