# 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?

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.

• Not my field, but I beleive earth mover distance is related to transport problems in OR. If you don't get help here maybe ask at or.stackexchange.com Apr 10 at 15:29