An extension of the angular synchronization problem to the heterogeneous setting

Given an undirected measurement graph \begin{document}$ G = ([n], E) $\end{document} , the classical angular synchronization problem consists of recovering unknown angles \begin{document}$ \theta_1, \dots, \theta_n $\end{document} from a collection of noisy pairwise measurements of the form \begin{document}$ (\theta_i - \theta_j) \mod 2\pi $\end{document} , for each \begin{document}$ \{i, j\} \in E $\end{document} . 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 \begin{document}$ k $\end{document} unknown groups of angles \begin{document}$ \theta_{l, 1}, \dots, \theta_{l, n} $\end{document} , for \begin{document}$ l = 1, \dots, k $\end{document} . For each \begin{document}$ {\left\{{{i, j}}\right\}} \in E $\end{document} , we are given noisy pairwise measurements of the form \begin{document}$ \theta_{\ell, i} - \theta_{\ell, j} $\end{document} for an unknown \begin{document}$ \ell \in \{1, 2, \ldots, k\} $\end{document} . 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 \begin{document}$ G = G_1 \cup G_2 \ldots \cup G_k $\end{document} , where the \begin{document}$ G_i $\end{document} '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 \begin{document}$ G_i $\end{document} , \begin{document}$ i = 1, \ldots, k $\end{document} which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.