Strong recovery of geometric planted matchings
Strong recovery of geometric planted matchings
复制标题
DOI：
10.1137/1.9781611977073.36
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Dmitriy Kunisky;Jonathan Niles-Weed
中科院分区：
文献类型：
--
作者：
Dmitriy Kunisky;Jonathan Niles-Weed
我们研究的问题，有效地恢复$n$点在$\mathbb{R}^d$和一个小的随机扰动，这些点之间的匹配未标记的集合。我们考虑一个初始点是独立同分布的模型。标准高斯向量，通过添加i.i.d.方差为$\sigma^2$的高斯向量。在这种情况下，最大似然估计（MLE）可以在多项式时间内找到线性分配问题的解决方案。我们在$\sigma^2 $上为MLE建立阈值，以完美地恢复种植匹配（没有错误），并在$d$恒定和$d = d（n）$任意增长的情况下强烈恢复种植匹配（使$o（n）$错误）。在这两个阈值之间，我们证明了MLE对于显式$\delta \in（0，1）$产生$n^{\delta + o（1）}$错误。这些结果扩展到几何设置最近的工作线恢复匹配种植在随机图与独立加权边缘。我们的证明技术依赖于仔细分析的组合结构的部分匹配在大型，弱相关的随机图使用的第一和第二时刻的方法。
We study the problem of efficiently recovering the matching between an unlabelled collection of $n$ points in $\mathbb{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 $\sigma^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 $\sigma^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^{\delta + o(1)}$ errors for an explicit $\delta \in (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.