TY - GEN

T1 - Strong recovery of geometric planted matchings

AU - Kunisky, Dmitriy

AU - Niles-Weed, Jonathan

N1 - Publisher Copyright:
Copyright c 2022 by SIAM Unauthorized reproduction of this article is prohibited.

PY - 2022

Y1 - 2022

N2 - We study the problem of efficiently recovering the matching between an unlabelled collection of n points in Rd 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 covariance 2Id. 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 2 (0; 1). These results extend a recent line of work on recovering matchings planted in random graphs with independently-weighted edges to the geometric setting. 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.

AB - We study the problem of efficiently recovering the matching between an unlabelled collection of n points in Rd 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 covariance 2Id. 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 2 (0; 1). These results extend a recent line of work on recovering matchings planted in random graphs with independently-weighted edges to the geometric setting. 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.

UR - http://www.scopus.com/inward/record.url?scp=85126146496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126146496&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85126146496

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 834

EP - 876

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -