# An extension of the angular synchronization problem to the heterogeneous setting

arXiv: https://arxiv.org/abs/2012.14932 · HTML: https://mlsanity.com/paper/2012.14932/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [Robust Angular Synchronization via Directed Graph Neural Networks](https://mlsanity.com/paper/2310.05842/) (2023)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)

## Abstract (arXiv)

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 ∈ 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 ∈ E, we are given noisy pairwise measurements of the form θℓ,i - θℓ,j for an unknown ℓ ∈ 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 = G1 cup G2 ldots cup Gk, where the Gi'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 Gi, i=1,ldots,k which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.