How can one compute the "average" of a dataset of histograms that minimizes the mean Earth Mover's Distance between all data points and average?

Question

It is my understanding that when the distance metric is euclidean distance, the mean of a dataset minimizes the average distance between all data points and the computed "mean".

In the case of Earth Movers Distance for discrete distributions, how would one compute a "mean" such that the average EMD distance between this "mean" and all of the histograms in the dataset is minimized? How would such an average distance minimizing formula be derived in general for a given distance function?

The application is for a K-means clustering task. Existing approaches only use averaging as an update rule for the new centroid even when using an unusual distance function for which a straightforward mean will not minimize average distance to the centroid. Our group believes using this approach for updating cluster centroids will improve the quality of our cluster generation.

Answer 1

I think what you discribed is the Wasserstein Barycenter.

There is plenty of literature about the Wasserstein barycenter, including fast ways to compute it, (you could specify it’s the Wasserstein-1 distance you’re interested in, since it’s easier to compute than the general Wasserstein distance) and about its use for clustering.