  The rotation averaging problem is a fundamental task in computer vision
applications. It is generally very difficult to solve due to the nonconvex
rotation constraints. While a sufficient optimality condition is available in
the literature, there is a lack of \yhedit{a} fast convergent algorithm to
achieve stationary points. In this paper, by exploring the problem structure,
we first propose a block coordinate descent (BCD)-based rotation averaging
algorithm with guaranteed convergence to stationary points. Afterwards, we
further propose an alternative rotation averaging algorithm by applying
successive upper-bound minimization (SUM) method. The SUM-based rotation
averaging algorithm can be implemented in parallel and thus is more suitable
for addressing large-scale rotation averaging problems. Numerical examples
verify that the proposed rotation averaging algorithms have superior
convergence performance as compared to the state-of-the-art algorithm.
Moreover, by checking the sufficient optimality condition, we find from
extensive numerical experiments that the proposed two algorithms can achieve
globally optimal solutions.
