Exact earth mover's distance between two histograms

The linear program is solved outright, not smoothed: the answer is the true optimum of the Kantorovich problem rather than an entropic relaxation of it. The plan returned is a vertex of the transport polytope, so at most n + m - 1 of its entries are non-zero.

Usage

Otemd(a, b, C)

Arguments

a

Source weights, length n, non-negative.

b

Target weights, length m, same total mass as a.

C

Ground cost, n by m.

Value

List with T, cost, n, m, n_basic.

Details

Formula: min_T <T, C> subject to T 1 = a, \(T' 1 = b\), T >= 0 – Kantorovich's problem, eq. (2.11) of Peyre and Cuturi (2019). Solved by the transportation simplex: north-west-corner start, potentials from the basis tree, MODI pivoting.

References

Rubner, Y., Tomasi, C. and Guibas, L. J. (2000). International Journal of Computer Vision 40(2):99-121. doi:10.1023/A:1026543900054 . Peyre and Cuturi (2019), Computational Optimal Transport, eq. (2.11).

Examples

Otemd(a = c(1, 2, 3, 4, 5, 6, 7, 8), b = c(1, 2, 3, 4, 5, 6, 7, 8), C = c(1, 2, 3, 4, 5, 6, 7, 8))
#> $T
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    0    0    0    0    0    0    0
#> [2,]    0    2    0    0    0    0    0    0
#> [3,]    0    0    3    0    0    0    0    0
#> [4,]    0    0    0    4    0    0    0    0
#> [5,]    0    0    0    0    5    0    0    0
#> [6,]    0    0    0    0    0    6    0    0
#> [7,]    0    0    0    0    0    0    7    0
#> [8,]    0    0    0    0    0    0    0    8
#> 
#> $cost
#> [1] 204
#> 
#> $n
#> [1] 8
#> 
#> $m
#> [1] 8
#> 
#> $n_basic
#> [1] 8
#> 
#> $method
#> [1] "Exact optimal transport (transportation simplex)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"