Algorithms Seminar

The Geometry of Synchronization Problems and Learning Group Actions

Speaker:Tingran Gao
Date: Thursday, February 16, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


We develop a geometric framework, based on the classical theory of fibre bundles, to characterize the cohomological nature of a large class of \emph{synchronization-type problems} in the context of graph inference and combinatorial optimization. We identify each synchronization problem in topological group $G$ on connected graph $\Gamma$ with a flat principal $G$-bundle over $\Gamma$, thus establishing a classification result for synchronization problems using the representation variety of the fundamental group of $\Gamma$ into $G$. We then develop a twisted Hodge theory on flat vector bundles associated with these flat principal $G$-bundles, and provide a geometric realization of the \emph{graph connection Laplacian} as the lowest-degree Hodge Laplacian in the twisted de Rham-Hodge cochain complex. Motivated by these geometric intuitions, we propose to study the problem of \emph{learning group actions} --- partitioning a collection of objects based on the local synchronizability of pairwise correspondence relations --- and provide a heuristic synchronization-based algorithm for solving this type of problems. We demonstrate the efficacy of this algorithm on simulated and real datasets.


Tingran Gao is a Visiting Assistant Professor in the Department of Mathematics at Duke. His work focuses on understanding the geometry and topology of massive datasets, lying at the intersection of applied harmonic analysis and manifold learning; some of his work apply computational geometry to large-scale automated statistical shape analysis in evolutionary anthropology.