transport (version 0.15-4)

shielding: 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
)

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

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.

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

Bernhard Schmitzer and
Dominic Schuhmacher
(based on C++ code by Bernhard Schmitzer)

Details

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

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

if (FALSE) {
shielding(random64a$mass,random64b$mass,nscales=6,measureScale=1) }