  Under mild conditions on the noise level of the measurements, rotation
averaging satisfies strong duality, which enables global solutions to be
obtained via semidefinite programming (SDP) relaxation. However, generic
solvers for SDP are rather slow in practice, even on rotation averaging
instances of moderate size, thus developing specialised algorithms is vital. In
this paper, we present a fast algorithm that achieves global optimality called
rotation coordinate descent (RCD). Unlike block coordinate descent (BCD) which
solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD
directly maintains and updates all valid rotations throughout the iterations.
This obviates the need to store a large dense semidefinite matrix. We
mathematically prove the convergence of our algorithm and empirically show its
superior efficiency over state-of-the-art global methods on a variety of
problem configurations. Maintaining valid rotations also facilitates
incorporating local optimisation routines for further speed-ups. Moreover, our
algorithm is simple to implement; see supplementary material for a
demonstration program.
