Alternate KL projections of a Gibbs kernel onto the two marginals

Entropic transport is a Bregman projection: the regularised plan is the KL-projection of K = exp(-C/eps) onto the transport polytope (eq. 4.7), and the polytope is the intersection of two affine sets, so alternating projections converge to it. Projecting on the rows means rescaling each row to sum to a; on the columns, to b.

Usage

Otbreg(K, a, b, max_iter = 200)

Arguments

K

Gibbs kernel, n by m, entrywise positive.

a

Row marginal.

b

Column marginal.

max_iter

Number of row/column sweeps; fixed, not tolerance-driven.

Value

List with T, iters, row_err, col_err, n, m.

Details

Formula: T <- diag(a / (T 1)) T then \(T <- T diag(b / (T' 1))\), repeated – Benamou et al. (2015) eq. (5)-(6); Peyre and Cuturi (2019) eq. (4.6)-(4.7).

References

Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L. and Peyre, G. (2015). SIAM Journal on Scientific Computing 37(2):A1111-A1138. doi:10.1137/141000439 .

Examples

Otbreg(K = c(1, 2, 3, 4, 5, 6, 7, 8), a = c(1, 2, 3, 4, 5, 6, 7, 8), b = 5L)
#> $T
#>           [,1]
#> [1,] 0.1388889
#> [2,] 0.2777778
#> [3,] 0.4166667
#> [4,] 0.5555556
#> [5,] 0.6944444
#> [6,] 0.8333333
#> [7,] 0.9722222
#> [8,] 1.1111111
#> 
#> $iters
#> [1] 200
#> 
#> $row_err
#> [1] 6.888889
#> 
#> $col_err
#> [1] 0
#> 
#> $n
#> [1] 8
#> 
#> $m
#> [1] 1
#> 
#> $method
#> [1] "Iterative Bregman projections"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"