英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
黎曼高斯-牛顿方法的收敛性分析及其与几何条件数的关系
Paul Breiding，Nick Vannieuwenhoven
Max-Planck-Institute for Mathematics in the Sciences，Leipzig，Germany
KU Leuven，Department of Computer Science，Leuven，Belgium
摘要：我们得到了在局部收敛中出现的乘法常数的估计．黎曼高斯-牛顿法最小二乘问题的结果．并将它们与Buuml;rgisse和Cucker(2013)的几何条件数联系起来．
关键词：黎曼高斯-牛顿法；收敛分析；几何条件数；CPD
Convergence analysis of Riemannian Gauss–Newton methods and its connection with the geometric condition number
Paul Breiding，Nick Vannieuwenhoven
Max-Planck-Institute for Mathematics in the Sciences，Leipzig，Germany
KU Leuven，Department of Computer Science，Leuven，Belgium
Abstract：We obtain estimates of the multiplicative constants appearing in local convergence results of the Riemannian Gauss–Newton method for least squares problems on manifolds and relate them to the geometric condition number of Buuml;rgisser and Cucker (2013)．
Key words: Riemannian Gauss–Newton method；Convergence analysis；Geometric condition number；CPD
介绍
科学和工程中的许多问题是参数识别问题 （）．这里有一个参数域和一个函数．给定的图像中的一个点，要求识别参数使得；注意可能有几个这样的参数．例如，计算给定矩阵的，，，极坐标，奇异值和特征分解就是这样的例子．在其他情况下，我们有张量
，需要计算，，块项，层次或张量列分解[1]．
如果应识别其参数的对象来源于应用程序，那么说明．尽管如此，在这种情况下，寻找参数，是尽可能接近的，例如，在欧几里得范数中．这可以表示为一个非线性最小二乘问题
． （1）
在这里，我们处理的函数，可微性是保证的，因此可以使用连续的优化方法来解决（1）．具体地，我们假设是的一个光滑嵌入子流形，并且是上的一个光滑函数[3，第一章和第二章]．因此，（1）是可使用例如黎曼高斯 - 牛顿（）方法来解决的黎曼优化问题[4]；详情请参阅下一节．
对扰动的敏感性可能会影响这些方法的性能．用“”表示流形和之间的光滑映射，用表示流形在处的切线空间．我们从[5，第14．3节]回想到，几何条件数表示输出对输入扰动的灵敏度为一阶，作为微分算子的谱范数；即．在的情况下，几何条件数如下导出．假定存在一个的开邻域，使得是一个具有的光滑流形．由于是流形之间的光滑映射，如果是内射的，则满足流形的反函数定理[3，定理4．5]，并且存在一个唯一的反函数，其导数满足．因此，参数的几何条件数是
， （2）
其中是线性算子的第个最大奇异值．如果导数不是内射的，则条件数定义为
．
在本文中，我们证明（2）中参数的条件数自然地出现在方法的收敛估计的乘法常数中．我们的主要贡献是定理1．
黎曼高斯 - 牛顿法
回想一下，黎曼流形（）是一个光滑的流形，其中对于每一个，切线空间有随光滑变化的内积；见[3，第13章]．的零元素由运算式表示．由于我们只涉及嵌入子流形，我们取等于上的标准内积．下面我们删除下标“”．诱导范数是．流形的切线束是光滑向量束．
在本文的其余部分，我们让是一个嵌入的子流形，其中，配备了从继承的标准黎曼度量．黎曼优化方法可应用于下列最小二乘函数的最小化
（3）
其中．
回想一下，牛顿最小化的方法包括选择一个，然后根据以下过程在中生成一个迭代序列：
和； （4）
其中：是黎曼梯度，是黎曼；详情请参阅[4，第6章]． 映射是收回运算符．
定义1（收回[4，6]）收回是一个来自开放子集的映射，对于每一个都满足下列所有属性：
1．；
2． 包含的邻域，使得限制平滑；
3． 满足所有的局部刚性条件．
我们令是在步骤处的收回．
收回是指数映射的一阶近似[4]；下列的结果是众所周知的．
引理1．设是收回．那么对于所有的存在一些，这样对于所有具有的，都有．
如[4，第8．4．1节]所述，最小化的方法是用高斯-牛顿近似代替牛顿过程( 4 )中的而获得的；这里表示有界线性算子相对于内积的伴随．注意，可以获得更新方向的明确表达式．黎曼梯度是
； （5）
参见[4，第8．4．1节]如果是内射的，那么（4）中系统的黎曼型用高斯-牛顿近似代替的解是
．
主要结果：RGN方法的收敛性分析
我们在本节中证明方法的收敛速度和半径都受到局部极小值处的条件数量的影响．在的情况下，对于某些固定的，我们有．因此，
，从而下一个定理能将几何条件数（2）与求解最小二乘问题（3）的方法的收敛性联系起来．
备注1．方法只是局部收敛的．通过添加一个全球化策略[ 4，7 ]如线路搜索或信任区域方案，获得了实用的方法．这些战略的目标是在保持局部收敛速度的同时，保证全局收敛的充分下降．在主要定理中，我们提出了不考虑全球化策略的分析，从而集中论述了证明的主要思想．在信任区域方案的情况下，扩展证明的通常方法包括证明在接近局部极小值的情况下，无约束牛顿总是包含在信任区域中并因此被选择的．如果起始点足够接近局部极小值，这将是正确的．然后，局部收敛速度将与不使用信任区域方案时相同．
在本节的其余部分中，令表示以为中心半径为的球． 以下是本文的主要定理．
定理1．假设是（3）中目标函数的局部最小值，其中是内射的．令
．于是，存在，使得对于所有的，存在取决于
和的通用常数，以便以下成立．
1．（线性收敛）：如果，则对于所有且
，
方法都生成一个序列线性收敛到．事实上，
．
2．（二次收敛）：如果是目标函数的一个零解，那么对于所有的且
，
方法都产生一个序列二次收敛到．事实上，
．
备注2．收敛的顺序也可以由[4，定理8．2．1]确定．然而，内在的乘法常数并不是在那里导出
的，因为它们的分析建立在取决于所选图表的坐标表达式上；因此它们只能导出图表相关的乘法常数．
在下文中，让表示在线性子空间上的正交投影．回想一下[8，第2节]中的下一个引理，这是我们在定理1的证明中所需要的．
引理2．设是一个平滑函数，其中．那么存在常数和，使得对于所有，我们有，其中
和．
我们现在可以证明定理1．
证明定理1．我们从一些一般的考虑开始：在引理1中，我们选择足够小的，使得它适用于所有．设，那么，根据收回算子存在一个恒定的，因此对于所有的，对于每一个我们有
． （6）
通过引理2分别应用光滑函数和，并使用（的导数）的光滑性，我们可以看到存在常数，因此对于所有的，我们有
（7）
其中 ，
和
（8）
其中．
而且，我们定义了常数
． （9）
我们选择一个常数，取决于和，满足
（10）
其中．
其余的证明是归纳．假设应用于起始点的方法生成了点的序列．首先，我们证明是内射的，从而定义了更新方向，因此被定义．之后，我们证明上的有效边界．为了避免下标，令和．
通过归纳，我们可以假设；事实上，的基本情况是非常正确的，我们将在证明的最后证明它也适用于，从而完成归纳．因此，．
令表示相对于和上的标准基的的矩阵．令为其（紧凑）奇异值分解（），其中和具有正交列，跨和的列是包含奇异值的对角矩阵．然后，关于标准基的矩阵是，即的
假逆，．同样，令表示的矩阵，令其为．
通过假设，是内射的，因此我们有．的矩阵是，对于也是类似的．那么，根据（9）中的定义，我们有
， （11）
因此，因为和的定义．从的摄动引理可以得出，我们还得到
，最后的不等式是假设．它遵循
， （12）
所以确实是内射的．这表明的更新方向是明确的．
它仍然要证明上的边界．首先我们证明，这样收回会满足（6）．假设是（3）的局部最小值，所以从（5）我们得到
．由[2，第三章，定理1．2（9）]和是内射的假设，我们有，从中我们得出．令．从（7）有，
， （13）
以便
．
（14）
从定理[2，第三章，定理3．9]我们可以得到
， （15）
最后一步是因为（11）和（12）．对于正交投影仪，使用，假设，（12），（15）和上的边界在（7）中，由（14）可以得出
． （16）
由定义和假设，我们有，所以由（16）有，
． （17）
使用（10）中上的第三个界限，我们有
，
当插入（17）时产生．
从前面的讨论，我们得出结论（6）适用于，所以有
， （18）
让，我们使用，从式（13）推导出
，
其中倒数第二个等式是由（8）得出的，并且在最后一行中，我们使用了三角不等式以及和从（7）和（8）开始的边界．结合（15）和（12）得出
． （19）
注意，我们选择了足够大的常量，使得．将（19）和（17）插入（18）得到第一个边界．
对于第二个断言，我们有另外的假设，是目标函数的零点，从（19）我们得到．从（14）我们得到，这样我们可以绑定到
其中的不等式是由不等式和的正交投影机的事实所决定的．如前所述，将和的这些边界插入（18）并利用，获得第二个边界．
一位评论者问，上述定理中，导数的内射性假设是多么的重要．简单的回答是，在实践中这通常是一个非常薄弱的假设．首先，我们需要一个引理．
引理3．令是一个嵌入流形，其投射变化是一个光滑的投射变化，令是一个正则映射．令表示变化，它是图像的闭包．如果维数满足
，欧氏拓扑中，点
是欧氏拓扑中的稠密子集．
证明．这本质上是对[9，定理11．12]的重述．
下面的命题表明，在引理3的假设下，定理1中的局部优化器对正量度的一组输入（以为单位）具有内射导数．
命题2．令和如引理3所示．假设我们有等式．令
是点在上所有最接近的近似的集合，即，位于中．于是，具有正度量，即它在欧几里德拓扑中是开放的．此外，是中的欧几里德密度．
证明．设是纤维的维度是严格为正的轨迹，即
．根据[9，定理11．12] 是一个闭集．命题的最后一个要求也是这个定理的必然结果，并且假设泛型纤维是维的．
它仍然表明第一个要求．令为位于集的奇异轨迹上的点的
闭集子集．设，其中上划线表示拓扑中的闭包．请注意，．
令．由于导数是内射的，所以的开放邻域和的开放邻域之间存在局部微分同胚性．通过限制邻域，可以假设的欧几里得闭包含在的光滑轨迹中，并且包含在中．取一个不与相交的的管状邻域，设为其高度；注意，因为的闭包不包含的奇点．那么在正半径为的中存在一个以为中心的开口球，其与的交点包含在中．通过构造．从三角不等式中可以看出，上的最近点到的任何一点都包含在中．从开始，由于存在，因此对于所有的都有．
数值实验
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[23809]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
