An extension of the angular synchronization ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
An extension of the angular synchronization problem to the heterogeneous setting
Auteur(s) :
Cucuringu, Mihai [Auteur]
Department of Statistics [Oxford]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Department of Statistics [Oxford]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Titre de la revue :
Foundations of Data Science
Éditeur :
American Institute of Mathematical Sciences
Date de publication :
2022
Mot(s)-clé(s) en anglais :
group synchronization
spectral algorithms
matrix perturbation theory
singular value decomposition
random matrix theory
spectral algorithms
matrix perturbation theory
singular value decomposition
random matrix theory
Discipline(s) HAL :
Mathématiques [math]/Statistiques [math.ST]
Résumé en anglais : [en]
Given an undirected measurement graph G = ([n], E), the classical angular synchronization problem consists of recovering unknown angles θ1,. .. , θn from a collection of noisy pairwise measurements of the form (θi − θj) ...
Lire la suite >Given an undirected measurement graph G = ([n], E), the classical angular synchronization problem consists of recovering unknown angles θ1,. .. , θ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} ,. .. , θ_{l,n} , for l = 1,. .. , k. For each {i, j} ∈ E, we are given noisy pairwise measurements of the form θ ,i − θ ,j for an unknown ∈ {1, 2,. .. , 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 ∪ G2. .. ∪ G k , 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,. .. , k which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.Lire moins >
Lire la suite >Given an undirected measurement graph G = ([n], E), the classical angular synchronization problem consists of recovering unknown angles θ1,. .. , θ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} ,. .. , θ_{l,n} , for l = 1,. .. , k. For each {i, j} ∈ E, we are given noisy pairwise measurements of the form θ ,i − θ ,j for an unknown ∈ {1, 2,. .. , 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 ∪ G2. .. ∪ G k , 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,. .. , k which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- document
- Accès libre
- Accéder au document
- ang_sync_het_setting.pdf
- Accès libre
- Accéder au document