Random Matching Between Distinct Distributions in Two Dimensions

Source abstract

Given two independent $n$-point samples drawn from possibly distinct probability distributions on a compact 2-dimensional surface, we minimize the total squared distance over all perfect bipartite matchings. Under regularity assumptions, the expected matching cost minus $n$ times the squared 2-Wasserstein distance between the sampling distributions grows logarithmically with $n$. We determine this difference up to an additive $o(1)$ error, including the dependence of the logarithmic coefficient and constant term on geometry and sampling distributions, and establish the existence of a universal constant shared by these formulas. Our analysis expresses the expected matching cost in terms of the cost of transporting a heat-smoothed sample back to its original points. The reductions giving this relation hold in every dimension and for general costs under suitable assumptions, with consequences beyond the setting studied here. In two dimensions, the relation is exact up to an additive $o(1)$ error, so determining the matching cost amounts to evaluating the smoothing cost with the same accuracy. We obtain this evaluation by subdividing the domain and exploiting cancellations between the sample and its own smoothing.