Return to Colloquia & Seminar listing
Strong recovery of geometric planted matchings
ProbabilitySpeaker: | Jonathan Niles-Weed, NYU |
Location: | MSB 2112 |
Start time: | 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).