Talk:Earth mover's distance

Latest comment: 2 years ago by 87.123.205.58 in topic Detail in Theory section

Wasserstein metric

edit

It seems that the EMD is very similar, if not identical, to the Wasserstein metric. Perhaps the two articles should be merged?

Note however that the EMD is typically used for distributions over a discrete region M (e.g. the bins of a histogram, or the pixels of an image), so the "dirt moving plan" is a matrix rather than a 2D continuous distribution. Also, in many applications of the EMD, one must allow for "dirt" to be created or destroyed (at a specified penalty cost), rather than transported. Is that reason enough to keep the articles separate? --Jorge Stolfi (talk) 19:19, 28 October 2008 (UTC)Reply

From my understanding, I would say that both Wasserstein metric and Earth mover's distance (section) are the same mathematical idea. Then, I am not absolutely certain but I think it was Kantorovich who introduced first the continuous version of this metric. --Joannes Vermorel (talk) 23:00, 8 February 2009 (UTC)Reply

The biggest reason for not merging that I can think of is that they seem to serve different audiences: this article seems to serve a comp-sci audience that wants a practical, usable definition suitable for discrete spaces; the Wasserstein metric serves mathematicians who are going to want precise, formal definitions, using the standard notation and definitions of measure theory and metric spaces (which may be unreadable to many comp-sci folks who do not have the formal training in these topics). linas (talk) 16:37, 22 July 2012 (UTC)Reply

Gaspard Monge

edit

This distance has been first introduced by Gaspard Monge in Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Science. Année 1781, avec les Mémoires de Mathématique et de Physique.--Joannes Vermorel (talk) 14:17, 28 October 2008 (UTC)Reply

Physics or computer science?

edit

I changed the wiki project link from "physics" to "Computer science" because, as far as I know, it is not related to physics despite its name, but it is a mathematical techniques used to compute distance between points in multidimensional space.

I choose the computer science project since it appear to be the one where the concept is used but perhaps mathematics could be better. G.Dupont 13:27, 22 August 2007 (UTC)Reply


Hungarian Algorithm

edit

The Hungarian algorithm is used for the assignment problem only, not the more general transportation problem. If someone else agrees, please remove the link to the Hungarian Algorithm 129.10.245.173 (talk) 22:33, 15 December 2010 (UTC)Reply

1D Case

edit

The article states only that "In particular, if D is a one-dimensional array of "bins" the EMD can be efficiently computed by scanning the array and keeping track of how much dirt needs to be transported between consecutive bins." It is actually not obvious how that works, and there are no links to sources explaining it in more detail. It would be good if this could be expanded so much, that it becomes understandable.Rubybrian (talk) 08:12, 27 October 2011 (UTC)Reply

Actually, without being able to give a rigorous proof of the top of my head, it seems to me that in the 1D case with equal sized bins this distance can be computed as sum(abs(cumsum(h1-h2))), because cumsum(h1-h2) tells us for each bin how much earth has to be passed through each bin, where the sign tells us if it will be moved in from the left or right. Is this correct, and if yes, do you think that we should include it in the main page?

Rubybrian (talk) 09:15, 27 October 2011 (UTC)Reply

Even more basic: What are "A" and "B" in the pseudocode? -- 216.137.29.122 (talk) 18:41, 25 March 2014 (UTC)Reply

Theory section seems to be plagiarized

edit

The Theory section seems to be plagiarized from [1]. J. Finkelstein (talk) 15:30, 11 October 2016 (UTC)Reply

Detail in Theory section

edit

It seems to me that constraint 2,   is equivalent to   given constraint 4. (And ditto with constraint 3.) If this is correct, I think writing   is quite confusing. Am I missing something? --87.123.205.58 (talk) 16:31, 13 June 2022 (UTC)Reply