The geometry of synchronization problems and learning group actions

DOI10.1007/S00454-019-00100-2zbMATH Open1456.05105arXiv1610.09051OpenAlexW2962844110MaRDI QIDQ2223632FDOQ2223632

Authors: Tingran Gao, Jacek Brodzki, Sayan Mukherjee 

Publication date: 29 January 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We develop a geometric framework that characterizes the synchronization problem --- the problem of consistently registering or aligning a collection of objects. The theory we formulate characterizes the cohomological nature of synchronization based on the classical theory of fibre bundles. We first establish the correspondence between synchronization problems in a topological group $G$ over a connected graph $Gamma$ and the moduli space of flat principal $G$-bundles over $Gamma$, and develop a discrete analogy of the renowned theorem of classifying flat principal bundles with fix base and structural group using the representation variety. In particular, we show that prescribing an edge potential on a graph is equivalent to specifying an equivalence class of flat principal bundles, of which the triviality of holonomy dictates the synchronizability of the edge potential. We then develop a twisted cohomology theory for associated vector bundles of the flat principal bundle arising from an edge potential, which is a discrete version of the twisted cohomology in differential geometry. This theory realizes the obstruction to synchronizability as a cohomology group of the twisted de Rham cochain complex. We then build a discrete twisted Hodge theory --- a fibre bundle analog of the discrete Hodge theory on graphs --- which geometrically realizes the graph connection Laplacian as a Hodge Laplacian of degree zero. Motivated by our geometric framework, we study the problem of learning group actions --- partitioning a collection of objects based on the local synchronizability of pairwise correspondence relations. A dual interpretation is to learn finitely generated subgroups of an ambient transformation group from noisy observed group elements. A synchronization-based algorithm is also provided, and we demonstrate its efficacy using simulations and real data.

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

Recommendations

• The geometry of synchronization
• Synchronization on Lie Groups: Coordination of Blind Agents
• On the geometry of master–slave synchronization
• A unified approach to synchronization problems over subgroups of the orthogonal group
• SYNCHRONIZATION IN RANDOM GEOMETRIC GRAPHS
• Synchronization over Cartan motion groups via contraction
• On the coordinate synchronization problem for dynamical systems
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Geometric unfolding of synchronization dynamics on networks
• Heterogeneous Multi-Agent Systems: Reduced-Order Synchronization and Geometry

zbMATH Keywords

holonomyHodge theorysynchronization problemgraph connection Laplacianfibre bundle

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Variational problems in a geometric measure-theoretic setting (49Q20) Smoothness and regularity of solutions to PDEs (35B65) Nonlinear elliptic equations (35J60) Measure-preserving transformations (28D05) Applications of optimal control and differential games (49N90) Hodge theory in global analysis (58A14) Topology of vector bundles and fiber bundles (57R22)

Cites Work

