Abstract
In this paper we explore the role of duality principles
within the problem of rotation averaging, a fundamental
task in a wide range of computer vision applications. In
its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality.
While such an approach is well-known it is normally not
guaranteed to provide a tight relaxation. Based on spectral
graph theory, we analytically prove that in many cases there
is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of
important non-convex problems in polynomial time.
We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers and is able to
handle the large problem instances commonly occurring in
structure from motion settings. The potential of this proposed method is demonstrated on a number of different
problems, consisting of both synthetic and real-world data