shielding: Compute Optimal Transport (Cost/Plan) Using the Multiscale...

In transport: Computation of Optimal Transport Plans and Wasserstein Distances

Compute Optimal Transport (Cost/Plan) Using the Multiscale Shielding Method

Description

Runs the multiscale version of the Shielding Method (a.k.a. Short Cut Method) for computing the optimal transport (cost/plan) on a rectangular grid in d dimensions for the squared Euclidean distance as cost function.

Usage

shielding(
  a,
  b,
  nscales = 2,
  startscale = 1,
  flood = 0,
  measureScale = 1e-06,
  verbose = FALSE,
  basisKeep = 1,
  basisRefine = 1
)

Arguments

a, b	arrays with d coordinates representing source and target measure, respectively. The entries must be all positive.
nscales	the number of scales generated in the multiscale algorithm.
startscale	the first scale on which the problem is solved.
flood	a real number. If positive, take the maximum of entry and flood for each entry of a and b.
measureScale	the required precision for the entries. Computations are performed on round(a/measureScale) and the same for b using integer arithmetics.
verbose	logical. Toggles output to the console about the progress of the algorithm.
basisKeep, basisRefine	internal use only.

Details

If a and b do not have the same sum, they are normalized to sum 1 before flood and measureScale transformations are applied.

Value

A list of components

err	error code. 0 if everything is ok.
a_used, b_used	the vectorized arrays that were actually used by the algorithm. a, b after applying flood and measureScale.
coupling	a vectorized coupling describing the optimal transport from a_used to b_used
basis	a matrix with two columns describing the basis obtained for the optimal transport
u, v	vectors of optimal values in the dual problem

Use of CPLEX

For larger problems (thousands of grid points) there are considerable speed improvements when shielding can use the CPLEX numerical solver for the underlying constrained optimization problems. If a local installation of CPLEX is available, the transport package can be linked against it during installation. See the file src/Makevars in the source package for instructions.

Author(s)

Bernhard Schmitzer [e-mail] and
Dominic Schuhmacher [e-mail]
(based on C++ code by Bernhard Schmitzer)

References

B. Schmitzer (2016). A sparse multiscale algorithm for dense optimal transport. J. Math. Imaging Vision 56(2), 238–259. https://arxiv.org/abs/1510.05466

See Also

transport, which calls this function if appropriate.

Examples

## Not run: 
shielding(random64a$mass,random64b$mass,nscales=6,measureScale=1) 
## End(Not run)

transport documentation built on Sept. 17, 2024, 1:08 a.m.