Greenkhorn: Greenkhorn Distances (approximation to EMD)

In Barycenter: Regularized Wasserstein Distances and Barycenters

Description

The Greenkhorn algorithm to approximate the earth movers distance (EMD), a.k.a. Wasserstein distance, between two probability vectors r and c with specified cost-matrix costm.

Usage

Greenkhorn(r, c, costm, lambda = 1, maxIter = 10000, tolerance=10^(-8))

Arguments

r	(n x 1) row vector in the probability simplex (nonnegative summing to one).
c	(1 x m) row vector in the probability simplex (nonnegative summing to one).
costm	(n x m) matrix of pairwise distances/costs between bins with mass described by r and bins with mass described by c.
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 a list containing the regularized transport plan represented as a n x m matrix as well as the Sinkhorn distance between the given marginals r and c.

Author(s)

Marcel Klatt

References

Altschuler, J., Weed, J. and Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Advances in Neural Information Processing Systems 30 (NIPS 2017)

Examples

#Sinkhorn Distances between the first image to the second image 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))
r <- matrix(eight[[1]],28*28,1)
c <- matrix(eight[[2]],1,28*28)
Greenkhorn(r, c, costm)$Distance

Example output

Loading required package: Rcpp
[1] 0.2945937

Barycenter documentation built on May 2, 2019, 6:47 a.m.