The geometry of synchronization problems and learning group actions

DOI10.1007/S00454-019-00100-2MaRDI QIDQ2223632zbMATH OpenOpenAlexFDO

Authors Tingran Gao, Jacek Brodzki, Sayan Mukherjee

Publication date 29 January 2021

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

Full work available at URL https://arxiv.org/abs/1610.09051, https://eprints.soton.ac.uk/430926/1/Gao_Brodzki_Mukherjee_The_Geometry_of_Synchronization_Problems_and_Learning_Group_Actions.pdf

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)

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.

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

Cites work

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

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
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Hodge Laplacians on graphs

Describes a project that uses

Uses Software

• t-SNE
• molaR

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)