[2402.15095] The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime

Mathematics > Statistics Theory arXiv:2402.15095 (math) [Submitted on 23 Feb 2024 (v1), last revised 7 Apr 2026 (this version, v2)] Title:The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime Authors:Shuyang Gong, Zhangsong Li View a PDF of the paper titled The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime, by Shuyang Gong and Zhangsong Li View PDF HTML (experimental) Abstract: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 $\p...