Motivated by the problem of matching two correlated random geometric graphs,
we study the problem of matching two Gaussian geometric models correlated
through a latent node permutation. Specifically, given an unknown permutation
$\pi^*$ on $\{1,\ldots,n\}$ and given $n$ i.i.d. pairs of correlated Gaussian
vectors $\{X_{\pi^*(i)},Y_i\}$ in $\mathbb{R}^d$ with noise parameter $\sigma$,
we consider two types of (correlated) weighted complete graphs with edge
weights given by $A_{i,j}=\langle X_i,X_j \rangle$, $B_{i,j}=\langle Y_i,Y_j
\rangle$. The goal is to recover the hidden vertex correspondence $\pi^*$ based
on the observed matrices $A$ and $B$. For the low-dimensional regime where
$d=O(\log n)$, Wang, Wu, Xu, and Yolou [WWXY22+] established the information
thresholds for exact and almost exact recovery in matching correlated Gaussian
geometric models. They also conducted numerical experiments for the classical
Umeyama algorithm. In our work, we prove that this algorithm achieves exact
recovery of $\pi^*$ when the noise parameter $\sigma=o(d^{-3}n^{-2/d})$, and
almost exact recovery when $\sigma=o(d^{-3}n^{-1/d})$. Our results approach the
information thresholds up to a $\operatorname{poly}(d)$ factor in the
low-dimensional regime.

通过研究匹配两个相关的随机几何图的问题，我们研究了通过潜在节点排列相互关联的两个高斯几何模型的匹配问题。我们证明了在低维情况下，当噪声参数小于等于 O (d^-3 * n^-2/d) 时，Umeyama 算法能够准确恢复隐藏的顶点对应关系 π*，当噪声参数小于等于 O (d^-3 * n^-1/d) 时，能够实现几乎准确恢复。我们的结果接近了低维情况下的信息门限，只有一个 poly (d) 的因子差异。