Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs

• URL: http://arxiv.org/abs/2109.08046v1
• Date: Thu, 16 Sep 2021 15:22:28 GMT
• Title: Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs
• Authors: Gabriel Moreira, Manuel Marques, Jo\~ao Paulo Costeira
• Abstract summary: A cornerstone of geometric reconstruction averaging seeks the set of absolute rotations that optimally explains a set of measured relative orientations between them. Our proposed methods achieve a significant gain both in precision and performance.
• Score: 2.1423963702744597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs [6.511636092857915]
  A benchmark of geometric reconstruction, averaging seeks the set of absolute settings that optimally explains a set of measured relative orientations between them. We propose a novel primal-dual cycle method motivated by the widely accepted spectral theory.
  arXiv  Detail & Related papers  (2024-05-29T21:46:39Z)
• A Primal-Dual Algorithm for Faster Distributionally Robust Optimization [12.311794669976047]
  We present Drago, a primal-dual algorithm that achieves a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems. We support our theoretical results with numerical benchmarks in classification and regression.
  arXiv  Detail & Related papers  (2024-03-16T02:06:14Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization [20.11028799145883]
  We propose an Accelerated Cyclic Coordinate Dual Averaging with Extrapolation (A-CODER) method for composite convex optimization. We show that A-CODER attains the optimal convergence rate with improved dependence on the number of blocks compared to prior work. For the setting where the smooth component of the objective function is expressible in a finite sum form, we introduce a variance-reduced variant of A-CODER, VR-A-CODER, with state-of-the-art complexity guarantees.
  arXiv  Detail & Related papers  (2023-03-28T19:46:30Z)
• RAGO: Recurrent Graph Optimizer For Multiple Rotation Averaging [62.315673415889314]
  This paper proposes a deep recurrent Rotation Averaging Graph (RAGO) for Multiple Rotation Averaging (MRA) Our framework is a real-time learning-to-optimize rotation averaging graph with a tiny size deployed for real-world applications.
  arXiv  Detail & Related papers  (2022-12-14T13:19:40Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent [15.136397170510834]
  We prove new geodesic convexity results which provide stronger control of the iterates, a free convergence. Our techniques also enable the analysis of two related notions of averaging, the entropically-regularized barycenter and the geometric median.
  arXiv  Detail & Related papers  (2021-06-16T01:05:19Z)
• Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging [47.3713707521106]
  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. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods.
  arXiv  Detail & Related papers  (2021-03-15T11:31:34Z)
• Pushing the Envelope of Rotation Averaging for Visual SLAM [69.7375052440794]
  We propose a novel optimization backbone for visual SLAM systems. We leverage averaging to improve the accuracy, efficiency and robustness of conventional monocular SLAM systems. Our approach can exhibit up to 10x faster with comparable accuracy against the state-art on public benchmarks.
  arXiv  Detail & Related papers  (2020-11-02T18:02:26Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck. We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian. We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
  arXiv  Detail & Related papers  (2020-02-16T09:01:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.