Rotation averaging with the chordal distance: global minimizers and strong duality
Date
2021
Authors
Eriksson, A.
Olsson, C.
Kahl, F.
Chin, T.J.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021; 43(1):256-268
Statement of Responsibility
Anders Eriksson, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin
Conference Name
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 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 by a large margin and compares favourably to current state-of-the-art. Further, our approach is able to handle the large problem instances commonly occurring in structure from motion settings and it is trivially parallelizable. Experiments are presented for a number of different instances of both synthetic and real-world data.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.