Dual potentials of the entropic transport problem

Entropic smoothing turns a constrained linear program into an unconstrained smooth concave maximisation in the two potentials, and that is what makes stochastic and large-scale solvers possible. The potentials are computed in the log domain, so the result survives small epsilon where the exponentiated form underflows.

Usage

Otreg(a, b, C, epsilon, max_iter = 200)

Arguments

a, b

Marginals, equal total mass.

C

Ground cost, n by m.

epsilon

Regularisation strength, positive.

max_iter

Sinkhorn sweeps; fixed count.

Value

List with f, g, dual_value, primal_cost, n, m.

Details

Formula: \(max_{f,g} <a,f> + <b,g> - eps sum_ij exp((f_i + g_j - C_ij)/eps)\) – Genevay et al. (2016) eq. (2); Peyre and Cuturi (2019) eq. (4.30). At the optimum the exponential sum is the total mass, so the dual value reduces to <a,f> + <b,g> - eps.

References

Genevay, A., Cuturi, M., Peyre, G. and Bach, F. (2016). Advances in Neural Information Processing Systems 29:3440-3448.

Examples

Otreg(a = c(1, 2, 3, 4, 5, 6, 7, 8), b = 5L, C = c(1, 2, 3, 4, 5, 6, 7, 8), epsilon = 5L)
#> $f
#> [1] 1965.211 1969.676 1972.704 1975.142 1977.258 1979.169 1980.940 1982.608
#> 
#> $g
#> [1] -1974.081
#> 
#> $dual_value
#> [1] 61316.59
#> 
#> $primal_cost
#> [1] 28.33333
#> 
#> $n
#> [1] 8
#> 
#> $m
#> [1] 1
#> 
#> $method
#> [1] "Entropic optimal transport dual"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"