METRIC-PRESERVING REDUCTION OF EARTH MOVER'S DISTANCE

Yuichi Takano () and Yoshitsugu Yamamoto ()
Additional contact information
Yuichi Takano: Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan
Yoshitsugu Yamamoto: Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 01, 39-54

Abstract: Earth mover's distance (EMD for short) is a perceptually meaningful dissimilarity measure between histograms. The computation of EMD reduces to a network flow optimization problem; however, it lays a heavy computational burden when the number of locations of histograms is large. In this paper, we address an efficient formulation for computing the exact EMD value. We prove that the EMD problem reduces to a problem with half the number of constraints regardless of the ground distance. We then propose a further reduced formula in which the number of variables is reduced fromO(m2)toO(m)for histograms withmlocations when the ground distance is derived from a graph with a homogeneous neighborhood structure. Specifically, EMD problems withL1,L∞andD-norm ground distances can be reduced in this manner. Some experiments show that the reduction helps compute the EMD efficiently.

Keywords: Earth mover's distance; transportation problem of Hitchcock type; flow decomposition; histogram-based dissimilarity measure; non-negative matrix factorization (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595910002545
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:27:y:2010:i:01:n:s0217595910002545

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002545

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().