Synchronization Problems: From Geometry to Learning

Thursday, May 24, 2018 - 10:30am - 11:30am
Lind 305
Tingran Gao (University of Chicago)
We develop a geometric framework, based on the classical theory of fibre bundles, to characterize the cohomological nature of a large class of synchronization-type problems in the context of graph inference and combinatorial optimization. In this type of problems, the pairwise interaction between adjacent vertices in the graph is of a non-scalar nature, typically taking values in a group; the consistency among these non-scalar pairwise interactions provide information for the dataset from which the graph is constructed. We model these data as a fibre bundle equipped with a connection, and consider a horizontal diffusion process on the fibre bundle driven by a standard diffusion process on the base manifold of the fibre bundle; the spectral information of the horizontal diffusion decouples the base manifold structure from the observed non-scalar pairwise interactions. We demonstrate an application of this framework on evolutionary anthropology.
MSC Code: 
05C50, 62-07, 57R22, 58A14