An extension of the angular synchronization problem to the heterogeneous setting

Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57) Random matrices (probabilistic aspects) (60B20) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: Given an undirected measurement graph

G = ([n], E)

, the classical angular synchronization problem consists of recovering unknown angles

h e t a_{1}, d o t s, h e t a_{n}

from a collection of noisy pairwise measurements of the form

(h e t a_{i} - h e t a_{j}) m o d 2 p i

, for each

i, j i n 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

h e t a_{l, 1}, d o t s, h e t a_{l, n}

, for

l = 1, d o t s, k

. For each

i, j i n E

, we are given noisy pairwise measurements of the form

h e t a_{e l l, i} - h e t a_{e l l, j}

for an unknown

e l l i n 1, 2, l d o t s, 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} c u p G_{2} l d o t s c u p 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, l d o t s, k

which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: An extension of the angular synchronization problem to the heterogeneous setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2148952)