论文标题
关于最小值的固有旋转平均的分布
On the Distribution of Minima in Intrinsic-Metric Rotation Averaging
论文作者
论文摘要
旋转平均是一个非凸优化问题，它从其3D场景的图像中确定了相机集合的方向。该问题已经使用了各种距离和鲁棒。 SO（3）上的固有（或测地）距离在几何上有意义。但是，尽管某些基于距离的求解器可以接受正确性（条件）保证正确性，但在固有度量标准下未发现可比的结果。 在本文中，我们研究了局部最小值的空间分布。首先，我们进行了一项新颖的实证研究，以证明定性行为的急剧过渡：随着问题变得更加嘈杂，它们从单个（易于找到的）主要最小值过渡到充满最小值的成本表面。在本文的第二部分中，我们得出了在这种过渡发生时的理论界限。这是[24]的结果的扩展，该结果使用局部凸度作为研究问题难度的代理。通过认识到问题的基本歧管几何形状，我们对先前的工作实现了n倍的改进。顺便说一句，我们的分析还将以前的$ L_2 $工作扩展到一般$ L_P $成本。我们的结果表明，使用代数连通性作为问题难度的指标。
Rotation Averaging is a non-convex optimization problem that determines orientations of a collection of cameras from their images of a 3D scene. The problem has been studied using a variety of distances and robustifiers. The intrinsic (or geodesic) distance on SO(3) is geometrically meaningful; but while some extrinsic distance-based solvers admit (conditional) guarantees of correctness, no comparable results have been found under the intrinsic metric. In this paper, we study the spatial distribution of local minima. First, we do a novel empirical study to demonstrate sharp transitions in qualitative behavior: as problems become noisier, they transition from a single (easy-to-find) dominant minimum to a cost surface filled with minima. In the second part of this paper we derive a theoretical bound for when this transition occurs. This is an extension of the results of [24], which used local convexity as a proxy to study the difficulty of problem. By recognizing the underlying quotient manifold geometry of the problem we achieve an n-fold improvement over prior work. Incidentally, our analysis also extends the prior $l_2$ work to general $l_p$ costs. Our results suggest using algebraic connectivity as an indicator of problem difficulty.
