# On the Definiteness of Earth Mover's Distance and Its Relation to Set Intersection

arXiv: https://arxiv.org/abs/1510.02833 · HTML: https://mlsanity.com/paper/1510.02833/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2015.

## Built on by (most cited first, 4 of 4)

- [Digger: Detecting Copyright Content Mis-usage in Large Language Model Training](https://mlsanity.com/paper/2401.00676/) (2024)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [A distance for mixed-variable and hierarchical domains with meta variables](https://mlsanity.com/paper/2405.13073/) (2024)
- [Modeling Hierarchical Spaces: A Review and Unified Framework for Surrogate-Based Architecture Design](https://mlsanity.com/paper/2506.22621/) (2025)

## Abstract (arXiv)

Positive definite kernels are an important tool in machine learning that enable efficient solutions to otherwise difficult or intractable problems by implicitly linearizing the problem geometry. In this paper we develop a set-theoretic interpretation of the Earth Mover's Distance (EMD) and propose Earth Mover's Intersection (EMI), a positive definite analog to EMD for sets of different sizes. We provide conditions under which EMD or certain approximations to EMD are negative definite. We also present a positive-definite-preserving transformation that can be applied to any kernel and can also be used to derive positive definite EMD-based kernels and show that the Jaccard index is simply the result of this transformation. Finally, we evaluate kernels based on EMI and the proposed transformation versus EMD in various computer vision tasks and show that EMD is generally inferior even with indefinite kernel techniques.