Strong recovery of geometric planted matchingsProbability
|Jonathan Niles-Weed, NYU
|Tue, May 9 2023, 1:10PM
We consider the problem of recovering a hidden matching between two correlated sets of n Gaussian samples in R^d. We analyze the performance of the maximum likelihood estimator, establish thresholds at which the MLE almost perfectly recovers the planted matching, and, in this regime, characterize the number of errors up to sub-polynomial factors. These results extend to the geometric setting a recent line of work on recovering matchings planted in random graphs with independently-weighted edges. Joint work with D. Kunisky (Yale).