旋转平均中极小值的分布的研究

6031关于内度量旋转平均中极小值的分布凯尔威尔逊华盛顿学院数学与计算机科学系Chestertown，MDkwilson24@washcoll.edu大卫·宾德尔康奈尔大学计算机科学系Ithaca，NYbindel@cs.cornell.edu摘要旋转平均是一个非凸优化问题，它从3D场景的图像中确定相机集合的方向这个问题已经研究了使用各种距离和鲁棒。SO（3）上的内禀（或测地线）距离具有几何意义;但是，虽然一些外部的基于距离的求解器承认（一致地）保证正确性，但是在内部度量下没有发现可比较的结果。本文研究了局部极小点的空间分布。首先，我们做了一个新的实证研究来证明定性行为的急剧转变：随着问题变得越来越嘈杂，它们从一个单一的（容易找到的）占主导地位的最小值转变为一个充满最小值的成本表面。在本文的第二部分，我们推导出一个理论界时，这种转变发生。本文推广了文[24]的结果，文[24]以局部凸性为代理来研究问题的难度。通过认识到潜在的商流形几何的问题，我们实现了一个N倍的改进，比以前的工作。顺便说一句，我们的肛门-ysis还将先前的l2工作扩展到一般lp成本。我们的研究结果表明，使用代数连接作为问题难度的指标。1. 介绍旋转平均问题出现在计算机视觉中，作为估计一组相机的三维姿态的一部分。我们得到了许多图像的一些场景，产生的相机在未知的位置和未知的方向。当两个图像重叠时，通常可以估计相关联的相机的相对取向通过考虑许多重叠的相机对，我们得到许多这样的成对测量。本质上，旋转平均是一个图上的优化目标是为每个顶点选择一个绝对方向，最好与相对取向测量一致相对和绝对方向都必须在SO（3）中，即3D空间的方向保持旋转群。我们可以选择的成本函数用于旋转平均，计算方便，存在的理论保证，或建模的关注。从几何学的角度来看，基于内在度量的成本-SO（3）上的测地距离-是一个自然的选择。然而，目前已知没有事实上，已知l2测地线成本产生非凸问题。公式的基础上的外在成本-非流形距离内的代表性-已更易于处理，有时给最优性保证。当求解器失败时，垃圾解决方案会导致下游问题，如平移平均和光束法平差。本文认为成本函数的基础上的内在，测地距离。最近的两项调查[9，21]提出了一种常见的模式：使用外部求解器生成候选解，然后使用根据其建模属性选择的求解器进行优化-即使后一个求解器仅保证局部最优性。这是几何计算机视觉中的常见模式外-内求解器模式导致了一些关键问题：“这个初始猜测是否足以让我们发现最佳解决方案？” 以及“为什么有些问题需要比其他问题更好的初始猜测？”在本文中，我们寻求这些问题的部分答案。(Note我们不建议一个新的求解器。）我们做出两个主要贡献：1. 我们实证研究成本表面的内在- sic旋转平均问题。我 们 演 示 了 如 何 属 性 的 问 题 实 例 可 以 导 致constrenging- ING分布的局部极小值。2. 通过改进文献[24]中的局部凸性分析，我们得到了这种行为的界我们展示了如何旋转平均的6032×2. 相关工作放松的方法。介绍旋转平均问题的开创性论文[13]还提出了一种基于3D旋转的单位四元数表示的求解器。这是一个典型的放松方法：通过忽略长度-1约束和最小化四元数之间的欧几里得距离，问题变成线性的。该解可能不满足单位约束（因此实际上不表示旋转），但它可以很容易地归一化许多后来的方法遵循相同的模式，即解决一个放松的问题，然后这一行的大多数作品使用旋转矩阵表示，并放松正交性和行列式约束。Martinec和Pajdla [17]放松到最小二乘问题。Arie-Nachimson 等 [3] 给 出 了 一 个 相 似 代 价 的 谱 解Arrigoni等人[4]在一个低秩中解决他们的松弛问题+稀疏框架，对离群值具有更强的鲁棒性Wang和Singer[23]通过解决l1松弛问题来寻求鲁棒性。不幸的是，即使无约束问题可以精确求解，最终的舍入解通常是不是任何特定问题的最佳解决方案，并且由于舍入而导致的多样的方法。流形方法使用黎曼几何的工具直接在旋转流形上进行优化。在实践中，这涉及迭代地求解一系列欧几里得切空间问题Govindu [14]开创了这种方法，Hartleyet al.[16]和Chat-terjee和Govindu [10]提出了鲁棒方法。Tron等人[20]给出了一个分布式共识求解器，用于特定的“重塑”成本。不幸的是，虽然这样的求解器收敛到局部最小值，但该局部最小值可能不是全局最优的。两篇调查论文[9，21]建议使用初始化和细化模式，其中全局可解的松弛方法生成初始猜测，然后基于流形的方法进行细化。核查和保证。最近，人们对求解器的验证和性能保证特别感兴趣弗雷德里克松和奥尔森[12]返回四元数，并能够验证-通过拉格朗日对偶-他们的解决方案是最佳的（如果噪音水平足够低Briales和Gonzales-Jimenez [7]给出了一个摄像机姿态的验证器，而不是旋转。 Boumal等人[5，6]取 一种统计方法，并研究了最大似然估计在Cram e′r-Rao界下的有效性。这些可视化显示了问题的图形拓扑如何相反，本文可视化拓扑结构如何影响成本曲面的宏观尺度形状，独立于解决方案的选择。最近，Ericssonet al. [11]提出了一种基于拉格朗日对偶的新求解器。不寻常的是，这种方法使用外部成本，但没有松弛（因此没有舍入间隙）。当强对偶成立时，该方法给出了全局解。对于完全图，它们表明，残差小于42就足够了。9◦.我们发现有趣的是，两个非常不同的方法（他们的：弦距离和拉格朗日对偶和我们的：测地距离和局部凸性）导致具有类似形式的陈述。Briales andGonzales-Jimenez [8] and Rosenet al. s [18]的快速松弛方法也给出了验证器。本文件是最密切相关的威尔逊等人。[24]通过局部凸性分析研究了L2内在成本它得出的结论是，一些旋转平均问题的实例表现出大面积的凸行为，但其程度与问题的大小，噪声，和连通性。然而，当地的凸性是不明显的，直到一个潜在的规范歧义被删除。本文回到[24]中的分析，对规范给出了更自然的几何描述，从而大大改进了边界。目前的分析也更一般，因为它考虑了lp成本而不是[24]的l2此外，与[11]和[24]不同的是，我们根据经验研究了在最优性界限之外会发生什么。其余部分的轮廓。本文的其余部分如下：第3节给出了旋转表示的符号和背景。它还以我们将使用的形式说明第4节是对我们问题的成本曲面形状的实证研究我们使用谱嵌入来可视化局部极小值的位置和强度这些实验清楚地表明，从简单的问题，lems占主导地位的一个单一的最小困难的问题与坏的局部极小值的优势。在第5节中，我们通过改进[24]中的局部凸性分析来约束这种行为，最后我们在第6节中提出了应用并得出结论。3. 预赛在这一节中，我们将介绍符号并正式定义旋转平均问题。我们还将注意到一些显而易见的性质。3.1. 三维旋转及其表示三维空间中的特殊正交群SO（3）是R3的旋转群.SO（3）是一个光滑的三维流形，所以它实际上是一个李群--一个连续对称的概念虽然这足以作为几何定义，但为了计算目的，我们需要坐标化表示。欧拉旋转定理指出，每一个旋转都可以分解（不是唯一的）成一个角度θ和一个轴v θ。或者，SO（3）的每个元素都可以用一个行列式为1的33正交矩阵唯一表示.作为正交矩阵，旋转矩阵具有R−1=R。角轴表示θv<$与SO（3）的切空间密切相关，SO（3）是3 × 3斜对称矩阵。我们写一个切空间6033J我˜ǁ· ǁ{R∈}R∈R→R<$→∈R∈˜˜G = (V, E) with measurements R={| ||}Σ由dextrinsic=2相关d（R，RR）.（3）iji2sin三维内禀2. 本文布吕普IJ元素：0 −θvz θvyvx3.4.一些简单的观察边缘方向如果Rij是RiR的度量，[θvθ]×=θ θvz0−θvx−θvy θvx0，其中v∈=vy.vz边（i，j）上的相对旋转-则R是一个度量RjR。我们将G视为无向图，并提供或者是Rij或者R（视情况而定）。旋转矩阵形成嵌入在R3×3的三维子流形，产生至少两个dintrinsic（R，S）=n（R<$S）（1）dextrinsic（R，S）=<$R−S<$F。（二）其中F（·）是given旋转的角度（欧拉内禀度量可以证明是测地线距离-即，遵循旋转流形曲率的最短路径的长度。外在度量穿过非流形空间：它是R3×3中的距离，因此通常比t短。他说他是一个很好的人。两个人是IJ最小约束问题。我们假设G是连通的。当G是一棵树时，总存在一个零成本解任何其他边都过度约束问题，但这种冗余提高了精度，在面对测量噪声。测量模糊性。上述形式的任何旋转平均成本函数对于映射旋转RiRiS，i V的形式S的乘法是右不变的。考虑到SO（3）n，则代价函数在整个规范等价集S上是常数，SSO（3）。3n维问题域可以被看作是划分为3维规范轨道，并且只有在选择轨道代表时，解才是唯一的。一个额外可以使用gauge-fixing约束来拾取轨道表示，关于内在度量下的旋转平均，所以我们将省略下标并简单地将dintrinsic写为d。3.2. 问题定义一个旋转平均问题实例由一个图组成，Rij（i，j）每个边上的相对方向的E。 写作n = V，我们的目标是为每个顶点选择一个绝对方向SO（3）n，以最好的方式尊重这些测量：独特的感觉最简单的规范固定方法是任意选取一个顶点（比如顶点k），并设置Rk=I3。在本文的后面，我们将考虑一种替代方法，该方法可以分解出对称性。有趣的是，Briales和Gonzalez-Jimenez [7]在从简单的顶点固定转移到类似于我们的方案时观察到更快的求解器性能。4. 一些经验观察minR∈SO（3）nφp（R）=j（i，j）∈E在本节中，我们将展示一种可视化旋转平均问题中局部极小值的空间分布的方法。它表明，结构因素（如边缘我们将把φp作为这个问题的成本函数。我们在第5节中的结果将适用于p >1的情况。3.3. 局部最小值方程（3）中的lp问题是非凸的流形值优化问题。欧氏空间中的类似问题是凸的;我们的问题的非凸性完全来自流形几何。我们考虑的迭代求解器类型从初始猜测开始，然后向一个稳定点（我们希望是局部最小值）移动这个局部最小值不一定是问题的全局最小值，第4节表明，在某些情况下，问题可能有许多坏的局部最小值。本文分析的指导思想是提高我们对这种失效模式的理解。请注意，局部极小值的多重性和空间分布原则上，这种困难可以通过足够高质量的猜测来大大减轻。因此，对于需要什么样的猜测质量，有一些理论指导是有帮助的。密度和连通性）可以极大地影响分布。我们将描述这与问题易处理性的关系实证映射的动机。 迭代求解器的一个关键故障模式是找到质量差的局部最小值。这个问题可以通过良好的初始猜测（也许通过放松问题）在很大程度上避免。即便如此，对于什么样的猜测是必要的，有一些指导也是有帮助的。事实上，对于某些优化问题，足够好的初始猜测是罕见的。在本节中，我们将从实验上研究这个问题，然后在第5节中，我们将试图从理论上解释我们的观察结果。我们从修复一个问题实例开始。然后我们收集许多局部最小值：我们选择在SO（3）n中均匀随机抽样的Nlm个初始猜测，然后运行Levenberg-Marquardt求解器[2]以有效地迭代最小化lp成本。这给了我们Nlm（可能不是不同的）局部极小值。现在我们有了一个大的随机抽样的局部最小值集合，我们可视化它们的分布。由于局部极小值存在于搜索空间SO（3）n（一个3n维流形）中，我们无法直接绘制它们。6034n4›→相反，我们首先计算（规范对齐）每一个Nlm最小值之间的成对这有效地给了我们一个带有标记边长度的图。我们使用谱投影将该图嵌入到2D平面中。这些2D嵌入在图1中示出并且在下面更详细地描述嵌入实验细节。图1中的每一行是同一图上的一系列实验;详见表1。为了创建每个问题实例，我们通过随机均匀地选择SO（3）的元素来为给定的图选择一个真实解然后，我们通过将噪声（切空间中的零均值和方差σ2高斯）综合添加到每个边缘的地面真实相对旋转来生成噪声边缘测量。图1中的列是增加的噪声水平。在一行中，只有σn变化。图形和地面实况解决方案是固定的。对于每个实验，我们使用Nlm=200个随机开始。对于谱图嵌入，我们使用扩散2内核de−d/σd 将距离转化为相似性，其中d是两个局部最小值之间的距离我们使用σ d=π对于我们所有的实验。合成噪声σn在图1中的每个实验上标记。行图参数连接αmax[11]Watts-Strogatz小世界图（一）n = 40，k = 16，p =0。0λ2（G）= 4.6十四点七度（二）n = 40，k = 16，p =0。2λ2（G）=7。719.0°（三）n = 40，k = 16，p =0。5λ2（G）=8。2十九点二度（4*）n = 40，k = 16，p =1。0λ2（G）=9。520.2度Gnm随机图（五）n=40，m=200λ2（G）= 4.2十三点六度（4*）n=40，m=240λ2（G）=9。520.2度（六）n=40，m=400λ2（G）=12。012.0 °表1.图1中的图表说明。 代数连通性λ2（G）在第5节的结果中得到了刻画.量αmax来自[11]：如果所有残差都小于α max，则它们的解可证明是最优的。（*）注意，图（4）是当p = 1时Watts-Strogatz和Gnm随机图两者的实例。如何解读嵌入式图中每个小的彩色圆圈都是局部最小值。在每个图中，绝对距离没有意义，但每个图中的相对如第5节所述，在计算距离时，量规被忽略。点的颜色和半径都与最小值的目标函数成比例抖动的点也用浅灰色绘制在后面，以显示多样性。例如，抖动揭示了在第3行第1列的图中的四个唯一最小值中，具有最低成本的最小值是强主导的。最大最小值（%max）的范围在每个实验这是达到的Nlm次运行的百分比最大的多重性最小。图1中的定性结果在重复试验下是稳定的。不同的随机图和随机合成噪声总是导致不同的2D嵌入，但下面讨论的所有趋势仍然存在。观察和趋势。图1 ~图4是Watts-Strogatz小世界随机图[19]。这个图族具有在k-连通循环图和Gnm之间平滑插值的重新布线参数p，G nm是从具有恰好n个顶点和m个边的所有图随机采样的随机图模型这些图对我们来说很有趣，因为Gnm图（以及密切相关的GnpErdosRe′nyi图）并不代表真正的旋转平均问题。对于它们的尺寸，它们具有小半径和高代数连通性。通过改变Watts-Strogatz重布线参数p，我们保持图的大小固定，但改变连通性。此外，Watts-Strogatz模型更接近于捕获图像图的定性性质：具有相似姿态的摄像机更有可能重叠，然而不同的摄像机确实偶尔看到相同的东西（可能在高的或突出的结构上）。行（1）是Watts-Strogatz族的最小连通极端，具有最低的代数连通性（表1）。第（4）行则相反：100%重新布线后，这只是一个G nm的随机图，有240条边。有些问题看起来很容易解决。例如，在行（3）列1中，97.5%的随机初始化足以找到显性最小值。这个最小值实际上是全局最优值，这看起来似乎是合理的。如果这么高比例的随机初始猜测足够了，那么非随机猜测（例如来自放松求解器）似乎很有可能成功。相反，考虑行（1）列5。这是一个非常嘈杂的问题。现在有许多不同的局部极小值，其中许多非常接近彼此。迭代求解器可能难以找到真正的全局最优值。最后，看看这些图表中的趋势：• 在低噪声水平下，几乎没有明显的局部最小值。其中之一通常是占主导地位的，似乎是全球最佳。• 随着噪声水平的增加，出现更多不同的局部极小值，并且它们更接近主导极小值。• 在固定的噪声水平下，连接更多的图看起来更容易。它们具有较少的不同的极小值，并且这些极小值被更好地分离。• 从第（1）行到第（2）行再到第（3）行，连接性增强，问题似乎变得更容易。然而，行（3）和（4）看起来非常相似。额外的连接似乎没有太大的影响。是否有一个关键的连接水平？图（4）-（6）改变不同的图形参数。回想一下，（4）中完全重新布线的Watts-Strogatz图也是一个6035（一）（二）（三）（四）（五）（六）图1.旋转平均问题的局部最小值的2D嵌入。每一行都是一个固定的底层图，而列是不断增加的噪声水平（σn）。颜色和圆半径都对目标函数进行编码（冷色和小半径成本低）。为了显示多重性，在每个点后面用灰色绘制了一个小的抖动+此外，%max给出了最常见的最小值的多重性。注意，一些问题/噪声水平组合本质上具有唯一的主导局部最小值，而其他问题/噪声水平组合具有许多。表1描述了每行的图形。6036˜RRRR r r rR R240条边的Gnm随机图行（5）是具有较少边的Gnm请注意这些变化对极小值图的影响是多么剧烈！行(5)，它的边缘较少，只有2的噪声，看起来和25的行（4）一样凌乱。排（6）仍然表现良好，噪音高达25分贝实用的takeaways 这些可视化表明，lp旋转平均问题的一些实例是容易-在这个意义上说，一个单一的最小值占主导地位的成本表面。这大概是全局最优值，几乎任何初始化都足以找到它。另一方面，有些问题是性质不同的。它们有许多局部极小值，并且这些极小值很接近。此外，甚至可能存在成本非常相似但彼此不接近的最小图像。这就提出了一个重要的问题，图2.一个二维流形M<$被划分为一维轨道的图像对于解来说是足够好的（即使是全局解，切线空间TXM<$在ny点X∈M<$可以decom-如果可以的话）是有用的。在这些实验中，对于相同数量的节点和边，连接更多的图更好。毫不奇怪，在其他条件相同的情况下，低噪音也更好。有关离群值边缘的讨论，请参见补充。看看表1的最后一列，我们看到埃里克森等人。的认证[11]是足够的，但不是必需的。该边界在Watts-Strogatz图上表现出预期的行为，但在Gnm问题上则不然。这可能是由于对图的最大度的脆弱依赖。5. 改进的局部凸性界现在我们来寻求第4节所示效应的理论描述。我们着手研究的程度，局部凸旋转平均问题的实例。我们通常遵循[24]中的计算，但我们增加了两个部分：（1）计算从l2推广到lp成本，（2）我们以几何自然的方式描述规范二义性，导致边界的大幅改善。凸问题在优化中占有突出的地位，因为它们提供了一个保证：所有局部极小值都是全局极小值。对于旋转平均，这个有用的属性不成立。然而，我们可以使用局部凸性进行分析，这是一个弱得多但密切相关的性质。定义1旋转平均问题（G，）在解处是局部凸的，如果存在一个开球，该问题在该开球周围是凸的。实际上，对于至少二次可微的函数，局部凸性是一个关于问题的Hessian矩阵是半正定的声明1假设为两个正交向量空间的乘积：垂直空间（遵循轨道）和水平空间（与轨道正交）。在旋转平均的上下文中，局部凸性限制了其局部最小值，因为如果我们在凸区域上具有局部凸性，则那里不可能有明显的局部最小值。在[24]中，证明了旋转平均代价函数的l2测地线变体经常表现出局部凸性，并且局部凸性的范围是有界的问题实例的属性这一争论的关键是对规范模糊性的理解--问题中的局部凸性只有在规范被处理之后才能看到。在本节中，我们将用更自然的规范描述来重新讨论这种处理。5.1. 一个更自然的角度来看衡量通过规范二义性，我们的意思是我们的成本函数是不变的右乘SO（3）的任何元素。这是SO（3）在SO（3）n上的一个自由群作用，从而使我们考虑商流形SO（3）n/（S）上的优化问题. （这个流形上的自然度量是dquot（1，2）=minS∈SO（3）d（1，2S）.）这个商不再有计量模糊性;我们已经完全消除了对称性的问题我们想分析这个新问题的局部凸性，它提出了一个问题，黎曼流形的商有一个特别好的结构[1，第3章]。商空间中的点对应于规范等价轨道。上的切空间T×M商流形与切空间TXM<$f有关关于M<$=SO（3）n，如图2所示。特别是，注意[1]这将适用于我们的大多数分析，但是当1≤p2并且在残差为零的点时，我们缺乏可微性。相反，我们沿着以恒定速度参数化的测地线查看成本函数，小球我们只需考虑精确通过该点的测地线最后，我们注意到，沿着这样的测地线，成本函数是f（θ）= |θ|p，已知p ≥ 1时是凸的。6037MHMH101nΣ∈.RVIJ=.切空间为[θijw<$ij]×我 IJ J..⊤原切空间TX<$是两个正交向量空间的直积。垂直空间是由保持在同一规范轨道上的运动组成的子空间，而水平空间是与之正交的运动空间。值得注意的是，水平空间等同于商流形的切空间：X=T X。此外，通过这种识别，商流形上的函数的导数仅仅是到原始流形对于我们的问题，我们可以明确地说明这些空间是什么。SO（3）n的切空间中的扰动可以表示为n元组（x1，. - 是的- 是的 ，xn），其中xi是都在R3中。（严格地说，那么切空间元素是斜对称矩阵[xi]×。每个这样的切空间元素通过exp映射映射到SO（3）n的一个新元素：5.2. 一些下界近似现在我们有了一个更好的方法来从局部凸性分析中去除规范模糊性，我们从[24]中计算的Hessian矩阵开始，并通过两个近似。（规范投影）海森矩阵的最小特征值描述了问题的图结构如何与残差的大小和方向相互作用，确定局部凸性。不幸的是，这种描述是复杂的。在本节中，我们的目标是通过牺牲一些准确性来获得洞察力。在每种情况下，我们的新规范方法都比类似的先前结果产生更好的界限[24]。黑森的结构。首先，我们给出了不确定的lp成本函数的精确Hessian，如通过遵循[ 24 ]中的链式规则计算（p> 1）所推导的。回想一下，成本函数（等式（3））是expR（x，. - 是的-是的 ，x）= 0R1exp[x1]×.好吧在图的每条边上都有项同样，黑森人是成本函数中每条边的项之和：Rnexp[xn]×如果这个运动是保规的，H=（i，j）∈E嗨，（六）exp[x1] ×=. - 是的- 是的 =exp[xn] ×= S对于SSO（3）.exp映射的逆是log，它从流形映射到切空间。为×12n其中，项是由3 × 3个矩阵组成的3n×3n矩阵，个街区. 对于每一项，正好有四个3乘3的块（对应于-响应于第i和第j块行和列）是非零的。这些块用残差表示在每条边上都有RRijRj我们把这些残差写在小x，log[x]是一对一的，所以x=x我=. . . =x.=log. RRR. 哪里换句话说，在Kronecker乘积表示法中，空间是R3n的子空间：θij是边缘（i，j）上的残余旋转的幅度，而wij是它的旋转轴100ijV =跨度100001n，100001n，100001n。。.我。- 是的- 是的Sij. . .−S ij+ A ij 。. -是的（四）⊥因此，水平空间是H=V。有趣的是，好的。..V和H只与n有关。每个点的切空间j. . .−S ij + Aij。- 是的- 是的Sij.- 是的- 是的在歧管上共享相同的垂直描述。和水平空间。..（七）回到最初的问题，我们想分析一下局部凸性的一致流形版本的lp旋转平均问题。回忆一下，其中，构成每个Hij的3乘3块是pS =p（p−1）θp−2ww+θp−1（I−ww），当Hessian矩阵的所有特征值非负时，局部凸性成立这将保持前-ijijijij ij一=pθp−1[w]。2ij3ijij2ijij×当Hessian矩阵的投影为半正定：注意，对称Sij黑森州的条款是-定理1旋转平均问题是关于lp测地代价函数的局部凸的，当范围内的图形拉普拉斯类似的结构，但反对称Aij项不是。各向同性的束缚。驯服这种海森的第一种方法是找到一个只依赖于残差的界minx∈V， x=1 xx>0，（5）数量级Sij项的最佳各向同性（方向无关）下限其中H是lp代价函数（在SO（3）n上;. pp−1p−2pp−1、0016038见下文）。希季·鲁敏2θij，p（p−1）θij−2θijI3.（八）6039）−12>（i，j）∈E2 ij-是的（十七）residualsxΣ=θ（十一）2让我们把这些值称为α ij，所以我们有S ij <$α ij I 3。注意，αij纯粹是θ i j的互补函数。N〇w，不定偏斜贡献Sij可以在上面各向同性地有界为块：0ApI0p−13现在，对应于图拉普拉斯算子的零特征值的特征向量是1n，所有1的向量这意味着（考虑到克罗内克积）规范子空间与图拉普拉斯算子的0-本征向量完美对应。注意，对角矩阵的最大值是它的最大元素，所以我们有一个界限：Aij02θij0I3.（九）λ（L（α））>maxmaxpθp−1。（十六）在[24]中，我们看到对于一个海森项，2iji∈V2ijJ|（i，j）∈EΣΣΣΣ注意，在p=2的情况下，右手边简单H≻αij−αijpp−1- θI30夏威夷岛剩余图的最大加权度。如果我们ij−αijαij2ij0我3 我3如果我们希望更积极地约束，我们可以通过`PSDLaplapecciantermx`非私营部门司的共同努力，（十）最小α，给出：λ2（L）maxi∈Vpθp−1联系我们最小ij`αij对角度矩阵的元素：Dpp−1ii2ijJ|（i，j）∈E在两边乘以D−1，我们看到这对于H 0是足够的：这给出了一个完美的分离的条件，局部凸性到一个图形结构项（所谓的代数连通性），一个长期依赖于残余噪声水平。请注意，这个界限与[24]中给出的界限不同，因为分母中没有因子n公式（17）中的结构项。这仅仅是改进的量规处理的结果，l2范数=.D（θij2L（αij）D（θij）-1In.（十二）增加了边界的实际效用。6.应用与结论图拉普拉斯算子的最小特征值为0，因此条件似乎无法满足。我们必须利用我们对量规的回想一下，从商流形的角度考虑这个问题实际上意味着将切空间从垂直空间投影到水平空间。这意味着（考虑到Kronecker乘积），我们需要：本文研究了测地线lp旋转平均问题的代价曲面。我们给出的经验证据表明，问题结构和噪声的变化可能会导致局部极小值的简单分布和具有挑战性的分布之间的急剧转变。然后，我们推导出这种行为的界限：连通性必须平衡噪声以获得单个主导最小值。这些界限是一个n倍的改进，minx 1n， x=1 xLnormx> 1。（十三）以前的工作，通过处理问题的规范模糊性在几何自然的方式实现也就是说，L规范 是一个特殊的加权归一化图我们看到这种分析是有用的新的内在度量旋转平均求解器的发展我们的理论-拉普拉斯算子它表示图拓扑的相互作用和残余噪声（但不是残余方向，我们近似了），它限制了局部凸性。将这个矩阵投影到规范向量1n之外表示将问题视为在商流形上求解。更简单的束缚。如果我们更有破坏性，我们可以达到一个界限，干净地分离结构和噪声项。让L（αij）<$D（θij）。（14）下一个条件仍然是充分的，但要弱得多：λmin（L（αij））>λmax（D（θij））。（十五）Σ>−考虑所有剩余项，我们将写这是H（L（αij）D（θij））I3。L是标准图拉普拉斯矩阵[22]，具有边权重αij，D是结构IJ6040实际工作表明如何保持在轻松的制度。我们希望这一分析可以提供指导流水线设计形成旋转平均问题的例子。存在对基于分层/合并的求解器方案的特定应用 在这些方法中（这是当前活跃的研究领域），小的子问题被选择，解决，并合并成一个更大的解决方案。我们的结果是特别适用于这里，因为不像在单次拍摄计划的问题是提供的，合并求解器有自由选择他们的子问题。能够保持高连通性的方案可以更好地避免局部极小陷阱。鸣 谢 。 这 项 工 作 得 到 了 国 家 科 学 基 金 会 DMS-1620038的部分支持。6041引用[1] P-A Absil，Robert Mahony，and Rodolphe Sepulchre. 矩阵流形上的优化算法。普林斯顿大学出版社，2009年。6[2] Sameer Agarwal，Keir Mierle，and Others.谷神星解算器http://ceres-solver.org。 3[3] M. Arie-Nachimson，S. Z.科瓦尔斯基岛Kemelmacher-Shlizerman，A. Singer和R.巴斯里全局运动估计从点匹配。In3DIMPVT，2012. 2[4] F. 阿里戈尼湖马格里湾Rossi，P.Fragneto和A.Fusiello基于低秩稀疏矩阵分解的鲁棒绝对旋转估计。在3DV，2014年。2[5] N. Boumal，A.歌手和P-A。Absil用最大似然法从相对测量值中稳健估计旋转在决策和控制。IEEE，2013。2[6] N. Boumal，A. Singe r，P-A. Absil和V. D. 金发旋转同步的Cramer'r-Rao信息与推理，2014年。2[7] Briales和J.冈萨雷斯-希门尼斯3D SLAM中的快速全局最优性验证。IROS，2016. 二、三[8] Briales和J.冈萨雷斯-希门尼斯Cartan-sync：快速和全局SE（d）同步。机器人与自动化，2017年。2[9] L. 卡隆河Tron，K.Daniilidis和F.德拉特3D SLAM的初始化技术：旋转估计及其在姿态图优化中的应用综述。ICRA，2015年。 一、二[10] A. Chatterjee和V. M.戈文杜稳健的相对旋转平均。PAMI，2017年。2[11] A.埃里克森角Olsson，F. Kahl和T.下巴旋转平均化和强对偶性。CVPR，2018年。二、四、六[12] J. Fredriksson和C.奥尔森同时多重旋转平均使用拉格朗日对偶。InACCV，2012. 2[13] 诉M. 戈文杜结合两视图约束进行运动估计。载于CVPR，2001年。2[14] V. M.戈文杜用于全局一致运动估计的李代数平均。载于CVPR，2004年。2[15] G. Hartley和A.齐瑟曼。计算机视觉中的多视图几何（第二版）.剑桥大学出版社，2004年。1[16] R. Hartley，J.Trumpf，Y.Dai，and H..李旋转平均。InIJCV，2013. 2[17] D. Martinec和T.帕杰拉多视重建中的鲁棒旋转和平移估计。CVPR，2007。2[18] D.罗森湖Carlone，A. Bandiera和J.莱纳德Se-sync：一种在特殊欧氏群上进行同步的可证明正确的算法。IJRR，2019年。2[19] S. H. 斯 特 罗 加 茨 探 索 复 杂 的 网 络 。 Nature ， 410（6825）：268-276，2001年3月。4[20] R.特龙河Vidal和A. Terzis。通过SE中的共识在相机网络载于ICDSC，2008年。2[21] R.创，X。Zhou和K.丹尼尔迪斯从运动恢复结构旋转优化研究综述。在CVPR研讨会，2016年。一、二[22] 联合冯·勒克斯堡光谱聚类教程。统计和计算，2007年。8[23] L. Wang和A.歌手. 用于鲁棒同步的旋转的精确和稳定恢复信息与推理IMA，2013年。2[24] K.威尔逊，D。Bindel和N.很聪明什么时候旋转平均很难？ECCV，2016。一二六七八