We present a new Linear Programming model that formulates the problem of computing the Kantorovich-Wasserstein distance associated with a truncated ground distance. The key idea of our model is to consider only the quantity of mass that is transported to nearby points and to ignore the quantity of mass that should be transported between faraway pairs of locations. The proposed model has a number of variables that depends on the threshold value used in the definition of the set of nearby points. Using a small threshold value, we can obtain a significant speedup. We use our model to numerically evaluate the percentage gap between the true Wasserstein distance and the truncated Wasserstein distance, using a set of standard grey scale images.
The Maximum Nearby Flow Problem
Auricchio, Gennaro;Gualandi, Stefano;Veneroni, Marco
2019-01-01
Abstract
We present a new Linear Programming model that formulates the problem of computing the Kantorovich-Wasserstein distance associated with a truncated ground distance. The key idea of our model is to consider only the quantity of mass that is transported to nearby points and to ignore the quantity of mass that should be transported between faraway pairs of locations. The proposed model has a number of variables that depends on the threshold value used in the definition of the set of nearby points. Using a small threshold value, we can obtain a significant speedup. We use our model to numerically evaluate the percentage gap between the true Wasserstein distance and the truncated Wasserstein distance, using a set of standard grey scale images.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
