Abstract:
|
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. 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 hese flat principal $G$-bundles, and provide a geometric realization of the 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 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.
|