• Characteristic Classes for the Deformation of Flat Connections
• Continuous Procrustes distance between two surfaces
• Gaussian Process Landmarking for Three-Dimensional Geometric Morphometrics
• Cohomology of cryo-electron microscopy
• Visualizing data using t-SNE
• Diffusion maps
• Computational topology. An introduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Transport
• Generalized Procrustes analysis
• Procrustes Problems
• Statistical ranking and combinatorial Hodge theory
• Mapping class group dynamics on surface group representations
• Topics in differential geometry
• Title not available (Why is that?)
• The Yang-Mills equations over Riemann surfaces
• Title not available (Why is that?)
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Title not available (Why is that?)
• Simplicial De Rham cohomology and characteristic classes of flat bundles
• Flat connections and geometric quantization
• Vector diffusion maps and the connection Laplacian
• Finite element exterior calculus, homological techniques, and applications
• Characteristic Classes. (AM-76)
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• Nonabelian algebraic topology. Filtered spaces, crossed complexes, cubical homotopy groupoids. With contributions by Christopher D. Wensley and Sergei V. Soloviev
• Flat G-bundles with canonical metrics
• Higgs bundles and local systems
• Moduli of representations of the fundamental group of a smooth projective variety. II
• Flows and decompositions of games: harmonic and potential games
• The Self-Duality Equations on a Riemann Surface
• Title not available (Why is that?)
• PERSISTENCE BARCODES FOR SHAPES
• Title not available (Why is that?)
• The Riemann-Hilbert problem for holonomic systems
• Non-commutative differential geometry
• Moduli of representations of the fundamental group of a smooth projective variety. I
• Isoperimetric inequalities in simplicial complexes
• A Cheeger-type inequality on simplicial complexes
• Computing Discrete Minimal Surfaces and Their Conjugates
• Orientability and diffusion maps
• Semi-supervised learning on Riemannian manifolds
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• Rotation averaging
• Exact and stable recovery of rotations for robust synchronization
• Cramer-Rao bounds for synchronization of rotations
• A Cheeger Inequality for the Graph Connection Laplacian
• Equations différentielles à points singuliers réguliers
• Title not available (Why is that?)
• On the existence of a connection with curvature zero
• Viewing angle classification of cryo-electron microscopy images using eigenvectors
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Viewing direction estimation in cryo-EM using synchronization
• Loop spaces, characteristic classes and geometric quantization
• Graph connection Laplacian methods can be made robust to noise
• Differential geometry. Bundles, connections, metrics and curvature
• The Riemann-Hilbert problem
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Global registration of multiple point clouds using semidefinite programming
• Spectra of random graphs with given expected degrees
• Efficient rounding for the noncommutative Grothendieck inequality
• Angular synchronization by eigenvectors and semidefinite programming
• Synthetic differential geometry
• Spanning forests and the vector bundle Laplacian
• Characteristic classes of flat bundles
• Groupoids and Van Kampen's Theorem
• Extensions of complexes of groups
• Noncommutative Riemannian geometry on graphs
• Lectures on representations of surface groups
• Metric graph theory and geometry: a survey
• Numerical Geometry of Non-Rigid Shapes
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: multiscale methods
• Title not available (Why is that?)
• Geometry of characteristic classes. Transl. from the Japanese by the author
• Simplicial complexes: spectrum, homology and random walks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multireference alignment using semidefinite programming
• Conformal Wasserstein distances: comparing surfaces in polynomial time
• Characteristic classes and representations of discrete subgroups of Lie groups
• Discrete differential geometry
• Title not available (Why is that?)
• Abelian and non-abelian cohomology
• Random walks on simplicial complexes and harmonics
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Title not available (Why is that?)
• Flat Bundles and Characteristic Classes of Group-Representations
• On De Rham's theorem in synthetic differential geometry
• Conformal Wasserstein distance: II. Computational aspects and extensions
• Flat bundles and holonomy homomorphisms
• Differential forms with values in groups
• Functional map networks for analyzing and exploring large shape collections
• Controlling singular values with semidefinite programming
• Introduction to Nonabelian Hodge Theory
• Hodge theory and the local Torelli problem
• Seamless surface mappings
• A Systematic Theory of Exponential Families of Probability Distributions
• Deformed Laplacians and spectral ranking in directed networks
• Gaussian process landmarking on manifolds
• The Spectral Gap of Random Graphs with Given Expected Degrees

Cited In (11)

• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Shotgun identification on groups
• Toward a spectral theory of cellular sheaves
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Approximate and discrete Euclidean vector bundles
• The geometry of synchronization
• Optimal rates of estimation for multi-reference alignment
• Counterexamples in synchronization: pathologies of consensus seeking gradient descent flows on surfaces
• Optimal orthogonal group synchronization and rotation group synchronization
• Hodge Laplacians on graphs
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018

Uses Software

• molaR
• t-SNE

This page was built for publication: The geometry of synchronization problems and learning group actions

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