Strong recovery of geometric planted matchings

We study the problem of efficiently recovering the matching between an unlabelled collection of n points in R d and a small random perturbation of those points. We consider a model where the initial points are i.i.d. standard Gaussian vectors, perturbed by adding i.i.d. Gaussian vectors with variance σ 2 . In this setting, the maximum likelihood estimator (MLE) can be found in polynomial time as the solution of a linear assignment problem. We establish thresholds on σ 2 for the MLE to perfectly recover the planted matching (making no errors) and to strongly recover the planted matching (making o(n) errors) both for d constant and d = d(n) growing arbitrarily. Between these two thresholds, we show that the MLE makes n δ+o(1) errors for an explicit δ ∈ (0, 1). These results extend to the geometric setting a recent line of work on recovering matchings planted in random graphs with independently-weighted edges. Our proof techniques rely on careful analysis of the combinatorial structure of partial matchings in large, weakly dependent random graphs using the first and second moment methods.