gromov hausdorff

Source: R/gromov_hausdorff.R

This function implements the discrete, extended version of gromov hausdorff distance proposed by Memoli in section 7 of (1) for comparing two measure-metric spaces.

gromov_hausdorff(d_X, d_Y, mu_X, mu_Y, p = 1, flb_solver = "glpk",
  flb_only = TRUE, options = list(localsolver = "COBYLA", localtol =
  1e-07), control = list(maxeval = 300), return_optimizer = FALSE)

Arguments

d_X

either a dist object, or (n x n) numeric metric distance matrix over X.
d_Y

either a dist object, or (m x m) numeric metric distance matrix over Y.
mu_X

(n-length) numeric vector giving the probability measure at each point of X.
mu_Y

(m-length) numeric vector giving the probability measure at each point of Y.
p

The norm to compute.
flb_solver

Which LOP ROI plugin solver to use to solve the lower bound approximation.
flb_only

If only crude approximation is needed, the lower bound can be returned. See details.
options

Options to auglag. Ignored if flb_only=TRUE.
control

Control options to pass auglag's control.
return_optimizer

Whether to return the optimizer, or just the results.

Value

If flb_only is set to TRUE, a list with components:

  • gh The gromov-wasserstein distance.

  • mu The result of the optimization.

  • correspondences A surjective matching from X to Y and from Y to X.

If flb_only is set to FALSE, a list of both the LOP and QOP optimization results are returned in the above format.

NOTE: The quadratic optimization problem (QOP) is non-convex, and requires solving for (n^2 x m^2) variables, which may be very computationally expensive to run. The FLB is an LOP of the same size.

Details

This function provides an implementation of the computational objective (Pp) listed in Section 7 of (1), which calculates an Lp approximition of Gromov-Hausdorff (i.e. wasserstein relaxation) distance between two measure-metric spaces. The first lower bound (FLB) is first computed via an LOP, and then the solution is used as the initialization point for the corresponding quadratic optimization routine. This code utilizes the R Optimization Infrastructure (ROI), and relies on having available at least one plugin available for to solve the initial lower bound (a linear program). If more than the lower bound is requested, the optimization is cast as a generic nonlinear optimization.

References

1. Mémoli, Facundo. "On the use of Gromov-Hausdorff distances for shape comparison." (2007).