An extension of the angular synchronization problem to the heterogeneous setting

DOI10.3934/FODS.2021036zbMATH Open1491.60013arXiv2012.14932OpenAlexW3116734197MaRDI QIDQ2148952FDOQ2148952

Publication date: 24 June 2022

Published in: Foundations of Data Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2012.14932

Recommendations

zbMATH Keywords

matrix perturbation theory random matrix theory singular value decomposition group synchronization spectral algorithms

Mathematics Subject Classification ID

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)

Cites Work

Cited In (4)

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)