1再论可分离非线性最小二乘问题的变量投影法英国剑桥大学jhh37@cam.ac.uk东芝欧洲研究所christopher.m. gmail.comAndrew Fitzgiant微软awf@microsoft.com摘要变量投影（VarPro）是一种通过最优地消除未知量的子集来有效地解决优化问题的框架它特别适用于可分离的非线性最小二乘（SNLS）问题，这类优化问题包括缺失数据的低秩矩阵因子分解和仿射光束法平差。基于VarPro的方法在过去的十年中受到了很大的关注，这是由于实验观察到的某些问题类的大收敛域，其中它们在所有未知数上都比基于联合优化的然而，在文献中没有找到明确的答案，为什么VarPro优于其他人，为什么联合优化，这已经成功地解决了许多计算机视觉任务，失败的这类问题。此外，VarPro主要在中小型数据集上进行测试的事实也引发了对其可扩展性的质疑。本文旨在解决这些未解之谜。1. 介绍优化方法在计算机视觉和相关领域中起着普遍的作用，并且其性能的改进可以实现新的功能和应用。近年来，人们已经认识到，使用非最小参数化可以显著改善收敛性示例包括用于二进制分割的凸松弛（例如，[8]），以及用于MAP推断的提升方法（例如，[16，29]），3D模型拟合[7]和鲁棒成本[31]。在这些示例中，已经从理论上证明或经验上示出，未知量的非最小表示导致具有显著较低目标值的解，这通常是因为 相反，在文献中经常观察到一类相反的问题：使用非最小参数化用于低秩矩阵分解问题(a) 估计的3D点（b）估计的相机图1：对于仿射光束法平差问题，标准联合优化（带内点迭代的Schur补光束法平差）无法从任意初始化（Red）得到有用的重构。相反，VarPro（蓝色）经常从随机开始中找到最佳的已知最佳值。本文展示了两种方法之间表面上的小差异如何引起非常不同的收敛特性。与基于变量投影（VarPro）的方法相比，具有缺失数据的方法的性能明显较差。变量投影最佳地消除了优化问题中的一些未知数，因此特别适用于下面描述的可分离非线性最小二乘问题。低秩矩阵分解是信号处理中出现的一类问题（例如，盲源分离），在机器学习中（例如，因子分析），而且在3D计算机视觉中获得例如仿射和非刚性重建。VarPro方法的成功在文献中经常被报道（特别是对于几何重构问题），但是据我们所知，缺乏对为什么可变投影在这种情况下如此有益的理解。本文的工作揭示了低秩矩阵分解的变投影方法与显式因子联合优化方法之间的关系本文揭示了联合优化算法在求解矩阵分解问题时存在固有的数值病态性，因而容易出现“失速”现象127128222！！§§§22§k·k虽然我们将专注于矩阵分解任务，但我们的分析也适用于更一般的可分离非线性最小二乘问题[10]。将可分离非线性最小二乘问题定义为极小化问题kG（u）v-z（u）k2（1）其中这两个向量是系统变量的非重叠子集，并且其中函数G：RpRsq和z：RpRsq通常在u中是非线性的。这类问题有一个特点，其残差矢量在至少一组系统参数中是线性的。由于这种普遍性，SNLS问题出现在工程和科学的各个部分[11]，从指数拟合[23]到化学，机械工程和医学成像。我们研究的一类特殊的SNLS问题是L2-范数秩加矩阵因子分解，它解决了+在4.3中，我们为VarPro提出了一个简单的可扩展策略，该策略可应用于大规模和潜在密集的SNLS问题，例如缺失数据的矩阵因子化和仿射束平差。相反，这项工作也有局限性：本文的研究范围仅限于L2-范数极小化。仍然有一些问题需要回答，例如为什么联合方法最终会出现在观察到的故障点。1.1. 相关工作变量投影（VarPro）首先由Golub和Pereyra [10]提出，用于一般的SNLS问题，并应用于主成分分析（即，矩阵因子化），Wiberg [30]。在过去的二十年里，计算机视觉和机器学习文献中出现了大量的低秩矩阵分解算法[9]，这些算法解决了（2）。 这些算法大多是基于空间有效的交替最小二乘算法，收敛性极差。布坎南和Fitzgills [6]引入了阻尼，阻尼新-最小？W？（UV>−M）？2（二）吨算法，但继续忽略Wiberg。 冈谷U， VF其中MRmn是观测矩阵，W罗文是权重矩阵，它通过执行逐元素（Hadamard）乘积来掩盖所有缺失元素，U2Rmr和V2Rnr是两个低秩因子，F是Frobenius范数。 如果使用均值向量，则V的最后一列被设置为all-1向量。是将（2）变换为（1）是很简单的。这个问题的分支在几个计算机视觉和机器学习应用中是可见的;使用仿射照相机的束调整[27]、使用基础形状或点轨迹基础函数的非刚性运动恢复结构[5]、光度立体假设环境光和朗伯表面[2]以及推荐系统[3]，仅举几例。本文的主要贡献如下：+ 在第3章中，我们对解决可分离非线性最小二乘（SNLS）问题的已知方法进行了广泛的回顾，即有 或 没 有 嵌 入 点 迭 代 （ EPI ） 和 变 量 投 影（VarPro）的联合优化。与以前的工作不同，我们显式地考虑Levenberg式阻尼的影响，没有它的替代品表现良好。+ 在4中，我们统一了上述方法，并表明联合方法和VarPro有效地共享相同的算法结构，但在细节上有所不同。+ 在5中，我们提供了经验分析，说明尽管两种方法的算法差异很小，但联合方法失败，而VarPro成功。和Deguchi [21]重新考虑了Wiberg，显示了其强收敛性，然后Okatani et al. [22]结合阻尼和Wiberg，在一些以前困难的问题上将收敛率提高到接近100%。与此同时，Gotardo这些rank-r最小化算法后来被统一[13]为来自变量投影的同一个根。各种论文指出了一些结构之间的相似性，联合优化和VarPro。鲁和Wedin [25]和Okatani等人。[22]指出了VarPro和联合优化的更新方程之间的相似性，但这仅限于没有阻尼的高斯-牛顿算法。Strelow [26]指出，VarPro在消除的参数上执行额外的最小化。Ceres求解器[1]是一种广泛使用的非线性优化库，也假设相同。我们发现，这些都不完全执行VarPro，并在某些地方消除阻尼在实施“纯”VarPro和扩大收敛盆地的关键作用关于VarPro的可扩展实现，Boumal et al.的RTRMC[4]在原则上是间接地解决VarPro约化问题，这就是我们所提出的。然而，他们的算法基于正则化问题，因此他们的算法对于机器学习推荐系统和其他随机矩阵表现良好，但在SfM问题上执行时存在数值不稳定性[13]，其中正则化器不是一个好主意，因为它本质上将先验放在Us和Vs上。我们提供了一个数值稳定的可扩展VarPro算法，该算法经过测试，在各种大小和密度的矩阵分解问题上效果良好。129pε二！2∆x21.2. 符号在本文中，我们使用以下定义-（8）的解由下式明确给出：¨Σ Σ¨kJk对于任意实薄矩阵A，xk= arg min？+pλI∆x¨∆x¨0k¨A−λ：=（A>A+λI）−1A>（3）A†：=（ A> A）−1 A>= A−0（4）JK=−λkIΣ†ΣK01>= −（J>J+λI）−Jε =J−λk ε。（九）2. Levenberg-Marquardt（LM）算法KKKKkkk我 们 首 先 说 明 Levenberg-Marquardt （ LM ） 算 法[19，20]，该算法广泛用于解决一般非线性最小二乘问题，并且它也构成了用于解决可分离非线性最小二乘（SNLS）问题的联合优化和变量投影（VarPro）方法LM是求解一般非线性最小二乘问题（SNLS是其中的一个子集）的迭代算法.旨在解决minkε（x）k2，（5）可 以 通 过 直 接 使 用 矩 阵 分 解 算 法 （ 例 如 QR 或Cholesky）或经由迭代方法（例如预条件共轭梯度（PCG））来求解（9）来实现计算矩阵xk3. 可分离非线性最小二乘问题在本节中，我们将详细介绍联合优化和变量投影（VarPro）方法。这些都是重新说明与一致的符号，让更容易x2方法之间的比较，并提供一个简单的-为我们在即将到来的第二次世界大战中的贡献而努力其中xRn是变量向量，ε：RnRs是残差向量。使用该算法获得的解最多保证是局部最小值。给定当前解决方案xk，感兴趣的数量是更新的数量xk，以改进xk，形成选项。我们还定义了以下特定于SNLS问题类型的术语ε（u，v）：=G（u）v-z（u）（10）xk+1=xk+xk。线性化残差产率ε（xk+1）=ε（xk+<$xk）<$εk+Jk<$xk，（6）Ju（u，v）：=ε（u，v）u=ε（u，v）d[G（u）]vdu−dz（u）中国（11）其中ε：=ε（x）和J ：=J（x）：=εε（x）/εx，Jv（u）：=n（u ）=G（u）k k k k k也就是x，k处的雅可比矩阵通过求解非正则化子问题arg minkεk+Jkxk2，（7）Qv（u）：= I − Jv（u）Jv（u）†。 （十三）3.1. 联合优化联合优化使用高斯-牛顿近似相对于变量u2Rp和v2Rq。的求解（7）假设成本是局部二次的，因此，xk+<$xk不一定会减少真正的目标kε（x）k2。LM通过添加具有阻尼参数λk2R的惩罚项来正则化更新，xk=arg minkεk+Jk（八）221302=kk k kkVKvkkVK未知数u和v被构造成x：=[u;v]2Rp+q，并应用LM（见§2）求解min ε（x）2：= min ε（u，v）.（十四）x2x=[u;v]22016年2月2日这种增广背后的关键直觉是，增加的项使得二次假设在x附近有效因此，用于联合优化的更新方程遵循（9），其中ε xk ：= [Juk;J vk] ，εk ：= ε （ uk ，vk） 和Jk=[Ju（uk，vk）;Jv（uk）] =[Juk;Jvk]。即K只. λk控制可信任“J> Ju +λkIJ>Jv#你好“#J>εk作为二次函数。为了详细说明，如果步骤λ xk改善了实际成本，则接受更新并且减小λk+1，使得（8）更接近（7）中的GN更新否则，更新被拒绝，λk增加，迫使算法ukkJ>JuKukkJ>Jv+λkIK克瓦希涅夫斯基u-J>εk（十五）更像是梯度下降。伪代码的一个简单的实现是在教学材料。Schur补约化系统Schur 补通常被建议有效地求解（15）（例如， [28]）：代替求解（p + q）<$（p+ q）系统矩阵，.1312−−ukVKukKukVKukKuk λkukKuk λkKKSλv−λkVKvkk）=的VV. J>（ I-JJ−λk）JΣ+ λI∆u=−J>（I−JJ−λk）ε关节（17）.u kvkvkukkkukvk vkkJ>（I−JvJ−λk）Ju+λkIuk=−J>（I−JvJ−0）εk=−J>εk关节+EPI（22）uk. J>（I-JkvkJ−0KΣ）J+λIuuk=−J>（I−JkvkJ−0）εuk=−J>ε中文（简体）图2：根据三种SNLS优化方法的关键方程在阻尼应用的地方明显的小差异引起非常不同的收敛特性。舒尔补将问题简化为两个子问题。因此，（15）简化为大小分别为pp和qq的LEM“J> J+λIJ>J#你好“#J>εk：=I-JkJvk（16）ukkkkJ>JuKukvkJ>Jv+λkI克瓦希涅夫斯基=−ukk0u=−。J>SJ+λI<$−1 J>Sε（17）（二十一）vk=−J−λk（εk+Ju利用Schur补，我们最终得到vkkuk=−.J> Sλ Ju +λkI Σ−1 J>εk。（二十二）更重要的是，Schur互补矩阵J>SλJu揭示了假设的局部二次模型ukk kuk3.3. 可变投影（VarPro）ukk k通过联合优化只在方面的最佳化，并将发挥核心作用§4。3.2. 嵌入点迭代（EPI）VarPro将在u和v上最小化（1）的问题简化为仅在u上求解非线性问题首先，观察给定u的v的最佳值是v（u）：= arg minkG（u）v−z（u）k2=G（u）<$z（u）. （二十三）v2嵌入点迭代（EPI）是一种新的迭代方法通过使用嵌套优化方法来加速经典光束法平差[17]：在计算标准后，将（23）插入（1）得到简化问题，minkε<$（u）k2：= minkε（u，v<$（u））k2（二十四）标准高斯-牛顿或LM更新，使用一组未知数（w.l.o.g.）v）在u固定的情况下进行优化 EPI衍生其2u2¨。†Σ¨2名称取决于它在光束法平差中的使用方式，其中v= min<$G（u）G（u）u-I z（u）<$. （二十五）表示3D点结构。由于v在每次迭代中相对于u的当前值进行优化，因此可以将其解释为变量投影的变体。因此，它有时被识别为实际VarPro [1]，但与VarPro的区别在于联合优化模型用于更新u（即使用（17）而不是（33））。（25）也可以被视为在简化子空间中定义的问题，因为我们可以将（25）中的残差重新表示为ε（u. I G（u）G（u）<$（G（u）vz（u））=. I−J（u）J（u）<$ε（u，v）=Qv（u）ε（u，v）（26）对于SNLS问题，由于残差ε（u，v）为对于任何v值，其中Q（u）是正交投影。在v中线性，最优的闭形式给定uk+1 可以计算为v在（13）中定义由于v是投影出来的，k+1：=uk+uk，仅根据u的模型是正交的，即，“不可知论者”，VKKVKKK132K2§v+J2vuvk+1 =arg min ε（uvk+1，v）k22扰动v。VarPro使用LM（参见 （25）解出（25），求约化残差ε（u）的雅可比矩阵。总=argminkG（uk+1）v−z（uk+1）k2（24）的导数读作=G（uk+1）<$z（uk+1）。（十九）J（u）：=dε（u）ε（u，v<$（u））dv<$（u）=ε（u，v<$（u））+udu杜杜杜注意，vk+1独立于V，因此（18）可以在此完全绕过（u，v（u））dv（u）Du（u，v（u）），（二十七）案子事实上，前一个kvk是最优的，kε（uk，v）k2意味着其中Ju和Jv是原始残差（10）的雅可比行列式。dv（u）/du可以通过使用以下公式解析导出：0 =J （u）>ε（u，v）=J>ε.（二十）（4）中伪逆矩阵的微分规则为vk kkvkk如下=J133⇡KukVKVKukKKKvK VKKKVKK⇤−−计算dv（u）/du及其近似值改善数值稳定性在 （33）、计算使用乘积规则指定v（u），JvJ†=Jv（J>Jv）−1J>很难kvkkv kkv k*如果 Jvk是病态的。一种解决方案是使用dv（ u） dDu=G（u）Duz（u）+G（u）<$dz（u）。（二十八）Du经济规模QR分解形成Jvk=JvQ，kJvR，k，其中JvQ，k形成col（Jvk）的正交基，并且通过注意G（u）=Jv（u）并应用伪逆矩阵的微分规则，我们得到以下结果：JvR，kJv J†是一个正方形上三角矩阵，然后计算=JvJ>.对于矩阵分解问题，kvkQ，kvQ，k结果（详见[14]）：Jv是块对角的，因此JvQ，k 可以获得dv（ u）<$通过对每个子块执行QR分解。du= −Jv（u）Ju（u，v（u））-（Jv（u）>Jv（u））−1d[Jv（u）]>ε（u）杜（二十九）4. 统一方法在本节中，我们将展示联合优化和将（29）插入（27）中，变量投影（VarPro）方法，分别是J=Q（u）J （u，v）t>d[Jv（u）]>ε（u）在§3中进行了详细的审查，这是完全相关的。 我们特别uv u-Jv（u）杜（三十）联合优化（Joint optimization，Joint optimiza）嵌入点迭代（联合+EPI）和可变投影与RW2近似（VarPro）。请注意，（29）（因此（30））包含一个包含一个sec-残差的二阶导数（通过d[Jv（u）]/du），因此已经提出了近似来减少4.1. 比较初始条件给定任意初始点（u，v）， 关节和计算成本。一种选择是使用粗ap-0 0近似dv（u）/du0，称为RW 3（遵循Ruhe和Wedin的分类法[25]）。其基本假设是u和v是独立的，并且所得到的方法本质上是块坐标方法（其对于矩阵分解问题显示出通常较差的性能[6，22，12，13]）。另一种近似，称为RW 2（Ruhe和Wedin算法2），丢弃了（29）中的第二项，导致dv（ u）<$Joint+EPI从（u0，v0）开始，而VarPro从（u0，v（u0））开始，因为简化的残差ε（u0）= ε（u0，v（u0））不包含v的初始值。为了表明这不是导致方法之间性能差异的主要原因，我们假设所有方法都是从（u0，v0）初始化的，其中v0=v（u0），使得初始条件相同。4.2. 比较更新方程du−Jv（u）Ju（u，v（u））（31）*根据（17）， （22），（33）我们现在处于...）Ju（u）<$Qv（u）Ju（u，v（u））.（三十二）尽管有命名约定，但RW2首先由Kaufman [18]提出，作为实现VarPro的有效方法。在过去的40年中，有显著的经验证据[18，25，11，12，13]表明RW 2-VarPro具有与完全导出的VarPro相似的收敛特性，同时受益于降低的计算复杂度。因此，我们将专注于VarPro的RW 2近似版本，并假设VarPro指的是RW 2-VarPro，除非另有说明。通过将近似雅可比矩阵从（32）馈送到（9）中，我们在迭代k处获得VarPro的更新方程：u=−（J>（I−JJ（t）J+λI）−1J>ε（33）哪里Juk：=Ju（uk，v（uk）），Jv：=Jv（uk）并且εk：= ε（uk，vk）= ε（uk，vk（uk））。上面的推导使用了Q2（uk）=（IJvJ†）2=I JvJ†。一旦u被更新，v以封闭形式被求解为对于新u是最优的。134VKVKK VKK−为了直接比较图1中的不同方法引起的对数据库的更新二、 我们还利用以下关系来强调各种更新规则之间的联系：J†=J−0，εk=（IJvJ−0）εk当vk=v（uk）时。使用（26）。在图中是明显的。2的SNLS的三种方法之间的唯一区别是，在实践中，阻尼参数λk的作用通常表现得非常不同：联合优化可以通过l.h.s.上的系统矩阵中的λk来阻尼λ vk在R.H.S.上的减少的残差使用EPI的联合优化在减少的残差中禁用了对Kvk的阻尼，并且VarPro完全禁用了对Kvk除了在每次迭代中如何确定Δ u之外，这三种算法在Δ v的更新方面也有所不同：联合优化使用局部线性模型来获得下一个Δ v，而Joint+EPI和VarPro在给定新值uk+1=uk+ Δuk的情况下完全优化v。特别是关于u的更新的简单观察具有几个重要的结果：1. 首先，他们确定VarPro for SNLS在派生和实现方面与（但不同）135§§§≥>vv- U（+λI）Uλv>¨U U¨2 −1>我从）更熟悉的联合优化方法结合舒尔补策略。因此，VarPro的数值实现在运行时间方面应该与常规联合优化相当。我们将在4.3中讨论这个问题。2. 其次，它允许我们推理联合优化和VarPro之间的差异在第五章中，我们分析了矩阵分解问题中的阻尼问题，以及它如何在联合优化中扭曲了更新方向3. 最后，统一这些算法并在它们之间进行选择是很简单的。总之，有两个独立的决定：（一）是否启用EPI？(ii)我们用λv表示的λ v的阻尼参数是否初始化为0（并且在迭代过程中保持为0）？这就产生了四种算法：Joint，Joint+EPI，VarPro，以及非线性系统上 不等阻尼（λu6= 0，λv= 0）的Joint优化方法。λv= 0λv= 0肾上腺素关闭联合（4%）（接头+零λv）（0%的百分比）肾上腺素打开关节+EPI(24%的百分比）VarPro(94%的百分比）表1：基于4的发现和表2中的修剪恐龙序列达到最佳最优的相应平均概率的方法分类。见图3）。对于矩阵因子化问题尤其如此，其中在使用联合优化时经常观察到目标的“平衬”。很容易假设在这种情况下，联合优化方法已经达到了次优的局部解（或至少是一个稳定点），但下面的分析将揭示，通常情况并非如此。回忆Fig.2，我们可以将更新公式写为如下：称为第四替代方案（也见表1）。的. J>（I-JJ−λv（三十五）这些算法中的步骤在[14]中给出。4.3. 一种可扩展的VarPro算法由于在实现方面，uvv）Ju+λuI<$u=b，其中λu>0，λv0，b是r.h. s之一图二、令Jv的奇异值分解由下式给出：Σ联合和VarPro的方法，它应该在理论上可以适应任何大规模的联合优化实现使用变量投影（VarPro）。大型⇥Jv=U˜⇤Σ0 第五章（36）和密集的问题，使用共轭梯度为基础的算法，其中σ1， . .... . . 你 好 。 ，σq）和U_n=nu_n（J_n）。然后，间接求解（33）的算法将是优选的。J−λv>>1- 1>2−1>> >然而，仅凭这一点可能无法复制VarPro对于矩阵分解问题，即使Boumal et al.s RTRMC [4]使用预处理的共轭梯度间接解决了VarPro问题v=JvJv+λvIJv=V（λ v+λvI） VJv=V（λ v+λvI） <$U。（三十七）因此，委员会认为，ent求解器，它在几个SfM数据集上表现不佳[13]。我们认为，这是由于这些数据集的病态性质，因此主要-I−JvJ−λv=HU，Uihi>U，U.2 2 −1>vΣ保持一定程度的数值稳定性至关重要，=U<$U<$>+UI−<$2（<$2+λvI）−1U在这类问题上扩大趋同范围我们的策略是解决一个数值上更-=UU>+U2U，（38）第3.3节中的稳定QR分解约化系统，其中，λv被定义为dia g（σ1， . .... . . 你 好 。 ，σ<$q），其中RES求解器[24]，这是一种共轭梯度型方法为解决p俄克拉何马州 ：=λv/（σ2+λv），i=1， . .... . . 你好 。 ，q. 注意到（35）也是一阶最优性条件，minkAx −bk2（34）x2英寸。˜联系我们其中，A是对称矩阵，其可以是定的、不定的，minüU+Uλv朱乌乌 2 +λukuk-2个B单位单一的或单数的。我们稍后将证明VarPro的收敛盆地（使用直接求解器）主要用于我们的仿射光束法平差策略，其可以是公式：¨¨=最小值阿鲁Σ联系我们联系我们¨2¨朱乌乌2U>阿鲁136+λukuk2−2b>u（三十九）这是一个矩阵分解问题。5. 提前停止联合优化在本节中，我们将概述为什么联合优化易于提前停止（或停止）SNLS（例如，请参见因为n>=0。（39）揭示了最小二乘目标w.r.t.算法所使用的函数。如果λv=0，即v上的信赖域阻尼被停用，则前导二次项仅在J >的零空间中对目标建模。137⇥⇡vv⌧⇡⇡§⌧瓦尔普罗v1>⇡！1U U⌧20151050 100 200 300 400 50051015202530355101520253035照相机ID(a) VarPro（最优）16014012010080604020051015202530355101520253035照相机ID(b) 关节+EPI（失效）160140120100806040200成功迭代次数图3：每个算法的收敛图。对于这个例子，VarPro收敛到已知的最佳值（4。23 103），而接头和接头+EPI都表现出平衬行为。具有不相等阻尼的关节在最小值不好时迅速终止。如果所有的奇异值σi与λv的当前值相比都相对较大，则σi0，并且线性模型中（以及更新方向上）的扰动可以忽略。相反，如果λv> 0，且有一个或多个奇异值σi对某个i（接近）为零，则σi<$1。在图4：投影框架中修剪恐龙（b）示出了当它未能达到最佳已知最优值4时，一些相邻相机（例如，在ID 1至8之间）紧密地对准在一起。23岁10岁3.导致¨ ¨k<$vvarprok≥σ<$2<$Jv（ε+Ju <$u）<$，其中， =maxiσi。因此，我们得到，kvjoint k/ kvvarprokσ<$2/λv1underour p-极限λ，我们有一个v eλv=I，并且由于[，]是一个旋转矩阵，（39）退化为u的块坐标方法，已知该方法在矩阵分解问题上表现不佳[22，13]）。我们可以在下面集中分析块坐标方法，因为如果σiλv仅对某些i，则dia g（1， . .... . . 你 好 。 、1、0、 . .... . . 你 好 。 ，0）和求解（39）基本上对应于块坐标方法。现在我们假设Jv是秩亏的。 为简单起见，我们将选项。 因此，更新后的BMv关节将比该更新是由Varpro公司提供的。在更一般的设置与Jv是接近奇异的，而不是接近零矩阵，我们得到，在某些方向上，Jv联合将比Jvvarpro缺乏更新的双曲正切联合（在某些方向上）反映在局部二次模型（39）中，B.R. U：减少残留物完全是B.R. U的责任。注意，如果Jv远不是奇异的，则J−λv接近于J†，并且λ v联合λvvarpro。因此，在这种情况下，做一个更强有力的假设，即Jv0（因此σiλv和λvI）的第10条。为了说明一个直观的想法，我们专注于更新分别用VarPro和Joint优化方法在各自的线性系统中计算了最优解.请注意，对于VarPro和Joint+EPI，这些更新实际上并不用于更新v，因为EPI负责更新v，但它们在确定更新u时仍起着关键作用，因为u和v在SNLS问题中是相关的。如（18）中所写，联合优化算法族计算VarPro优化的行为类似。为了了解这如何影响算法性能，我们求助于仿射光束法平差的示例，其中u是一组相机参数，v是一组3D点。对于这个问题，当对应于3D点的一束射线几乎共线时，可能会出现近奇异J v。在这样的情况下，联合优化子模型在深度方向上固定了点更新（pointupdate），并且因此这对相机参数施加了更多负担以减少目标。另一方面，VarPro允许不受约束的点更新BNOV，允许相机更新BNOU进行ε v=−J−λv（ε+Ju）u）更多冒险的举动接头V并且因此uvuλv1英寸6. 实验结果为了验证我们在§4和§5中的分析，我们进行了两次前-kv联合kλ<$Jv（ε+Ju<$u）<$实验解决仿射光束法平差，可以矩阵分解问题[27]。它有假设σiλv对所有i。另一方面，我们在4中的分析表明，VarPro对v没有阻尼，因此其相应的更新vv为经验表明[15]，所获得的仿射解可用于引导投影束调整。ε v=−J<$（ε+Ju）在第一个实验中，我们测试了我们的VarPro-MINRES联合优化策略（Joint optimization）， 联合优化-联合关节+EPI具有不等阻尼VarPro的接头log10（成本）照相机ID照相机IDvu138N§数据集Fn缺失（%）联合关节+EPIVarProVarPro-MinRes*蓝色泰迪熊（修剪）19682780.7十（238）二十（一百五十五）88（22.3）76（21.9）走廊1173750.240（8.71）4（14.8）一百（1.07）100（0.78）恐龙（修剪）3631976.94（5.95）二十四（9.38）94（1.55）九十九（3.96）包括离群值的36498390.80（28.6）0（62.1）100（13.9）36（38.9）房子1067257.744（4.90）8（9.71）100（0.30）100（0.41）道路场景#471115047.144（1.88）三十二（三点）100（0.16）100（0.17）斯德哥尔摩市政厅（修剪）43100018.092（45.1）48（35.7）100（22.8）100（3.12）Wilshire19041160.738（409）94（9.90）一百（7.64）一百（1.96）瓢虫（骨架）49777691.60（77.3）0（155）50（49.7）0（155）特拉法加广场（骨架）211131584.70（76.2）0（160）100（14.7）100（56.4）杜布罗夫尼克（骨架）162210676.3三十八（一百五十九）0（346）100（23.6）100（32.9）威尼斯（骨架）526405389.60（913） 0（1495）八十（一百二十三）六十（329）表2：各种数据集上的仿射光束平差的实验结果。对于每个数据集和每个算法，收敛到该数据集的最佳已知最优值的运行的百分比在括号内以秒为单位报告相应的中值运行时间。* 我们的VarPro-MINRES实现效率相对较低，而其他算法基于我们的Ceres Solver [1]库的修补版本。在各种SfM数据集上使用嵌入点迭代（Joint+EPI）和可变投影（VarPro）。VarPro-MINRES在MAT-LAB中实现的效率较低，而其他方法在Ceres Solver框架中实现[1]。由于我们的代码分析表明，当前的Ceres版本实现了Joint+EPI而不是VarPro，因此我们根据§4中的统一 工 作 修 补 了 Ceres 以 正 确 支 持 VarPro （ 没 有MINRES）。对于每个算法的每次运行，我们从（0，1）中采样u 0的每个元素，然后使用u0生成v0=v（u0），以确保所有算法的初始条件相等。在每个数据集上，我们运行每个算法-rithm进行固定次数，并报告达到数据集最佳已知最优值的运行分数。对于某些数据集，最佳最优值是已知的（例如恐龙和修剪恐龙），但对于其他数据集，我们使用了在所有实现算法的所有运行中观察到的最佳目标值。 我们将函数容差设置为10−9和成功迭代的最大次数，300.对于VarPro-MINRES，我们将相对容差设置为10−6，内部迭代的最大次数设置为300。图中报告的目标值3和图4是从（2）计算的值的一半表2显示VarPro-MINRES基本上保留了标准VarPro所观察到的大范围收敛。请注意，它对较大稀疏数据集的速度较慢可能是由于其相对低效的实现。在第二个实验中，我们从随机起点观察了4中描述的四种算法在修剪恐龙数据集[6]上的行为这个圆形运动衍生的序列由36个合理的弱透视相机和319个内点轨迹组成。76.9%的元件缺失，并表现出带状闭塞模式，没有环路闭合。表1显示，使用139§EPI本身提高了成功率，但必须伴随着阻尼因子λv的去除（即切换到VarPro），以显著提高算法的性能。图3示出了由Joint和Joint+EPI共享的典型“失速”行为。在文献[5]中，我们提出了在仿射光束法平差中，当一批摄影机射线几乎共线时， 这一说法在图中得到验证。图4和图1，其示出了一些仿射相机方向（例如，从ID 1到ID 8的一组摄像机）在基于联合优化的算法的故障点处非常小。在VarPro达到的最佳值中没有观察到射线的这种共线对准。7. 结论在本文中，我们表明，联合优化和变量投影（VarPro），这是两个明显非常不同的方法解决可分离的非线性最小二乘问题，可以统一。联合优化与VarPro最大的区别在于VarPro方法中的非平衡信赖域假设。这两种方法之间的联系表明，VarPro原则上可以像标准联合优化一样有效地实现，这使得VarPro可以在比文献报道的数据集大得多的数据集上得到证明。我们还解决了为什么VarPro在计算机视觉中某些重要问题类别的成功率比联合优化高得多的问题。致 谢 本 工 作 得 到 了 Microsoft 和 Toshiba ResearchEurope的支持。我们还感谢Roberto Cipolla提供额外的资金支持。140引用[1] S. Agarwal，K. Mierle及其他 谷神星解算器网址：//ceres-solver.org，2014年。 二四八[2] P. N. Belhumeur和D.克里格曼在所有可能的照明条件下，物体的图像集是什么在1996年IEEE计算机视觉和模式识别会议（CVPR），第270-277页，1996年6月。2[3] J. Bennett和S.朗宁Netflix奖在2007年KDD杯和研讨会论文集，第3-6页2[4] N. Boumal和P. - A. Absil RTRMC：一种低秩矩阵完备化的 黎曼 信赖 域方 法。 神经 信息 处理 系统 进展24（NIPS 2011），第406-414页。2011. 二、六[5] C. Bregler，A. Hertzmann和H.比尔曼从图像流中恢复非刚性3D形状。2000年IEEE计算机视觉和模式识别会议（CVPR），第2卷，第690-696页，2000年。2[6] A. M. Buchanan和A.W. 菲茨吉本缺失数据下矩阵分解的阻尼牛顿在2005年IEEE计算机视觉和模式识别会议（CVPR），第2卷，第316-322页，2005年。二、五、八[7] T. Cashman和A. W.菲茨吉本海豚是什么形状的？从2D图像构建3D可变形模型。IEEE Transactions on PatternAnalysis and Machine Inteligence，35（1）：232-244，2013. 1[8] T. F. Chan和S.埃塞多格鲁全变差正则化L1函数逼近问题.SIAM Journal on Ap-plied Mathematics，65（5）：1817-1837，2004. 1[9] 陈平。子空间上的优化算法：再论低秩矩阵中的缺失数据问题。国际计算机视觉杂志（IJCV），80（1）：125-142，2008。2[10] G. H. Golub和V.佩雷拉伪逆的微分与变量分离的非线性最 小 二 乘 问 题 . SIAM Journal on Numerical Analysis（SINUM），10（2）：413-432，1973. 2[11] G. H. Golub和V.佩雷拉可分离非线性最小二乘：变量投影法及其应用。在Proceedings of Inverse Problems，第1-26页，2002年。二、五[12] P. F. Gotardo和A. M.马丁内斯计算相机的平滑时间轨迹和从具有遮挡的运动中的结构中的可变形形状。IEEETransactions on Pattern Analysis and Machine Intelligence（PAMI），33（10）：2051 二、五[13] J. H. Hong和A.W. 菲茨吉本 矩阵分解的秘密：近似，数值，流形优化和随机重启。2015年IEEE国际计算机视觉会议（ICCV），第4130-4138页。二五六七[14] J. H.洪角，澳-地 Zach和A. W. 菲茨吉本 重新审视可分离非线性最小二乘问题的变量投影方法：补充文件，2017年。https://github.com/jhh37/varpro网站。五、六[15] J. H.洪角，澳-地Zach，A. W. Fitzgienic和R.西波拉用可变投影法进行任意初始化的投影光束法平差。第14届欧洲计算机视觉会议（ECCV），第477-493页，2016年。7[16] H.石川具有凸先验的马尔可夫随机场的精确优化。IEEE Transactions on Pattern Analysis和Machine Intelligence（PAMI），25（10）：1333 -1336，2003。1[17] Y. 郑，D.Nister，D.斯蒂利河Szeliski和我S. 奎恩推进光束法平差的现代方法。2010年IEEE计算机视觉和模式识别会议（CVPR），第1474-1481页，2010年。4[18] L.考夫曼解可分离非线性最小二乘问题的一种变量投影法。BIT Numerical Mathematics ，15 （1 ）： 49-57，1975. 5[19] K.莱文伯格用最小二乘求解某些非线性问题的一种方法。Quarterly of Applied Math-matics，2（2）：164-168，1944. 3[20] D.马夸特非线性参数的最小二乘估计算法。Journal ofthe Society for Industrial and Applied Mathematics ， 11（2）：431-441
我的内容管理
展开
