旋转平均的原-对偶方法和封闭形式的解决方案

5452e⇠{}2我JF瞬间旋转平均：圈图的原-对偶方法和封闭形式GabrielMoreira ManuelMarques JoaoPauloCosteiraInstituteforSystemsandRobotics，InstitutoSuperiorTe´cnicoAv.天气-里斯本，葡萄牙{gmoreira，manuel，jpc} @ isr.tecnico.ulisboa.pt摘要作为几何重建的基石，旋转平均寻求绝对旋转的集合，其最佳地解释它们之间的一组测量的相对取向尽管是光束法平差和运动恢复结构的组成部分，但平均旋转是非凸和高维优化问题。在本文中，我们解决它从最大似然估计的首先，我们提出了一种新的初始化免费的原始对偶方法，我们的经验表明，收敛到全局最优。此外，我们得出什么是我们的知识，第一个最佳的封闭形式的解决方案，旋转平均在循环图和上下文的谱图论内的结果。我们提出的方法实现了显着的增益在精度和性能。1. 介绍旋转平均，也称为组同步，是一个估计问题，其中我们想要找到一组10个10- 510- 10十到十五10- 210- 1100101102103时间（秒）（对数标尺）图1：我们的原始-对偶方法与由Shonan Averaging [12]和SE-Sync [22]产生的解决方案之间的比较，用于从姿势图优化数据集[8]调整的旋转平均问题。最大似然估计（MLE）问题旋转{R1，. ......、Rn} 2 SO（p）n，其中p⇥p>尽量减少R1，…RnX..Re-R R>.. 2SO（p）={R2R：经常资源=1，det（R）= 1}，（1）受Ri2SO（3），i=1，. ..，n.其最优地解释了相对取向Ri R j >的m个噪声成对测量的集合Riji jSO（p）m。符号是j是指旋转i和j之间的测量值的存在。 作为的子问题几个3D重建任务，即束调整[1，26]，运动恢复结构[23，17]和相机网络校准[25]，旋转平均在计算机视觉中特别感兴趣。然而，上述问题的高维性和SO（p）的非凸性使得这个问题变得困难。在[13，12，3，20]中采用的朗之万噪声模型[6，9]的假设下，我们将旋转平均形式化贡献首先，我们提出了一种原始-对偶方法来求解（2），该方法受到正交约束优化算法的启发[15]。我们的经验表明，该算法收敛到全局最优时，对偶变量是初始化的图度矩阵（图。①的人。其次，我们提出了第一个最优封闭形式的解决方案的旋转平均问题的循环图拓扑结构。该解决方案允许机器精度全局最优值的检索比现有技术快几个数量级，并且复合了[13]中 阐 述 的 谱 图 理 论 中 的 结 果 。 我 们 的 代 码 可 在https://github.com/gabmoreira/maks 上 获得。SmallGrid3D（n=125）Torus3D（n=5000）Grid3D（n=8000）湘南湘南SE-SyncSE-Sync SE-Sync我们我们我们最优性（对数标度）-越小越好IJ伊日（二）5453eeG VE{}2ne>：eeee6.eΣ2Xe.eΣ。Σ2. 相关工作关于旋转平均的文献涵盖了大量的优化方案，从迭代搜索方法[2，12，13，14，21，22]到封闭形式的次优解[3，19，20]。最近，全局最优性已经成为旋转平均论文的焦点。然而，找到全局最小值并因此求解（2）仍然是难以有效完成的任务。在迭代算法的领域中，可以使用高斯-牛顿（GN）和Levenberg-Marquardt（LM）方法，诸如在姿态图优化框架g20中[18]和GTSAM [11]直到最近才成为解决旋转平均的最重要技术。然而，该问题的非凸性使得这些技术依赖于初始化。Tron等人提出了三维旋转流形上的分布式黎曼梯度下降算法。[25]但这种方法可以说比GN和LM效率低。为了规避局部最优的检索，其中3. 问题陈述设=（，）是一个连通图，Riji jSO（3）m是节点i和j之间的相对旋转度量的集合. 在各向同性朗之万噪声的假设下[6，9]，旋转平均寻找旋转的集合{Rij}i2V，其在图的所有边缘上最小化每个测量Ri j与相应成对估计Rijjj j之间的弦距离[ 16 ]。MLE估计[8，20，12]为{Rij}i2V=arg maxtr（Ri>Ri jRj）。（三）{Ri}i2V2SO（3）i j我们现在介绍一个分块矩阵符号，我们将在整个文件中使用。设Sp是对称pp矩阵的集合，ip2Rpp是单位矩阵，0p2Rpp是零矩阵.我们定义块向量R2SO（3）n为R：=R1>。 . .Rn>（4）并且成对分块矩阵Re2S3n为对于我们所考虑的应用没有实际意义，Eriksson等人。[13]求问题的对偶8>I3如果i=j（2）并给出了依赖于对偶理论的最优性验证的大量结果。假设强对偶成立，半定pro-boundary的解R：= Rij2SO（3）ifij0 3if i 6j.（五）对应于问题（2）的对偶的gram（SDP）产生所寻求的旋转集合。为了求解该问题，提出了一种块坐标下降法。已经提出了替代的全局最优策略。Rosen等人的SE-Sync姿势图优化框架。[22]依赖于黎曼阶梯[5，7]以解决SDP松弛并保证全局最优R的块条目i，j包含该边缘的测量旋转，或者如果i，j则包含空块。我们将从每个节点到其自身的旋转设置为恒等式，并考虑Rji=Ri>j。定义成本函数f（R）：=-trR>RR，（6）我们可以将（3）中的优化问题写为在对噪声模型的一些假设下，得到了一个错误的解。Dellaert等人提出的Shonan平均法。[12]现在尽量减少Rf（R）（七）GTSAM的一部分，局部求解SO（3）上的问题，然后增加流形的维数，再次开始优化这被迭代地执行，直到获得全局最优解。该方法结合了GN和LM方法的性能，并具有保证全局最优的策略。与上述方法相反，许多工程已经提出了最优解的封闭形式近似。Martinec等人[19]将问题视为最小二乘法，然后将解投影到旋转空间。最近，Arrigoniet al. [4，3]和Moreira等人。[20]已经提出了基于特征空间的解决方案，其注意到以下事实：对于无噪声测量，求解旋转平均等同于求解特征向量方程。虽然这些封闭形式的方法可能会产生令人满意的结果，中等的噪音水平，这是很难确定其适用范围。受 R2 SO（3）n。4. 原对偶法在本节中，我们提出了一种新的原始-对偶更新方法来解决问题（7）。我们将在第6节中展示，在所考虑的应用中，该算法成功地检索到全局最优值。如在[13]中导出的，在正交约束R2O（3）n下的旋转平均的拉格朗日量是L（R，）=-trR>RRR-tr（I-RR>），（8）其中拉格朗日乘子是块对角矩阵=blockdiag（..，n），其中微分（8），我们有平稳性条件5454.-ReΣR=0（9）5455e-Xee-2k+12k+1⇥e22ee-F我我 我J我- -e的缩写也就是说，最优旋转在R的核中。相反，我们可以通过以下公式从（9）中获得i=RiRi>+Ri jRjRi>，i=1， . ...... 你 好。 ，n.（十）伊日我们的原始-对偶方法包括将（9）和（10）分别与SO（3）n和S3 n的投影相结合，以创建原始和对偶可行更新规则。给定在第k次迭代处的对偶变量的估计，我们用k表示，等式（9）一般在SO（3）n中没有解。因此，我们采用一种近似方法。为了避免平凡解R=0，我们在Stiefel流形上寻找X10.980.960.940.920.90.880.860 0.1 0.2 0.3 0.4 0.5St（3n，3）：={X2R3n 3：X>X=I3}（11）最小化Tr。X>（k-Re）XΣ。然后我们计划重新-图2：nf的有噪声和无噪声特征空间之间的主角余弦R表示具有50个节点和不同的代数连通性（Fiedler值）。平均超过3104次模拟。Xk+1= arg minX2 St（3n，3）tr. X>（k-Re）XΣ（12）其中DRn n是图的度矩阵。因此，无噪声测量的最佳拉格朗日乘子为R=arg min.. R-X...（十三）R2SO（3）n⇤NF（12）的解由下式的三个特征向量给出：与三个最小特征值相关联的kR。这些特征空间可以有效地计算稀疏对称特征求解器的装置。（13）中的优化问题可以通过3× 3矩阵的奇异值分解来解决如[13]所示，如果原始-对偶对（R，）验证平稳性条件（9），则⇤⇤-Re⌫0is sufficient for strong duality to hold and for如[3，20]所述。在我们的方法中，我们设置0 = nf。为了理解为什么这种初始化允许原始-对偶迭代达到最优，我们凭经验表明，对于中等噪声水平，包含地面真实旋转的子空间和在k= 0处求解（12）的子空间是接近的。设RnfS3 n表示地面真值对-wise块矩阵和Re2S3n（5）矩阵，通过（R，）为最优。因此，（12）在每次迭代处的最优性评估的所有结果双重更新从高等人的工作图纸。在具有正交约束的优化问题[15]上，我们通过对称化（10）来形成对偶更新。 令（X）de-注意到S3的投影即，（X）：= 1（X+X>）.给定原始变量估计Rk，我们根据以下公式计算k=RkRk>+...... 你 好。 ，n（14）济初始化不是用原始变量的估计来初始化上述原始-对偶更新，即，一组旋转估计，我们利用了这样一个事实，即对于无噪声测量，仅取决于图topology.在这种情况下，最佳旋转R验证.（D+I）I3-ReΣR=0，（15）主角余弦通过求解n个Procrustes问题得到SO（3）n。我们的原始更新包括：=（D+I）I3，（16）5456.Σ2>>根据c os=trUUU/3计算。Asex-nfnfe-用朗之万噪声（标准差σ_n_s_e）扰动R_nf的非零块。我们在图中表示。2nfRnf的核（我们用Unf表示）与nfR的与最小特征值相关联的三个特征向量所张成的子空间（我们用U表示）之间的主角的余弦。余弦是com-期望的，这些子空间更接近良好连接的图（大Fiedler值）。然而，即使对于连接较差的节点，余弦平均也接近1。在算法1中，我们展示了我们的原始-对偶更新是稀疏特征值求解器中使用的参数σ对应于我们正在计算的特征向量的特征值目标。由于我们的原始更新是通过求解（12）来实现的，因此我们选取σ〇使得检索到的三个特征向量对应于三个最小特征值。<注意，在将原始问题的解投影到SO（3）n之前，我们通过锚定第一次旋转来固定规范自由度。切实贯彻该方法此后将被称为瞬间旋转平均（RAveSS）。这页-5457.e6Σe eeY.ΣKee e-ee-2-2Yee ee二-Res，s+1Ri←U diag [11 det（UV>）] V>;端我济IJJ我问题（7）。设置J={✓1 2， . ...... 你 好。 ，✓n1}。优化问题1个3Ri=s=1Ei-1， i2 {2，. ......、 n}（19）算法一：RAveSS（原始-双重）结果：R，←（D+In）fort←0to maxiterdoX，λ1，λ2，λ3←特征解ver-R，σ=-10-;X←XX1-1;5.1. SO（3）的单参数子群我们现在考虑SO（3）的单参数子群，假设两两旋转测量R12，R23，. ......、 Rn1共享公共轴。引理1. 对于边测度位于SO（3）的单参数子群中的圈图，对于i ← 1到n做。Σ。！U V>←SVDXi;i-1>fori←1ton与R=1，由k2{0， . ...... 你 好。 ，n-1}，是平稳的←1PReRR>+端1 .一、PjiReijRjRi>Σ>+RiRi>;证据 我们将成本函数f（6）重写为←blockdiag（..， n）;{||||||}f（R）=-3n-2Xtr. ReRR>Σ。（二十）如果min λ1，λ2，λ3，则）=\（Ri j） \（RiRj>）。从tr（R）= 1 + 2cos（I（R）），则（20）中的迹线变为tr. ReijRjRi>Σ=1+2c os。\（Reij）-\（RiRj>）Σ。（21）定义角度✓ij：=\（RiR>），✓eij：=\（Reij）和事实上，我们证明了旋转平均问题与一个underlying循环图拓扑有封闭形式的解决方案包括全局最优解。我们将最大⇥Xc os.✓eij-✓ijΣ（二十二）首先导出SO（3）的单参数子群的封闭解然后，我们表明，在一般情况下，有一个基础，其中的块矩阵R可以写，使其非空块位于SO（3）的一个参数这使得我们能够最优地解决问题（7）。循环误差我们首先定义误差E2SO（3）在-在遍历循环图开始和结束满足✓12+· ··+✓n1=2k，对于k2{0， . ...... 你 好 。 ，n-1}，满足（7）。假设残差为✓ij✓ij的，R是一个对偶变量。（22）的拉格朗日量为L （ ， y ） =Xc os （ ✓eij-✓i j ） +y。 X✓ij-2k！（二十三）伊日伊日在同一个节点上。不失一般性，让n-1E：=Rmod（k，n）+1，mod（k+1，n）+1，（17）k=0其中（17）中的矩阵乘积从左到右定义在具有3个节点的循环中，E=R12R23R31。Further，letц[ [1]是E的角，我们用ц：=\（E）表示。我们定义E的第n个根的集合为n2伊日25458X9k2{0， . ...... 你 好。 ，n-1}，✓=2k。（25）ij01将（25）和（26）与✓eij从（23），我们有充分的平稳性条件9w2[-，]，8ij✓eij-✓ij=w，（24）伊日在循环图的所有边上求和（24），我们有X✓eij-X✓ij=n w。（二十六）E1：=. E，E， . ...... 你好 。、EKΣ，（18）伊日伊日P其中Ek2SO（3），En=E且\（Ek）=ц/n-2k/n，对于k 2 {0，. ......、 n-1}。✓ij=✓eij-ц/n+2k/n。（二十七）n-1伊日=ц产量5459Re41eYee0>eUi. 例如， R：=URU。然后，六、七7e六四七五e>：eeee e eeeRe〇=6。.. . ...、（三十五）由式（19），我们有RiRj>=ReijEk>，其中ij。因此，在本发明中，\中找到。RiRj>Σ=I。RijΣ-1。EkΣ（28）简单地为（27），因为\（Ek）=ц/n-2k/n。34R4R1R3ER10R40我R30定理2. 对于边测量值R2位于SO（3）的单参数子群中，点.i-1！>0Re12Re23IRi=Rk，k+1k=1Ei-1， i2 {2，. ......、 n}（29）图3：左边的循环图问题可以跨形成了右边的问题。当R1∈=I3时，是问题（7）的一个解证据调用[13]的定理4.2对于循环图，强对偶将保持并且解将是全局op的。最后，如果8ij，则残差验证。✓eij-✓.。从引理3. 由Re0表示，矩阵Re写在基2I3I3 .. .0E>3（29），最优旋转验证ijnI3I3 .. .0个 0个Rj=E0Ri>jRi，（30）其中\（E0）=ц/n.从（30）我们可以写出00 .. .I3I3E0.. .I3I3e.e*>Σ其中E=Re1 2Re23。 . . 其中，Ren1是环er r或（17）。以来✓ij=\RijRjRi⇡=ц/n，（31）（三十二）证据从（34），在下三角形部分上的块Re0：=U >ReU由下式给出：|n|n8>U>ReU，i=n，j=lRijRi>jUi，j=i-1Ui>Uj，i= j。（三十六）SO（3）的参数子群将重新分配循环er-在所有边缘上公平地进行如果我们遇到E的错误，在\（E）=ц的情况下，最佳相对旋转RiRj将直接的是，对于i=j和j=i-1，我们具有Ri0j=I3. 它足以表明Un>Ren1U1=E。注意，从（34）我们有你. 因此，在本发明中，R=R-.. .R和U=I具有角残差联系我们13nen>1，ne2>3e1>2关于ive测量Rij。通过将该数字增加倍数的2π/n，我们得到了（7）的次优稳定点。5.2. SO（3）中的最优化ReR20我54600i-1，ii-113我们现在证明了SO（3）中的任何循环图问题对于其驻点（19）和全局有相同的表达式最优（29），如针对单参数子组导出的。我们通过在一个新的基础上写Re来实现这一点。将矩阵U2SO（3n）定义为U：=bloc k dia g. U1， . ...... 你好 。 ，UnΣ，（33）Un>Rn1U1=R1 2R23。 . . Rn-1，nRn1，（37）根据后者的定义，其等于E我们可以在图中看到这个结果3 .第三章。在循环图中，可以通过将循环误差E集中在单个边缘来求解MLE旋转平均（7此外，通过改变基，成对测量I3和E属于SO（3）的单参数子群.因此，我们可以利用5.1节的结果来检索问题（7）的全局最优解和稳定点。定理4. 对于SO（3）中具有边测量的圈图，点其中Ui2SO（3）对于i2 {1，. ......、n}根据下式计算（我Ri= .iY-1>Res，s+1 Ei-1， i2 {2，. ......、 n}（38）U：=I3，i= 1（三十四）s=1Re>U， i 2{2，. ......、n}。其中R= I，是问题（7）的解。！5461.eΣ.Σ7！0e8 2{-}.Y0e--.Σ.Σ-eee..Σ Σ[1+2c os2k/n .（45）k=0，…n-1Res，s+1Ei-1， i2 {2，. ......、 n}（43）R如果给定的解是最优的并且强对偶成立，则它为零 此外，我们表示成本函数eval-证据 我们把f写成f（R）= tr （U>R）>U>RU（U>R）。（三十九）利用变量变换R0=U>R和基变换Re0=U >ReU，我们得到了等价问题6. 实验结果在本节中，我们分别评估了我们的原始-对偶更新方法（RAveSS）和我们的闭合形式解决方案在姿态图数据集和循环图中的合成旋转平均问题中的性能。我们的算法在C++中实现，所有的测试都是一致的。尽量减少r10的tr.R0>Re0R0Σ（四十）安装在笔记本电脑上，采用6核英特尔酷睿i7-受 R02SO（3）n，根据引理3，其边缘测量值为I3和E。 这些旋转属于单参数子群texpt[n]，其中n是E的轴。因此，定理2是适用的，并且（40）的解是R0i=Ei-1，i2{1， . ......你 好。 ，n}，（41）由于Ri0，i+1 =I3， 我1、 . ...... 你 好 。 ，n1.一、 根据R=UR0 ，在旧的基向量中写入（41 ）就足够了。因为U是块对角的，所以Ri=UiR0i。根据Ui（34）的定义，9750H@2.6GHz运行macOS Big Sur。6.1. 姿势图数据集使用来自在线提供的姿势图优化文献[8]的七个数据集，我们从每个数据集中提取成对旋转测量值，以生成旋转平均问题。这些数据集中的一些包含每个边缘的多个测量，其中仅保留一个。我们比较了RAveSS（ 算 法 1 中 的 原 始 -对 偶 更 新 方 法 ） 与 Shonan平 均（SA）[12]和SE-Sync [22]的性能。作者的实现可以在网上找到，我们用他们的默认参数对它们进行了由于SE-Sync旨在解决Ri=i-1s=1>Res，s+1 Ei-1， i2 {2，. ......、 n}（42）在姿势图优化问题中，我们将输入转换设置为零。我们的方法的停止标准被定义为|λ0|<10- 15，其对应于其中R1=I3。作为定理4的推论，我们可以在新的基中取问题的任何驻点（参见引理1），并恢复到旧的基向量，以便获得问题（7）的相应驻点。因此，各点Krylov特征解算器。结果可以在表1中观察到。 为了将这三种方法在正半定性方面并置即为了验证最优性，我们如下进行。对于计算的每个估计，我们使用（10）和（12）中的KKT条件获得拉格朗日乘子。.IY-1！>Ks=1通过投影使其对称化。列λ0ble1对应于的最小特征值在Ta-e、其中R1=I3，是（7）的稳定点，其下标为k2{0，. ......、 n-1}，其中成本函数评估为f（R）=-3n-2ntrEk.（四十四）由于trEk=1+2c os（ц/n2k/n），因此节点的数量越大，接近全局最优值的局部最小值的数量越大。因此，很难最佳地解决旋转平均。我们通过证明在循环图中R的谱与f在驻点处的值有关，因此可以以封闭形式计算来结束本节。第五章. 设σ（R）表示R的谱。然后，σ。ReΣ=.1+2c os.ц/n-2k/nΣΣk=0，...，n-1证据见附录（第8.1节）。Ri=！5462-e-在RAveSS产生的解处进行评估，由f表示，并且该最小值与SA和SE-Sync计算的最小值之间的差由6=f表示F.所有三种算法的CPU时间均以秒为单位显示。基准的三种方法在所有七个数据集上都达到了全局最优。虽然可能存在不一致的re-garding精度，在所考虑的应用中，在所获得的最小值和所产生的旋转集合方面的差异是可以忽略的因此，我们专注于每个算法的CPU时间我们的原始-对偶方法达到λ0的机器精度，因此全局最优，比其他两种方法停止迭代的速度更如果我们放松我们的停止标准的上限，CPU时间可以进一步降低，而不会影响几何重建的解决方案。补充材料中提供了显示RAveSS在6个数据集的正半定性方面收敛的图5463e-||数据集图n m|λ 0|RAveSS（我们的）ft（s）|λ 0|湘南平均6（近似值）t（s）|λ 0|SE-Sync6（近似值）t（s）SmallGrid125297十到十五十到十五十到十五十到十五十到十五十到十五十到十五-2118202-42632998-56981692-69227058-92163079-157206257-1640379300的情况。020的情况。060的情况。360的情况。350的情况。461 .一、78五、9210-07十点零五分10-0710-06十点零五分10-07十点零五分-10- 04-10- 01-10- 03-10- 02-10- 02-10- 02-10- 010.5524.530.198.896.8154.54221.6310-08十到十四10-0910-0910-0810-0910- 12-10- 05-十-十-10- 05-10- 05-10- 04-10- 04-10-070.090.992.793.862.4911.698.73车库16616275球体22008647Torus3D50009048隔间575012486Grid3D800022236Rim1019522251表1：RAveSS（算法1）、Shonan平均[11]和SE-Sync [22]之间的比较数据来自[8]。6.2. 循环图形借用[12，13]中采用的评估方法，我们在合成循环图数据集中测试了我们的封闭形式循环图解决方案，名为C-RAveSS。这些由具有不同大小的底层循环图结构的随机旋转平均问题组成，其中地面真实绝对方位Ri对应于旋转围绕z轴的运动，形成圆形轨迹。合成的成对测量值进行了模拟perturbing相邻节点之间的相对地面实况方向的误差矩阵从角轴表示。轴在单位球体上均匀采样。这些角度是从具有零平均值和标准差σ的正态分布绘制的。我们针对两个基线对C-RAveSS进行基准测试，块坐标下降法（BCD）[13]用于解决问题（7）的对偶的对偶，以及我们也在姿势图实验中测试的SA算法。我们在MATLAB中实现了前者，并使用了作者这两种方法都是随机初始化的。在表2中可以观察到20次模拟的平均结果。对于我们的解决方案，我们列出最小的特征值R，用λ¯0表示，它证明，如我们所示，我们的解决方案对于我们运行的所有模拟中的机器精度是最优的。在最右边的两列中，我们显示了我们的封闭形式的全球最小值和成本函数evalu，在一组旋转产生的SA和BCD。使用其默认设置，SA在进行的所有测试然而，不仅精度下降，作为周期的顺序增加，但也平均CPU时间大幅激增，因为变量的数量增加。为了测试BCD方法，我们首先使用C-疯狂然后我们用它来设置BCD的停止标准为610-3。正如平均CPU时间所证明的，收敛在最大周期内是平坦的对于n=100，使用该算法达到全局最小值（小数点后三位）问题n σ（rad）C-RAveSS|t ¯（s）| t¯ (s)湘南6¯t¯（s）BCD6¯t¯（s）200的情况。2十到十五0.0000710- 40.1110- 30.180的情况。5十到十五0.0000710- 40.1210- 30.235464表2：随机循环图问题的封闭形式解决方案，Shonan平均[12]和块坐标下降法（BCD）[13]之间的比较。图4：使用我们的封闭式解决方案对循环图进行重建，在70µs内计算出38个最佳旋转。并且比n=200所需的时间更长。虽然这可能是我们实现的缺点，但CPU时间的数量级似乎与[12]中报告的数量级一致。这些实验验证了我们的解决方案作为最快和最精确的方法来解决循环图。如表2所示，我们的最佳闭合形式表示超过最先进技术的性能增益，其可能高达10000倍。图图4示出了该解决方案在使用从较大的3D重建数据集[10]提取的循环图旋转平均问题的几何重建中的应用5465e.Σe一个.6Σ75e.7ee7n，（52）Σ23K..e46cos.zk：=cos 2 2knE7. 结论在本文中，我们提出了两个贡献的平均多个旋转的问题。考虑到Langevin噪声假设下的极大似然估计公式，我们提出了一种原始-对偶更新方法和一个封闭形式的解决方案的循环图。正如我们的实证评估所证明的那样，前者在现有求解器的一小部分时间内产生了最佳的解决方案，以机器精度。此外，它在每次迭代时默认验证最优性。后者是，据我们所知，第一个最佳的封闭形式来推导这一类问题。从最佳解决的问题，用来钉领导通过迭代搜索方法，在封闭形式的性能增益，是substan。如所进行的实验所证明的因此，的对角线包含R 0 的三个 特征值。根据（49），这些特征值 是I3+Ek+Ek的特征值，即，{3，1+ 2cos（\（Ek）），1+ 2cos（\（Ek））}. 根据定义\（Ek）=ц/n-2k/n，因此1+2c os（/n-2k/n）k=0，...，n-1σ（R），其中 每个特征值具有重数2。为了识别R的剩余η个特征值，令η（表示循环误差E的轴，即， En=n且E>n=n。定义向量zk2r3n二、2kΣ3cos 1N六、七8. 附录8.1. 定理5我们将给出R0的谱的 结 果，由于矩阵相似，所以R0的谱与Re的谱相等。我们从.（n-1）索引为k 2 {0，. ......、 n-1}。我们有Re0zk=n示出了块向量Vk2R3n 3，其中二、.Σ。Σ301 +cosE62kn+cos.（n-1）2k）n7六一七六、.Σ。 Σ。ΣΣ7Vk：=6k7，（46）62k2k 2k74个6.七五cos四六（i-1）n+cosin.+cos（i+1）nn7En-1索引为k 2 {0，. ......、的n-1}跨距不变子空间.1+cosnK.Σ2k5466nn.EnRz= 1 + 2 cos（2k/n）z、（54）.236（n-2）2k2+ cos（n-1）2k3ΣΣn5R0即， 9H2R33：R0Vk=VkH. 对于该步骤，它用于计算Re0Vk。从（35）和（46）✓✓2k◆◆61.2k Σ7E02E0+E1+E>En-135467e..ΣΣk=0，…，n-1.=1+2 cosn因.7（535468）5469.=EKeK6 杨永.七六Ek+ Ek+Ek.K2K0K3K.7我.6K.4.第一章En-13KKe06.K K.RK54707七五6i-1iKi+17547146c os.（n-1）2kΣ754个6.七五六四.EE0+En-2+En-1在紧凑符号中，（53）读作e0k.Σk.对于k2{0，. ..，n-1}。它遵循=I 7 .第一次会议。I3+Ek+Ek>Σ.（四十七）.1+2cos（2k/n）Σk=0，…，n-1σ（Re）.（55）6En-175它是紧凑符号，（47）读作R0Vk=Vk（I3+Ek+Ek）。（四十八）由于I3+Ek+Ek>2S3，设其EVD为EVDI+E+E>=JJ >， （49）其中J2O（3）和2R3 3是对角线。（48）我们有Re0（VkJ）=（VkJ）。（五十人）最后，从（51）和（55）我们有σ（R）=1+2cosц/n-2k/n[。1+2c os.2k/nΣΣk=0，…，n-1。（五十六）致谢作者感谢审稿人的评论和建议。这项工作由Fundaca oparaaC ie nciaeTecnologia，grant [UIDB/50009/2020]资助。JoaoPauloCost eira和ManuelMar-ques也得到了欧盟地平线2020项目（GA 825619，AI 4 EU）的支持