Group synchronization on grids

DOI10.4171/MSL/6MaRDI QIDQ2319814zbMATH OpenFDO

Authors Emmanuel Abbe, Laurent Massoulié, Allan Sly, Nikhil Srivastava, Andrea Montanari

Publication date 20 August 2019

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

graphscommunity detectiongroup synchronizationweak recovery

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Estimation in multivariate analysis (62H12) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: Group synchronization requires to estimate unknown elements $({heta}_v{)}_{vinV}$ of a compact group $mathfrakG$ associated to the vertices of a graph $G=(V,E)$, using noisy observations of the group differences associated to the edges. This model is relevant to a variety of applications ranging from structure from motion in computer vision to graph localization and positioning, to certain families of community detection problems. We focus on the case in which the graph $G$ is the $d$-dimensional grid. Since the unknowns $$ are only determined up to a global action of the group, we consider the following weak recovery question. Can we determine the group difference ${heta}_u^{-1}{heta}_v$ between far apart vertices $u,v$ better than by random guessing? We prove that weak recovery is possible (provided the noise is small enough) for $dge3$ and, for certain finite groups, for $dge2$. Viceversa, for some continuous groups, we prove that weak recovery is impossible for $d=2$. Finally, for strong enough noise, weak recovery is always impossible.

Recommendations

• A unified approach to synchronization problems over subgroups of the orthogonal group
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• On the computational tractability of statistical estimation on amenable graphs
• Message-passing algorithms for synchronization problems over compact groups
• Exact and stable recovery of rotations for robust synchronization

Cites work

• scientific article; zbMATH DE number 1054729 (Why is no real title available?)
• scientific article; zbMATH DE number 2038320 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• A remark on global positioning from local distances
• Angular synchronization by eigenvectors and semidefinite programming
• Community detection and stochastic block models: recent developments
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• Cramer-Rao bounds for synchronization of rotations
• Eigenvector synchronization, graph rigidity and the molecule problem
• Exact and stable recovery of rotations for robust synchronization
• Gibbs measures and phase transitions.
• Localization from incomplete noisy distance measurements
• Message-passing algorithms for synchronization problems over compact groups
• On Intrinsic Cramér-Rao Bounds for Riemannian Submanifolds and Quotient Manifolds
• Phase transitions in semidefinite relaxations
• Statistical Physics of Spin Glasses and Information Processing
• Strong-disorder paramagnetic-ferromagnetic fixed point in the square-lattice \(\pm J\) Ising model
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The Nishimori line and Bayesian statistics
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• Unpredictable paths and percolation

Cited in

(17)

• Transience and anchored isoperimetric dimension of supercritical percolation clusters
• Message-passing algorithms for synchronization problems over compact groups
• Phase transitions for the XY model in non-uniformly elliptic and Poisson-Voronoi environments
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Shotgun identification on groups
• Strong Recovery In Group Synchronization
• Continuous symmetry breaking along the Nishimori line
• Statistical reconstruction of the GFF and KT transition
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Tightness of SDP and Burer-Monteiro factorization for phase synchronization in a high-noise regime
• Graph powering and spectral robustness
• On the computational tractability of statistical estimation on amenable graphs
• Application of the information-percolation method to reconstruction problems on graphs
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• On the landscape of synchronization networks: a perspective from nonconvex optimization
• An information-percolation bound for spin synchronization on general graphs
• Iterative algorithm for discrete structure recovery

This page was built for publication: Group synchronization on grids

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