  A cornerstone of geometric reconstruction, rotation averaging seeks the set
of absolute rotations that optimally explains a set of measured relative
orientations between them. In spite of being an integral part of bundle
adjustment and structure-from-motion, averaging rotations is both a non-convex
and high-dimensional optimization problem. In this paper, we address it from a
maximum likelihood estimation standpoint and make a twofold contribution.
Firstly, we set forth a novel initialization-free primal-dual method which we
show empirically to converge to the global optimum. Further, we derive what is
to our knowledge, the first optimal closed-form solution for rotation averaging
in cycle graphs and contextualize this result within spectral graph theory. Our
proposed methods achieve a significant gain both in precision and performance.
