论文标题
角度同步问题扩展到异质设置
An extension of the angular synchronization problem to the heterogeneous setting
论文作者
论文摘要
给定一个无方向的测量图$ g =（[n]，e）$，经典的角度同步问题包括恢复未知角度$θ_1，\ dots，tin $，从表单$ $（θ_i -θ_j）的表单$（θ_i -θ_j）\ mod2π$ $ \ $ \ \ for $ \ \ \ for中的noisy成对测量集中。这个问题出现在各种应用程序中，包括计算机视觉，分布式网络的时间同步以及从偏好关系中排名。在本文中，我们考虑到存在$ k $未知组的设置$θ_{l，1}，\ dots，θ_{l，n} $，$ l = 1，\ dots，k $。对于每个$ \ {i，j \} \在e $中，我们得到了$θ_ {\ ell，i} - θ_ {\ ell，j} $的噪声成对测量值，用于未知$ \ ell \ in \ in \ in \ in \ in \ in \ {1,2，\ ldots，k \ \ \ \ \ \} $。可以将其视为角度同步问题的自然扩展到多个角度组的异质设置，其中测量图具有未知的边缘 - 边界分解$ g = g_1 \ cup g_2 \ cup g_2 \ ldots \ cup cup g_k $，其中$ g_i $ $ g_i $ sepote sepote sepote s sub subsgraph of Edges sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sopers sougens sopers sopers sougens。我们为此问题提出了一个概率的生成模型，以及一种频谱算法，我们就对采样稀疏性和噪声的鲁棒性提供了详细的理论分析。理论发现与一组全面的数值实验相辅相成，在各种参数制度下展示了我们算法的功效。最后，我们考虑将双同步化的应用到图形实现问题上，并在迭代图中提供了分开的图形程序，该过程揭示了子图$ g_i $，$ i = 1，\ ldots，k $，k $，k $，这是独立的，因为这表明可以提高所有实验的最终恢复准确性。
Given an undirected measurement graph $G = ([n], E)$, the classical angular synchronization problem consists of recovering unknown angles $θ_1,\dots,θ_n$ from a collection of noisy pairwise measurements of the form $(θ_i - θ_j) \mod 2π$, for each $\{i,j\} \in E$. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from preference relationships. In this paper, we consider a generalization to the setting where there exist $k$ unknown groups of angles $θ_{l,1}, \dots,θ_{l,n}$, for $l=1,\dots,k$. For each $ \{i,j\} \in E$, we are given noisy pairwise measurements of the form $θ_{\ell,i} - θ_{\ell,j}$ for an unknown $\ell \in \{1,2,\ldots,k\}$. This can be thought of as a natural extension of the angular synchronization problem to the heterogeneous setting of multiple groups of angles, where the measurement graph has an unknown edge-disjoint decomposition $G = G_1 \cup G_2 \ldots \cup G_k$, where the $G_i$'s denote the subgraphs of edges corresponding to each group. We propose a probabilistic generative model for this problem, along with a spectral algorithm for which we provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise. The theoretical findings are complemented by a comprehensive set of numerical experiments, showcasing the efficacy of our algorithm under various parameter regimes. Finally, we consider an application of bi-synchronization to the graph realization problem, and provide along the way an iterative graph disentangling procedure that uncovers the subgraphs $G_i$, $i=1,\ldots,k$ which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.
