深度学习框架中的基于随机区域分解的非线性最小二乘求解方法

10308DeepLM：使用随机区域分解的黄精卫1，黄珊1，孙伟1，21华为技术公司里曼实验室2武汉大学摘要我们提出了一种基于深度学习框架的大规模非线性最小二乘问题的新方法。非线性最小二乘通常用Levenberg-Marquardt（LM）算法求解，以实现快速收敛。我们通过设计一个新的后向雅可比网络来实现深度学习框架上的通用高效LM求解器，以实现自动稀疏雅可比矩阵计算。此外，我们引入了一个随机区域分解的方法，使批量优化和保持收敛的大问题。我们通过解决光束法平差作为一个基本问题来评估我们的方法。实验表明，我们的优化器在质量、效率和内存方面明显优于最先进的解决方案和现有的深度学习求解器我们的随机域分解，使分布式优化，消耗很少的知识和时间，并实现类似的质量相比，一个全球性的解决方案。因此，我们的求解器有效地解决了非线性最小 二 乘 在 一 个 非 常 大 的 规 模 . 我 们 的 代 码 将 基 于Pytorch1和Mindspore2提供。1. 介绍数值优化是解决科学与工程中各种问题的一个重要阶段。在计算机视觉和图形学中，许多问题都与模型拟合有关，可以用非线性最小二乘法表示，包括网格处理[16，43，40，34]、运动和模型[2019 - 04 - 16]【2019 - 04 01：00】【2019 -04-16】【2019 - 04 01：00】【2019 - 04】[49，36，3，54，35，57，58]作为3D重建的基本问题。非线性最小二乘法广泛使用Levenberg-Marquardt（LM）算法[30，33]求解，因为它具有鲁棒性和快速收敛性。通用求解器已开发用于学术界和工业界，如第1https://github.com/hjwdzh/DeepLM2https://gitee.com/mindspore/mindspore/tree/master/model_zoo/research/3d/DeepLM图1.使用随机区域分解的深度学习框架上的大规模捆绑调整我们以高收敛质量解决非常大规模的问题。[21]和谷神星[2]。然而，他们不适合日益增长的需求，以有效地处理非常大的问题与先进的硬件，如GPU的可用性典型的算法是专门为效率或可扩展性而设计的。PBA [54]使用GPU来加速光束法平差的优化。[19]提出了用于面部表演捕捉的局部Schur补。[57]分割图形并使用ADMM [7]实现相机共识。STBA [58]通过使用校正阶段解决较小的问题来加速步长计算。然而，这些方法不能处理具有数十亿残差的问题，可能会牺牲质量，或者不能处理一般非线性最小二乘问题最近，像Tensorflow [1]和Pytorch [37]这样的深度学习框架开启了有效解决大规模问题的潜力。它充分利用了GPU等计算资源，提供了一个自动的反向传播系统，以方便用户对一般问题的编程，并实现了有效的随机优化求解器。不幸的是，它们对于求解非线性最小二乘并不理想，因为基于梯度下降的优化器10309收敛速度比常用的LM算法慢得多因此，我们的目标是在深度学习框架内开发一个随机LM优化器，以解决一般和大型非线性最小二乘问题，并大幅提高效率和可扩展性。具体来说，我们主要解决两个挑战，开发这样的优化器。首先，反向传播不能直接用于计算LM算法所需的稀疏雅可比矩阵。反向传播提供了标量函数对每个变量的偏导数，而雅可比矩阵需要所有残差对相关变量的导数。对每个残差调用反向传播是不切实际的，因为它会产生密集的雅可比矩阵，并消耗大量的内存和时间。我们发现，残差变量的指数指定了一个一对一的对应雅可比矩阵的非零元素和标量函数的导数之间在此基础上，我们设计了一个新的反向雅可比网络来计算这个标量函数，调用一个单一的反向传播来收集导数并恢复雅可比。其次，虽然基于批处理的随机优化处理大问题，它很容易导致LM求解器发散，因为LM步骤通常很大，需要从所有数据进行精确的jacobian计算。我们发现区域分解[9]可以避免发散。该方法将变量划分为不同的域，并通过固定其他域中的变量来交替优化每个域。从训练的角度来看，我们将域视为批处理，将替代优化视为具有多个时期的批处理优化。然而，这种方法降低了收敛质量，特别是对于不同域之间的边界为了实现高收敛质量，我们提出了一种新的随机区域分解方法。与传统的域分解不同，我们利用随机聚类对域进行不同的划分，使得域边界上的变量在每个时期都在变化。这极大地提高了优化的收敛质量。我们还在每个epoch开始时提供可选的全局重新初始化步骤 我们抽象每个域，保留域内残差的描述符，并全局优化不同域的所有描述符。在我们的实验中，我们主要研究了光束法平差这一基本问题。图1显示了使用我们的随机域分解解决的我们的LM求解器在质量、效率和内存方面显著优于现有的解决方案实验表明，我们的随机方法收敛速度快的全局LM求解器，并显着减少了内存和时间的消耗。消融研究表明，质量的关键贡献来自随机分解。我们在深度学习框架上为大规模非线性最小二乘提供了一个通用、高效和可扩展的随机LM求解器。2. 相关作品非线性最小二乘计算机视觉和图形学中的许多问题[16，43，11，24]需要求解非线性最小二乘。由于这些问题通常被认为是稀疏的，其中每个残差函数采用少 量 变 量 ， 因 此 可 以 有 效 地 评 估 雅 可 比 矩 阵 ，Levenberg-Marquardt（LM）算法[30，33]实际上是最佳解决方案之一在这里，核心挑战是节省时间和内存，以有效地处理大规模问题。快速和专用的LM求解器可以在GPU中实现 [54]，用于特定问题或由特定领域语言（如Opt [14]）创建的常规快速和简单的松弛方法用于进一步加速速度[50，51]，牺牲收敛质量。局部Schur补[19]可以进一步加速可以分解为具有少量边界变量的簇的问题。为了节省内存，无矩阵方法[55，61]通过推迟残差导数的评估而提出然而，这些方法仍然不适合处理内存有限的超大规模问题[57]。我们的深度求解器不仅利用GPU加速，还采用了随机批量优化方法来处理大规模问题。深度学习框架通常用于训练深度神经网络。他们提供了强大的随机求解器，具有自动微分功能[32]，以便用户可以专注于网络功能设计。例如，Tensorflow [1]和Pytorch [37]支持一阶基于梯度的求解器，包括SGD[6]，RMSProp [23]， AdaGrad [15]和 Adam [27]。 此外，这些基于梯度的求解器是通过随机优化处理超大数据的完美候选者。然而，对于非线性最小二乘问题，现有的深度求解器在收敛速度方面不如LM算法。我们设计了一个后向雅可比计算网络，并使深度学习框架中的LM求解器能够优化非线性最小二乘。区域分解区域分解[9，44，48]通过迭代求解子域中的子问题来因此，它降低了计算复杂度，提高了并行性，是一个很好的候选人为大规模的问题。最近的几种方法通过求解随机微分方程来解决不同领域的不确定性[39，5，56]。不同于他们的情况下，我们的问题是非线性最小二乘与随机性，但我们引入了一个随机聚类过程中的每个时代的高收敛质量。光束平差（BA）[49]是运动恢复结构[53，41]中的一个基本问题，10310RRRrR需要求解非线性最小二乘法。最近针对这一特定问题的工作旨在实现效率或大规模。SBA [31]使用舒尔补将问题简化为纯粹的相机系统。稀疏稀疏分解方法应用于具有可变排序的相机系统[4，13，38]。基于共轭梯度（CG）[22]的不精确解算器节省内存，并在几种不同预处理器的支持下实现更好的效率[3，26，29]。SSBA [28]和PBA [54]设计了有效的并行算法来加速捆绑调整。为了处理大规模的问题，该问题被分解成集群，并以分治的方式解决[59，60，18]优化集群内变量并全局合并集群。[36，35]优化全局分隔符，因此，x在每一步更新为x=x−Hr（x）−1JT（x）r（x）。由于Hessian矩阵Hr（x）的计算量很大，在Gauss-Newton方法中用JT（x）Jr（x）逼近Hr（x），当最终残差很小或近似仿射于最优位置时，该方法收敛.但是，当步长较大时，线性逼近不准确，高斯-牛顿更新不能保证降低残差范数。Levenberg-Marquardt（LM）方法使用类似于Tikhonov正则化的阻尼因子来调整步长：Min||r（x）+J（x）（x <$−x）||2+λ||D（x<$−x）||二、基本节点，然后进行群集内优化。运动x运动22平均[10]可以提供次优的结果，不需要亚像素精度的大规模问题。最近的方法[17，57]利用ADMM [7]的分布式系统进行全局优化。然而，它需要仔细的超参数调整，并且根据[58]，其内部迭代是耗时的。STBA [58]通过约束释放和校正解决了线性求解器内部的点一致性。然而，校正步骤仍然可能是不准确的，并防止完美收敛。我们的求解器使用深度学习框架利用并行性，并使用新的随机域分解解决大规模的鲁棒性和准确性。3. 方法我们首先在3.1节讨论一些背景知识。我们在3.2节中展示了我们的后向雅可比网络，并在3.3节和图2中介绍了使用随机区域分解的非线性最小二乘公式。在第3.4节中，我们描述了随机变量图聚类的细节。3.1. 背景非线性最小二乘问题可以用公式表示为等式1中的能量最小化：1年因此，LM步长可以通过求解（JT（x）Jr（x）+λDTD）<$x=−JT（x）r（x）（2）√其中D=diag（JT（x）JR（x））。λ用于控制可以使用信赖域来调整步长方法[8]。3.2. 后向雅可比网络用通用求解器求解方程2需要对雅可比矩阵进行精确评估。一个常见的解决方案是多维对偶数的前向微分[20]。然而，它需要用户明确指定可变维度，并且集成到标准深度学习框架中是不平凡的。另一方面，自动微分与反向传播不能直接适用于雅可比。同时计算标量函数的导数。我们需要每个剩余项对相关变量的导数。因此，所需的反向传播的数量等于残差维数n。此外，反向传播存储所有变量并且将创建维数为n×m考虑到时间和内存，这是不切实际的。我们的直觉是，不同残差对非重叠变量的导数可以用单个E（x）=2r i（x si，1，...，Xs我i，k）2.（一）从残差的总和反向传播。然而，将残差分段为非重叠x=（x1，...， xm ）是要优化的m 维变量。 r =（r1，. r n）是依赖于x的n维残差函数。1≤si，j≤m是第i个剩余项ri的第j个自变量的变量索引。额外要求Si，j对于每个残差是唯一我们的目标是最小化r的平方范数。牛顿步骤在x处局部线性化残差函数，并通过以下方式找到最优解：组和收集衍生物作为一个紧凑的链表表示[19]。我们定义一个新的变量y，使得yi，j=xsi，j。我们称y为我们的关键思想是收集残差对y而不是x的导数，以避免重叠问题。由于si，j对于每个残差ri是唯一的，所以可以如等式3所示计算原始变量的雅可比数。ΣMin||r（x）+Jr（x）（x<$−x）||二、Jr（x）（i，s）=Jr（y）（i，j）=y（ri（y））（i，j）（3）x100i、j我10311迭代次数= N(c)分隔符解算器(d)块求解器Levenberg-Marquardt算法后向雅可比矩阵网络张量运算迭代次数N(a) 变量图（b）随机聚类 （e）深度学习框架上的LM（f）优化结果图2.在每个epoch中，我们随机将变量重新聚类到C-1块和一个分隔符集群中。我们并行优化分隔符和不同块中的变量通过我们的后向雅可比网络，我们开发了一个LM求解器，并在深度学习框架。我们运行多个epoch来解决问题。(a)=i=i =i ⋅=������=（���）将导数构造为雅可比矩阵的方法。补充i，si，j阿斯图里亚斯i，j尼加拉瓜i，j尼加拉瓜i，j拉吉吉尼加拉瓜i，ji、j材料提供了LM求解器的实现细节3.3. 随机区域分解对于大规模的问题，内存无法存储雅可比矩阵甚至所有残差。虽然批量优化可以通过随机求解器来处理它，但它很容易导致LM算法发散。我们结合了区域分解的思想[9]来处理大规模问题。（B）逆向过程（C）逆向过程图3. 我们将索引变量视为独立变量，并使用单个反向传播收集这些变量的残差和的导数。导数和可变指数形成稀疏雅可比矩阵的三元组表示。我们将y视为独立变量， 并评估一个简单的反向传播（backpropagation）。在wards之后，我们使用i，si，j，Y（iri（Y））（i，j）>来形成三元组表示。Jacobian矩阵的表示详细的数学推导如图3（a）所示。在此基础上，我们设计了一个后向雅可比网络，如图3（b）所示.网络的输入是原始变量x。我们根据s重新索引变量以形成-首先，我们建立一个变量图G=< V，E >，其中V={x1，. x m}，并且E包含出现在至少一个公共残差中的所有变量对。图2（a）中显示了这样的曲线图。在图2（b）中，我们将变量划分为C个聚类，并为每个变量xi.我们还确保具有不同的标签我们称第一个簇为分隔符，其他簇为块。代替求解全局问题（等式1），我们采用区域分解方法。我们将每个聚类视为一个域，并通过在等式4中从1到C枚举c来交替求解相同聚类中的变量。1年dexed变量y y被发送到由用户提供的残差函数以评估残差。计算最终损失Lmin{xi|li=c}2我r i（x si，1，...，Xsi，k第二章（四）作为伊里岛 在反向传播过程中，我们遵循图3（c）并将导数传播到y。 由于x的每个维度对应于具有多个导数的多个ri，我们的设计允许将它们存储在从x复制的多个位置y处，并使用（i，j）→（i，si，j）将y处的导数映射到雅可比矩阵。我们的方法计算雅可比矩阵，一次反向传播假设残差维数为n，每个残差与k个变量相关，我们的时间和空间复杂度为O（nk），而Ceres[2]使用的对偶数[20]的复杂度为O（nk2）。而不是一个神经网络的训练，我们的雅可比网络是一个建筑师-由于分隔符确保不同的块不会共享残差，它使我们能够优化分隔符（图2（c）），然后并行地优化其他块（图2（d））。我们运行多个epoch来优化整个问题，如图2（b-d）所示。对于每个优化，我们使用我们的后向雅可比网络来计算雅可比，并在深度学习框架上运行具有张量操作的LM算法区域分解的一个限制是分离- 变量收敛得很慢。因此，我们重新聚类变量stochemical（细节在3.4节中讨论），分隔符集群在每个时期都在变化。i，j=1拉吉吉10000000002吉吉i L吉吉海恩-1L=∑���ii索引索引卢恩（中文）i，j���变量索引变量残差反向传播10312数据集方法 摄像头数量区块数#分隔符瓢虫STBA10618131209我们的B1061660898最终STBA427374156614我们的B427323177896图4. 从一个光束法平差问题的例子看随机分割。我们将摄像机分成不同的集群，每个集群都用不同的颜色标记。三个不同的分割结果，我们的算法得到不同的时期。此外，我们可选地支持用户指定的全局描述符作为一个整体在块上操作，要求这样的操作不改变块内残差。我们在图2（b）中根据等式5联合优化全局描述符和分隔符。表1.随机聚类统计。 使用不同的模块-在相同的最大块大小约束下，我们比STBA [58我们采用[58]提供的随机图聚类的解决方案。具体来说，每个变量都被初始化为一个聚类，聚类被重新合并以最大化具有一定概率分布的模块性[12]。与[58]不同的是，我们最小化分离器的大小以确保快速收敛。因此，我们优先合并具有连接它们的最大数量的边的聚类对，使得交叉的边的数量不同min{x i，t j |l i=1}1Σ22ri（tlsi，1<$xsi，1，，tlsi，1<$xsi，k）我（五）集群被最小化。相应地，我们将模块度定义为变量图中相同聚类内部的边的数量。[58]第58话：你是谁？其中Q使用我们的模块性重新定义我们是对第j个聚类中的所有变量进行运算的聚类j的全局描述符，并且是对于由用户指定的块内残差不变的运算例如在对于光束法平差或尽可能刚性的变形问题，可以将Tj定义为刚性变换算子，并且tj表示具有六个参数的刚性变换这样的全局描述符优化导致有效的全局描述符优化。在整个图结构上重新初始化。如果这样的全局描述符不清楚，则我们将t_j_i固定为恒等运算，使得问题简化为等式4。分 离 器 、 块 和 全 局 描 述 符 优 化 的 概 念 是 从HyperSFM [35]扩展而来的，用于具有一般图形结构的一 般 非 线 性 最 小 二 乘 。 与 HyperSFM [ 35 ] 不 同 ，HyperSFM [35]执行全局描述器优化，然后使用单个epoch执行内部块优化，我们将其视为域分解问题，执行多个epoch，并通过每次迭代随机聚类此外，我们仅对等式4或等式5执行单个LM步骤，以节省内部循环的计算时间。这样的简化比HyperSFM [35]使用我们的随机区域分解实现了更好的收敛性3.4. 随机变量图对于聚类，我们的目标是均匀地分割变量以实现最大的并行性。第二，我们希望最小化分隔符的大小。最后，我们希望随机地重新聚类问题，以便分隔符在每个时期都在变化。图聚类问题有标准的解决方案，包括[36]使用的归一化切割[42]或[19]使用的谱聚类[45]。然而，这些方法产生固定的聚类，并且对于处理非常大的数据是低效的。如果合并的集群中的变量的数量大于阈值，则停止合并对在这一步之后，我们构建分隔符集群，这样块就不会共享残差。具体来说，对于变量图中连接不同块的任何边，我们随机选取边的一个顶点并将其移动到分隔符集群。图4示出了束调整问题的示例中的分割我们将摄像机分成不同的集群，每个集群都用不同的颜色标记。我们的算法在不同时期得到了三种不同的分割结果。根据表1中的统计数据，在最大块大小的相同约束下，我们公式中的分隔符集合中的块和元素的数量小于[58]中的原始公式。4. 评价4.1. 结果基于我们的后向雅可比网络，我们在Pytorch上实现了LM求解器，其中线性方程用预处理共轭梯度求解[29]。我们对包括1DSFM [52]和BAL [3]在内的数据集提供的光束法平差问题进行了实验。我们使用BAL [3]中的初始化光束法平差问题，并使用Colmap [41]获得1DSFM的初始化问题。我们运行的机器上，与QuadroP5000 GPU和16核3.7GHz的CPU的实验。我们使用精确稀疏线性求解器（Ceres-S）和共轭梯度（Ceres-CG）将我们的方法与Ceres [2]进行比较。此外，我们还将我们的方法与PBA [ 54 ]进行了比较，PBA [54]被称为光束法平差最有效的求解器之一，H-SFM [35]和STBA [58]是两种最先进的大规模问题块式求解器。10313杜布罗夫尼克瓢虫威尼斯最终罗马广场Piccadily伦敦塔Trafalgar图5.BAL [3]（第一行）和1DSFM [52]（第二行）的问题可视化使用我们的完整管道“Ours-BG”解决绿色框表示摄影机姿势，点颜色表示其3D坐标。数据集摄像头数量点数预测数谷神星-SCeres-CGPBAH-SFMSTBAOurs-GOurs-BG我们的BTrafalgar257651322259110.8550.8621.9133.4231.0200.8580.8610.892瓢虫17231565026787181.1431.2232.2292.3721.3071.1211.1021.135杜布罗夫尼克35622673012552680.7870.7881.8992.3250.9630.7870.7880.813威尼斯177899392350019460.6600.664-2.1580.7750.6620.6640.701最终13682445611728987644-1.5873.0043.394-1.5011.5051.524联合广场647133681080833.0001.0151.7812.6353.2680.8260.8270.831P. del Popolo404141281289400.9570.9591.8633.5411.0720.9590.9600.963埃利斯岛367203551374500.9420.9422.3003.3381.1050.9420.9440.949纽约图书馆491213961497201.0071.0102.3633.902-1.0091.0111.013M. N. Dame547338302725751.0581.0572.5534.0011.1761.0581.0591.065将军markt905436202809710.8810.8832.1923.1021.0170.8800.8830.886阿拉莫741312033081470.9710.9702.1383.0811.0250.9680.9710.972约克郡910509473339020.8560.8611.7823.2690.9880.8400.8430.848罗马广场1368610084355310.9090.9061.9523.0651.0420.9060.9060.907诉大教堂1016562664590140.9130.8952.1683.0431.0330.8930.8950.899M. 都市524863645948480.4590.4360.9811.3310.5230.4380.4380.440Piccadily29181040278232210.9630.9512.2243.8427.8960.9500.9500.954T. 伦敦81418557915121670.3210.3350.6701.0790.4430.3050.3030.308Trafalgar779221665019249011.3771.3923.2675.1921.6411.3681.3701.374表2.BAL [3]和1DSFM [52]数据集中场景的不同方法产生的统计量和均方误差对于我们的方法，我们将“Ours-G”报告“Ours-BG”对于所有场景，我们将全局问题划分为17个集群，并报告了20个时期的单次运行。“Ours-BG”解决的问题质量我们报告优化后的均方误差（MSE），以衡量不同方法的优化质量。我们在表2中列出了从不同方法获得的问题和MSE的统计数据。单元格标记为如果优化失败或运行时间超过2小时，则为“-”。Ceres-S是具有精确线性求解器的全局优化，通常提供最佳质量。与其他不精确解算器或阻塞解算器相比，我们的全局解算器（Ours- G）实现了最佳质量（以粗体标记）。它产生相当接近甚至更好的结果相比，Ceres-S的几个问题。我们的随机解算器效率和内存我们在表3和表4中报告了BAL [3]数据集的时间（秒）和内存（GB）使用情况。1DSFM的其他统计数据[52]是赞成的，10314数据集Ceres-CG PBA STBA Ours-G Ours-BG 我们的BTrafalgar65.116.859.63.442.141.81瓢虫46.712.389.45.875.535.00杜布罗夫尼克32025.521313.13.973.14威尼斯1992-83553.016.514.2最终3897340-24333.925.4表3.不同方法优化的时间（秒）BAL [3]数据集的问题。数据集Ceres-CG PBA STBA Ours-G Ours-BG 我们的BTrafalgar0.190.090.250.080.030.01瓢虫0.520.320.640.240.060.03杜布罗夫尼克0.900.541.680.430.130.04威尼斯3.68-5.671.740.650.24最终16.811.9-9.733.521.24表4.不同方法优化BAL [3]数据集中的问题所使用的内存（GB）。杜布罗夫尼克瓢虫图7.城市尺度光束法平差结果的可视化使用“我们的B”进行切割。颜色对3D点的z值进行编码。时间（秒）时间（秒）表5. 城市规模的数据集。 我们能够处理多个约克郡皮卡迪利通过将数据分割为36个块，并在大约6分钟内完成优化，BG因此，我们的随机求解器支持在非常大的规模上优化问题-���时间（秒）-���时间（秒）比图6. 1DSFM中不同场景的收敛曲线[52][3]故在补充材料中。在现有的全局求解器中，GPU上的PBA [54]比多核CPU实现中运行的其他算法更快。Ours-G甚至比PBA更快。我们发现最大的区别在于从J T r内的累积求和。 我们在Pytorch中直接调用一个系数“indexadd“，而PBA分配一个把质量记录下来在实践中，它们中的任何一个都可以使用，这取决于应用程序是喜欢质量还是速度。图7显示了使用“Ours-B”解决的一个大型光束法平差问题，其中包含超过10万张图像详细统计数据见表5。我们能够通过将数据分割为36个块来处理我们自己收集的数据集中超过10亿个残差项，并在大约6分钟内完成优化线程到每个变量xi，以收集kJk，irk，即由于附加的存储器加载和与不同变量相关的残差数量的不均匀分布而效率较低。因此，我们的实现可以比PBA的内核快图6绘制了BAL [3]和1DSFM [52]数据集中几个问题的收敛曲线。“Ours-G” is our solver shownin blue, which con- verges faster than other state-of-the-art通过仔细的实现，“Ours-G”比其他现有的求解器使用更少的算法。通常情况下，我们使用较少的内存来计算我们的后向雅可比网络的雅可比。通过并行解决“我们的”的子问题深度学习解决方案 我们将LM求解器与深度学习框架中的其他基于梯度的优化器-如图8所示。与SGD [6]、RM- SProp [23]和Adam [27]相比，LM解算器收敛速度更快，质量更好。4.2. 消融研究球实验为了说明我们的直觉为什么随机区域分解有助于优化，我们考虑一个简单的球实验在方程6中，其物理意义如图9（a）和（b）所示我们有MSE（像素）MSE（像素）MSE（像素）MSE（像素）点数摄像头数量预测数区块数334.8M0.28M小行星123636存储器时间初始MSE最终MSE12.4G403s3.410.0510315我2.01.81.61.41.21.0036912迭代（一）1518211.151.101.051.00数量的块（b）第（1）款迭代图8. BAL [3]使用我们的方法和深度学习求解器（包括SGD[6]，RMSProp [23]和Adam [27]）提供的Trafalgar数据集上的收敛曲线。图9. 球的实验。(a)我们有N个球，它们离地面的高度是x，i.(b)我们优化了它们的高度，使每个球都接近地面和球的中点。相邻的球(c)是损失对迭代次数的收敛曲线。（d）-（f）是来自通过不同方法优化的前7次迭代的形状。N= 100个球，其到地面的高度为xi。我们优化它们的高度，使每个球都接近地面和它的两个邻居的中点。图10.（a）我们的不同变体的收敛曲线Bundle平差方法。随机求解器（(b)使用不同块数的“Ours-B”的全局求解器的错误率对于每次迭代，我们得到图9（c）和（f）中的绿色曲线最后，如图9（c）中的紫色曲线所示，通过我们的全局重新初始化，可以进一步增强收敛。Bundle Adjustment我们在图10（a）中绘制了我们的方法的不同变体的收敛曲线，用于BAL [3]数据集中的La- dybug 场 景 “Ours-BG-Fixed” and “Ours-B- Fixed”represent traditional domain decomposition where clusters“Ours-BG” and “Ours-B” converge quite close to在图10（b）中，我们绘制了损失与使用“Ours-B”的全局优化的比率优化质量对聚类数不敏感我们E（x）=n−1 x2+（x−xi−1+xi+1）2（6）观察到，对于当块的数量设置为128时，损失增加I2I=2对于传统的区域分解，我们通过在中间切割将变量分成两个区域，并交替优化两个区域。迭代的损失如图9（c）中的红色曲线所示另外，我们在图9（d）中可视化了前七次迭代的结果（不透明值随迭代次数增加）。收敛速度慢，尤其是对于分离器在中间为了改变分隔符，我们在第i次迭代中以25×（imod3 + 1）前七次迭代的收敛曲线和优化状态如图9（c）和（e）中的蓝线所示。因此，当我们改变时，优化收敛得更快每个epoch的分隔符。 通过随机选择分隔符256个。我们认为原因是每个集群内的摄像机太少。例如，通过将图形分割为256个块，每个块最多包含杜布罗夫尼克场景的2个摄像机。因此，损失增加不会出现在像“决赛”和“特拉法加”这样的较大场景中5. 结论我们基于深度学习框架为大规模非线性最小二乘问题开发了一种有效的解决方案我们的后向雅可比网络使我们能够在Pytorch中实现LM求解器，我们的随机区域分解方法帮助我们鲁棒地解决快速收敛的超大规模问题。MSE（像素）MSE（像素）误差比10316引用[1] Mart 'ın Abadi，Paul Barham，Jianmin Chen，ZhifengChen ， Andy Davis ， Jeffrey Dean ， Matthieu Devin ，Sanjay Ghe- mawat，Geoffrey Irving，Michael Isard，etal. Tensorflow：A大规模机器学习系统。在第12届{USENIX}操作系统设计和实现研讨会（{OSDI}16）中，第265-283页，2016年。一、二[2] Sameer Agarwal，Keir Mierle，et al. Ceres solver. 2012.一、第4、5项[3] Sameer Agarwal，Noah Snavely，Steven M Seitz，andRichard Szeliski.大规模的捆绑式调整。在欧洲计算机视觉会议上，第29Springer，2010. 一、三、五、六、七、八[4] Patrick R Amestoy，Timothy A Davis，and Iain S Duff.一种 近 似 最 小 度 排 序 算 法 。 SIAM Journal on MatrixAnalysis and Applications，17（4）：886 3[5] Alexander Bihlo，Ronald D Haynes，and Emily J Walsh.基于随机区域分解的时变自适应网格生成。arXiv预印本arXiv：1504.00084，2015年。2[6] 我 在 博 图 。 随 机 梯 度 下 降 的 大 规 模 机 器 学 习 在COMPSTAT'2010的会议记录Springer，2010. 二、七、八[7] 史蒂芬·博伊德尼尔·帕里克和埃里克·朱通过交替方向乘法器的分布式优化和统计学习。Now Publishers Inc，2011. 第1、3条[8] Richard H Byrd，Jean Charles Gilbert，and Jorge Nocedal.非线性规划的一种基于内点技术的信赖域方法。89（1）：149-185，2000. 3[9] Tony F Chan，Tarek P Mathew，等.区域分解算法Actanumerica，3（1）：61-143，1994. 第二、四节[10] Avishek Chatterjee和Venu Madhav Govindu。高效和强大的大规模旋转平均。在IEEE计算机视觉国际会议论文集，第521-528页，2013年。3[11] Sungjoon Choi，Qian-Yi Zhou，and Vladlen Koltun.室内场景的立体重建。在2015年IEEE计算机视觉和模式识别会议，第5556-5565页中。2[12] 我是达迈拉克和塞巴斯蒂安·卢斯托。Mcmc卢万在线社区检测。arXiv预印本arXiv：1612.01489，2016。5[13] Timothy A Davis，John R Gilbert，Stefan I Larimore，and Esmond G Ng.列近似最小度排序算法。ACM数学软件学报（TOMS），30（3）：353-376，2004。3[14] Zacha ryDeVito， MmichaelMara ， MichaelZollh oüfer，GilbertBernstein ， Jonathan Ragan-Kelley ， ChristianTheobalt，Pat Hanrahan，Matthew Fisher，and MatthiasNiessner.Opt：一种用于图形和成像中的非线性最小二乘优化的领域特定语言。ACM Transactions on Graphics（TOG），36（5）：1-27，2017。2[15] John Duchi，Elad Hazan，和Yoram Singer.在线学习和随机优化的自适应次梯度方法。Journal of MachineLearning Research，12（7），2011.2[16] Marv i nEisenbe r ge r，ZorahLaéhner，andDanielCremers.通过变形实现无发散形状对应。在计算机图形论坛，第38卷，第1-12页。Wiley在线图书馆，2019年。一、二[17] 安德斯·埃里克森、约翰·巴斯蒂安、陈达俊和马茨·伊萨克松。基于共识的分布式束平差框架。 In Proceedingsof the IEEE Conference计算机视觉和模式识别，第1754- 1762页，2016年。3[18] Meiling Fang，Thomas Pollok，Qum Chengchao.合并-sfm：合并部分重建。在BMVC，第29页，2019年。3[19] Marco Fratarcangeli ， Derek Bradley ， Aurel Gruber ，Gaspard Zoss，and Thabo Beeler.大规模半稀疏问题的快速非线性最小二乘优化。在计算机图形论坛，第39卷，第247-259页。威利在线图书馆，2020年。一二三五[20] 安德里亚斯·格里万克和安德里亚·瓦尔特。评估导数：算法微分的原理和技术。SIAM，2008年。第三、四节[21] Gior gioGrisetti ， RainerKümmerle ， Hauk eStrasdat ，andKurt Konolige.g2o：（超）图优化的通用框架。在IEEE机器人与自动化国际会议（ICRA）上，上海，中国，第9-13页，2011年。1[22] Magnus R Hestenes，Eduard Stiefel，等.解线性方程组的共轭梯度法国家标准局研究杂志，49（6）：409-436，1952。3[23] 杰弗里·辛顿，尼蒂什·斯里瓦斯塔瓦，凯文·斯沃斯基.机器学习的神经网络第六讲小批量梯度下降概述。引自，14（8），2012。二、七、八[24] Jingwei Huang，Zhili Chen，Duygu Ceylan，and HailinJin. 6-一个360度摄像头的自由度VR视频在2017年IEEE虚拟现实（VR），第37-44页。IEEE，2017年。2[25] Jingwei Huang ， Angela Dai ， Leonidas J Guibas ， andMatthias Nießner. 3dlite：面向内容创建的商品3d扫描。ACM Trans. Graph. ，36（6）：2031[26] Yekeun Jeong ， David Nister ， Drew Steedly ， RichardSzeliski，and In-So Kweon.推进光束法平差的现代方法 。 IEEE transactions on pattern analysis and mac