Published on Tue Dec 29 2020

An extension of the angular synchronization problem to the heterogeneous setting

Mihai Cucuringu, Hemant Tyagi

In this paper, we consider a generalization to the setting where there exist unknown groups of angles. We propose a probabilistic generative model for this problem, along with a spectral algorithm for which we provide a detailed theoretical analysis. The theoretical findings are complemented by a comprehensive set of numerical experiments.

0
0
0
Abstract

Given an undirected measurement graph , the classical angular synchronization problem consists of recovering unknown angles from a collection of noisy pairwise measurements of the form , for each . 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 unknown groups of angles , for . For each $ \{i,j\} \in E$, we are given noisy pairwise measurements of the form for an unknown . 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 , where the '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 , which is of independent interest, as it is shown to improve the final recovery accuracy across all the experiments considered.

Wed Apr 01 2020
Machine Learning
Synchronizing Probability Measures on Rotations via Optimal Transport
We introduce a new paradigm, measure synchronization, for synchronizing graphs with measure-valued edges. We propose a nonparametric Riemannian particle optimization approach to solve the problem. Our qualitative and quantitative experiments show the validity of our approach.
0
0
0
Wed Jan 25 2017
Computer Vision
Distributed methods for synchronization of orthogonal matrices over graphs
This paper addresses the problem of synchronizing orthogonal matrices over directed graphs. For synchronized transformations, composite transformations over loops equal the identity. The proposed methods are verified in numerical simulations.
0
0
0
Wed Sep 16 2020
Machine Learning
A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group
In this paper, we consider the class of synchronization problems over a closed subgroup of the orthogonal group. Under certain conditions on the subgroup, the measurement model, the noise model and the initialization, the estimation error of the approach decreases geometrically. Experiment results show that our approach outperforms existing approaches in terms of computational speed, scalability and estimation
0
0
0
Wed Aug 12 2020
Machine Learning
Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods
Group synchronization asks to recover group elements from their pairwise measurements. It has found numerous applications across various scientific disciplines. We establish our theory by applying the recent popular~\emph{leave-one-out} technique.
0
0
0
Wed Sep 02 2015
Machine Learning
On Transitive Consistency for Linear Invertible Transformations between Euclidean Coordinate Systems
Transitive consistency is an intrinsic property for collections of linear invertible transformations between Euclidean coordinate frames. This work addresses the problem of synchronizing transformations that are not transitively consistent. Two direct or centralized synchronization methods are presented.
0
0
0
Wed Jun 28 2017
Machine Learning
Generalized notions of sparsity and restricted isometry property. Part II: Applications
The restricted isometry property (RIP) is a universal tool for data recovery. It turns out that for a given measurement instrument the number of measurements for RIP can be improved.
0
0
0