Barycenter (version 1.3.1)

Sinkhorn: Sinkhorn Distances (upper bound to EMD)

Description

The Sinkhorn algorithm to compute \(N\) dual-Sinkhorn divergences, i.e. upper bounds on the earth movers distance (EMD), a.k.a. Wasserstein distance.

Usage

Sinkhorn(a, b, costm, lambda = 1, maxIter = 10000, tolerance=10^(-8))

Arguments

a

Either a \(d_1 x 1\) column vector in the probability simplex (nonnegative summing to one) or a \(d_1 x N\) matrix, where each column is in the probability simplex.

b

A \(d_1 x N\) matrix of \(N\) vectors in the probability simplex.

costm

A matrix of pairwise distances/costs between bins described in a and bins in the \(b_1\),...,\(b_N\) histograms.

lambda

Non-negative regularization parameter (for small lambda the Sinkhorn Distance is close to the EMD).

maxIter

Maximum number of iterations.

tolerance

A threshold for the integrated stopping criterion based on marginal differences.

Value

Returns the Sinkhorn Distances between the given bins. If a is given by a \(d_1 x 1\) column vector the function returns the distances $$[D(a,b_1),...,D(a,b_N)].$$ If a is given by a \(d_1 x N\) matrix the function returns the distances $$[D(a_1,b_1),...,D(a_N,b_N)].$$ If a and b are simply given by two \(d_1 x 1\) and \(d_2 x 1\) vectors each in the probability simplex, respectively, then the functions returns a list containing the Sinkhorn Distance as well as the corresponding regularized transport plan.

References

Cuturi, M.: Sinkhorn Distances: Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems 26, 2013

Examples

# NOT RUN {
#Sinkhorn Distances between the first image to the remaining four images in the dataset eight.
#We creat costm simply using a distance matrix on the grid [0,1]x[0,1].
n <- seq(0,1,length.out = dim(eight[[1]])[2])
costm <- as.matrix(dist(expand.grid(n,rev(n)), diag=TRUE, upper=TRUE))
a <- matrix(eight[[1]],28*28,1)
b <- matrix(c(eight[[2]],eight[[3]],eight[[4]],eight[[5]]),28*28,4)
Sinkhorn(a, b, costm)
# }