（计算数学专业论文）procrustes问题的若干研究.pdf

摘要 摘要 本文主要研究正交约束下的非均衡p r o c r u s t e s 问题：给定矩阵a 7 妒n ，b 7 妒“，几 k ，使得i i a q b i i f 最小化，其中q 7 q = i k ，q 7 护“全 文共分为四章 第一章是绪论部分，主要介绍了正交约束下的p r o c r u s t e sf 司题及其现状 第二章主要研究了正交约束下的p r o c r u s t e s 问题的解的性质给出了均 衡p r o c r u s t e s 问题的解的结构与性质；分析了非均衡p r o c r u s t e s i n 题的解的性质及 其满足的条件 第三章我们在l s q e i h q 题的投影算法的基础上构造了非均衡p r o c r u s t e s 问题 的持续投影算法分析了持续投影算法的计算过程可能出现的问题及其收敛性 第四章给出了丰富的数值例子 关键词：p r o c r u s t e s 问题，最小二乘问题，投影算法 a b s t t a c t a b s t r a c t i n _ t h i sp a p e r , w ec o n s i d e rt h eu n b a l a n c e dp r o c r u s t e sp r o b l e mw i t ho r t h o g o n a l c o n s 仃a i n t ：g i v e nm a t r i xa 冗”。”a n db 冗“。，礼 南，m i n i m i z et h er e s i d u a l j i a q b 胁o v e r t h es t e i f e lm a n i f o l do f o r t h o n o r m a lm a t r i c e s t h ep a p e rc o n s i s t so f f o u rc h a p t e r s i nt h ef i r s tc h a p t e r , w eg i v es o m ei n t r o d u c t i o n so fp r o c r u s t e sp r o b l e m i nt h es e c o n dc h a p t e r , w ei n v e s t i g a t ep r o p e r t i e so f s o l u t i o nf o rp r o c r u s t e sp r o b l e m w i t ho r t h o n o r m a lc o n s t r a i n t s w ep r e s e n ts t r u c t u r e sa n dp r o p e r t i e so fs o l u t i o nf o rh a l a n c e dp r o c r u s t e sp r o b l e m ；a n dw ea l s oa n a l y z ep r o p e r t i e sa n dc o n d i t i o n so fs o l u t i o n f o ru n b a l a n c e dp r o c r u s t e sp r o b l e m i nt h et h i r dc h a p t e r , w ep r e s e n tas u c c e s s i v ep r o j e c t i o nm e t h o d ( s p m ) f o rs o l v i n g u n b a l a n c e dp r o c r u s t e sp r o b l e m ，w h i c hb a s eu p o np r o j e c t i o nm e t h o df o rs o l v i n gp r o b - l e m sl s q ea n db a l a n c e dp r o c r u s t e sp r o b l e m s a n dw ea l s od i s c u s sc o m p u t a t i o n a l i s s u e sa n dc o n v e r g e n c eo fs p m i nt h el a s tc h a p t e r , w et a l ka b o u tn u m e r i c a lr e s u l t sf o rs p m k e y w o r d s ：p r o c r u s t e sp r o b l e m ，l e a s ts q u a r e sp r o b l e m s ，p r o j e c t i o nm e t h o d i i 致谢 致谢 首先感谢张振跃老师将我带入矩阵计算这一学术领域，感谢张老师在学术方 面的指导，在他的耐心指导下我完成了一篇学术论文和这篇毕业论文感谢张老 师对我的谆谆教诲 感谢方敏，王靖，李旭东，裘渔洋等师兄的指导和关心；感谢一起参加讨论班 的方腊，卢俊峰，李丽敏，赵凌潇，何孝睿等师弟师妹在讨论班上的交流，使我有 了更加宽广的视野 感谢杨起帆，杨启帆，方道元，管志成，卢兴江等数学系的老师，感谢他们在我 在浙大求学期间学习上的指导以及生活上无私的帮助还要感谢浙江大学的朋友 们无私的帮助有了他们的指导和帮助，我才能顺利的度过这六年半的浙大求学 生涯 最后还要感谢远在家乡的家人，感谢他们这么多年来的抚养与支持，是他们 默默的支持和谆谆教诲使我少走了很多弯路 i l l 第一章绪论 第一章绪论 1 1 p r o c r u s t e s 问题的简介 ，p r o c r u s t e s 这个名字的来自于希腊神话p r o c r u s t e s 是n e s e u s * 话中的一个恶 棍，他专门在通往雅典的路上抢劫路人，并强迫他们躺在铁床上，如果铁床跟哪个 受害者不适合，那么p r o c r u s t e s 将截断或者拉长他们的四肢使得铁床跟这个受害 者正好合适 p r o c r u s t e s 问题就是求一个矩阵q ，使得a q 尽可能的接近日，其中矩 阵a 和b 是给定的，即是求解以下问题： ，( q ) 2 呼i i a q b i i f 其中l i f ：为f r o b e n i u s 范数若给矩阵q 加上约束条件，那么问题( 1 1 ) 就成了约束 下的p r o c r u s t e s 问题，定义舻蛐中的正交矩阵集为正交s t i e f e l 流形： s = q 缈蚰：q r q = ，)( 1 2 ) 若约束条件为q 5 ，则问题( 1 1 ) 即为本文研究的正交约束下的p m c n j s t e s 问 题：给定矩阵a 冗”“，b 7 已”“，其中m k ，求标准正交矩阵q 7 妒。使得 它是如下约束问题： m i nl i a q b 临 q t q = i 。 。4( 1 3 ) 的解 一般来说，7 7 l n 如果m n ，我们很容易通过q r 分解降低原问题的规模 不失一般性，我们假设矩阵a 是n 阶方阵，问题( 1 3 ) 就可以写成如下形式： 。m ，。i n ：ji i a q 一圳刍，a 缈“，b 冗删，n ( 1 - 4 ) 当= 扎时，我们称( 1 4 ) 为均衡p r o c r u s t e s 问题；当 礼时，我们称( 1 4 ) 为非均 衡p r o c r u s t e s 问题 第一章绪论 均衡p r o c r u s t e s 分析以及相关的广义p r o c r u s t e s 分析在测地学，地理信息系 统( g 1 s ) 等方面有着广泛的应用( 文献 1 0 9 对于均衡p r o c r u s t e s 问题，在文献 4 ； 6 中，通过矩阵a t b 的奇异值分解+ 或极分解，我们可以得到它的显式解 下面我们来了解一下非均衡p r o c r u s t e s l 司题的现状 1 2 非均衡p r o c r u s t e s 问题的现状 非均衡p r o c r u s t e s 问题看起来并不那么简单，它要比均衡p r o c r u s t e s 问题难得 多首先，如果a 是秩亏损的，也就是说，r = r a n k ( a ) n ，那么由a 的奇异值分 解a = 珥，妒，我们有 a q b i 曙= l i ，妒q 一呼b i 悟+ 1 i ( 哪) t b l | ； 其中畔为珥的正交补因此问题( 1 4 ) 可以写成如下形式 。糌恤一殍b i i 记x = v 7 0 ，于是有i l x l i 1 ，但这并不意味着原问题等价于如下约束下的最小 二乘问题： m i ! 。i i r , r x 一呼b i i f 其次，l e l d 6 n 与h p a r k 在文【3 】中给出了非均衡p r o c r u s t e s 问题的局部( 全 局) 最优解的必要条件和充分条件但是到目前为止，非均衡p r o c r u s t e s 问题 的全局最优解的充要条件并没有给出，或许它的全局最优解的充要条件并 不存在就目前而言，非均衡p r o c r u s t e s i n 题的解析解仍然是一个有待解决的 问题假设q + 是非均衡p r o c r u s t e s i h q 题的解，那么我们可以把a q + 看出是b 在集 合f x ：x = a q ，q 冗“ 上的投影，很显然这个集合不是一个凸集一般来 说、在非凸集上的投影并不唯一这也是求解非均衡p r o c r u s t e s 问题的困难所在 最后求解非均衡p r o c r u s t e s 问题的有效算法的需求依然没有得到满足g r e e n 与g o e r s 在文【9 】中，以及j m f t e nb e r g e 与d l k n o l 在文【1 1 中给出求解非均 衡p r o c r u s t e s 问题的迭代算法，该迭代算法通过求解一系列的n 阶均衡p r o c r u s t e s 问题，这些均衡p r o c r u s t e s i h q 题通过把矩阵b 扩充成n 阶矩阵而成文献 9 ；11 】给出 + 诅文【6 】中，奇异值分解被称为e c k a n y o u n g 分解 一2 一 第一章绪论 了以下的算法： 算法1 给定a 7 4 “，b t 己m ”，n k ，求标准正交阵q 冗“。使 得i i a q b i i ，最小 1 初始化亩，使得【b ，亩】为方阵 2 迭代求解，直到收敛 2 1 求解均衡p r o c r u s t e s 问题： 一m g i n ：，i i a g 一限驯f - 其最优解g 可由月旧，司的奇异值分解或极分解表出 2 2 把g 分成两块：g = 【q ，卸然后令宫= a h 文【9 】与文 1 1 】的不同之处在于矩阵_ 8 的初始化方式不同在文 9 】中，g r e e n 与g o e r s 通过在矩阵b 后面添加n k 列零向量或随机向量的方式进行扩充 而j m f t e nb e r g e 与d l k n o l 则通过把矩阵b 扩充成 b ，a 司，其中矩阵e 由矩 阵a 下a 的最小的n k 个特征值所对应的特征向量组成当礼非常大或者礼k 时，这是不可接受的而且这两个算法可能不收敛或者收敛于局部最优解h p a r k 毛e 文 5 】中给出了一个上述算法不收敛的例子 h p a r k 在文【5 】中给出了基于一系列的2 2 矩阵的奇异值分解的迭代算法 算法i i 给定a = a l ，a 。】冗”“，b = b ，b e 7 p 妯并j l n 府， 求标准正交阵q = q l ，q k 】冗“。使得i i a q b i l f 最小 1 u = 厶，v = 厶 2 迭代求解，直到收敛为止 3 i = 1 ：k 3 1 j = i + l ：七 计算 n ；】7 慨 的奇异值分解 n 。a j 丁 b ib j 】= x z x ： 【a ia j 】= a ia j x l ， b i _ 慨b j x 2 k - ( u iu j x t ， v i 】- v iv j x 2 一t 一 第一章绪论 求解r a ，i n 1 l b ；a j x 一良 。 ? 。z = j 令x ，= - - m x 2 引 f a i 吩 = k q 】x 1 i u 。u j _ 【u t x 1 4 q = u v 丁( 1 ：七) 虽然算法i i 保证了数列 ，( q ( ) ) 是个递减的数列，但是仍然无法保证算 法i i 的迭代解收敛于问题( 1 4 ) 的真解我们将在第4 章中给出数值例子 在文i t l 中aw b o j a n c z y k 与a l u t o b o r s k i 通过：j ( ? , g i v e n s 旋转和投影技巧， 得到两个与算法类似的迭代算法：左松弛算法( l s r m ) 与右松弛算法( r s r m ) 假 设u p , v r = a 是矩阵a 的奇异值分解则问题( 1 4 ) 等价于求解如下问题： 百= a r g q m ，q i n ：一国一u t b j | f q = y 国就是问题( 1 4 ) 的解 l s r m 算法求解r a i ni l o 一直怯，其中= d i a g ( a 1 ，吼) ，亩= u t b = 0 1 q = 1 ( h ，一，孔l ，国= 瞬，一，甄 1 初始化国= 厶。 ，i t e r = 0 ，r 一1 = 0 ，r o = 审一彦 f 2 迭代求解 i = 1 ：几 j = i + 1 ：礼 求解平面p r o c r u s t e s 问题： 肋吐r a m i n 。i l d i a g ( 0 - i ：。) 啦西卜慨b j l l f f 磊爵 - 一， 磊爵 i t c r * i t e r + 1 r i t 。，= i q b 怯 若i n 一r m 1 i o i 。 ( 9 - i 。是南个互异的奇异值因此我们可以推断g 是块对角的并且g = d i a g ( g ，g ) 的对角块g 与，的对角块吼。，是相互对应的由c 叮，= ，g 可 得q ，q 是对称的，因此g 是对称的又由呼q k = c ，可得 q t 珥= w g + p s 其中s 满足伊口+ s r s = j - ，v 是w 的正交补另一方面，由0 t a t b = v , c s ，v , r + 译s e ，甲的对称性可知k 。s e ，v 也必须是对称的，由此可得s = 0 从而g 是正 交对称阵，那么g 只能是单位阵因此我们有 珥= q w 由此可得( 珥，时) t q ( w ，睁) = d i a g ( i ，t ) ，其中时是正交补，即有q = ( 珥，唠) d i a g ( i ，t ) ( k ，时) t e h j 锄2 1 1 可知q 是均衡p m c m s t e s 问题( 1 4 ) 的最 优解 定理2 1 2 即为均衡p r o c r u s t e s i a 题的最优解的充要条件但是定理2 1 2 对非 均衡p r o c r u s t e s1 6 题是否成立昵? 注记2 1 1 ：定理2 1 2 说明均衡p r o c m s t e s l h 日题的最优解可以通过a t b 的极分解 a t b = q s 8 一 第二章正交约束下的p r o c r u s t e s 问题的解的性质 求解，其中q 是正交阵，s 是对称正半定阵但是对非均衡p r o c r u s t e s i h 题来说，定 理2 1 2 并不成立 与我们后面所提到的一样，非均衡p r o c r u s t e s 问题的解是与之相关的均 衡p r o c r u s t e s 问题解的列的一部分这个性质与定理2 1 2 一起有助于我们研究非 均衡p r o c r u s t e s ( 口 题全局( 局部) 最优解的性质 2 2 非均衡p r o c r u s t e s 问题的解的充分条件和必要条件 假设q 是非均衡p r o c r u s t e s i h q 题( 1 4 ) 的一个解，日是q 的正交补显然对任意 正交阵国= 亩，国。】，我们有 l i a q ，明一 b ，a h i i f = l i a q b i i f i i a q ，一b i i f l i a o 一 b ，a h i i f 很显然旧，h i 是如下均衡p r o e r u s t e s l 口- j m i n 1 i a c 一【b ，a 明i i f 6 , r g = ， 。 ( 2 2 ) 的一个解因此由定理2 1 2 ，我们得到一个非均衡p r 咖s t 船问题全局最优解的必 要条件 定理2 2 1 ：若q 是非均衡p r o c r u s t e s 问题( 1 4 ) 的一个最优解，那 么【q ，q 上】t a b ，a q 上】是对称正半定的，其中q 1 是q 的正交补 与均衡问题不一样的是：满足 q ，q 1 t a b ，a q 上】对称正半定的标准正交 阵q 并不一定是非均衡问题的最优解尽管如此，这还是为我们提供了最优解的 重要信息举例来说， q ，q 1 丁a b ，a q l 的对称性可以推出q 满足如下法方程： a t a q q a = a t l 3( 2 3 ) 其中a 为一对称矩阵另一方面，由于f q ，q j 。 丁a b ，a q 上 是正半定的，因 此q 丁a t b 依然是正半定的 我们称方程( 2 3 ) 是为问题1 4 的法方程由定理2 2 1 以及上述分析可知：法方 程( 23 ) 是非均衡p r o c r u s t e s 问题全局最优解的必要条件，但不是充分条件为了说 9 第二章正交约束下的p r o c r u s t e sj h 目题的解的性质 孵满足( 2 3 ) 的正交阵q 作为一个全局或局部最优解的条件，我们需要引入下面的 引理 引理2 2 1 ：如果标准正交阵q 满足以t a q + q a = a t b ，其中a 是对称的，那么对 任意标准正交阵0 ，我们有 a q 一日瞎= i i a q 一日| | ；十| | a ( 勺一q ) i i ；十t r ( a ( 0 一q ) t ( 国一q ) ) 证明：我们记a 亩一b = ( a q b ) + a ，其中= 亩一q 两边取f r o b e n 珧范数 的平方并利用等式a t ( a q b ) = q a 以及a 的对称性，可得 a 0 8 8 ；= i i a q b 8 釜+ i i a ( q q ) t l g t r ( ( 丁q + 矿) a ) 另一方面，e - 于0 = q + 与q 均为标准正交阵，因此等式t q + q t = 一? 成 立把它代入上面的等式中即可 由引理2 2 】，我们立刻得到一个唯一全局最优解的充分条件：若q 满足法方 程( 2 3 ) ，并且a 是正的，那么q 是非均衡p r o c m s t e s l b 题( 1 4 ) 的唯一全局最优解、但 是，这个条件太强了以至于i b i s ( 1 4 ) 的全局最优解普遍的不满足这个条件因此 我们必须寻求更一般的更弱的条件 定理2 2 2 ：假设存在对称阵a 使得标准正交阵q 满足a t a q + q a = a t b 若 仃。2 ( 4 ) + a m e n ( a ) 0 ，( 2 4 ) 则q 是非均衡p r o c r u s t e s 问题( 1 4 ) 的个( 全局) 最优解更进一步，若等式( 2 4 ) 严格 成立，则q 是唯的 证明：假设0 = q + 是不同于q 的任意标准正交阵，a u d i a g ( a 1 ，k ) c ，丁是a 的特征值分解记w = a u 则我们有 a a i i 蚤+ t r ( a a ( a ) r ) = i i a w i i 备+ t r ( d i a g ( a ，k ) 彤t w ) k = ( 1 l a w j l l 2 + 训训：) j = l 1 0 第二章正交约束下的p r o c r u s t e s i n 题的解的性质 k ( a ：( a ) + a j ) l l w j l l 2 0 j = l 由引理2 ，2 1 可得1 1 a 国一b i l ；i i a q b | j ； 注记2 2 1 ：当七= 1 时不等式( 2 4 ) 也是充分条件参看【8 ，定理2 2 】 在文 3 】中给出了与( 2 4 ) 相似的形式 定理2 2 3 ：【3 ，定理3 8 假设q 是非均衡p r o c r u s t e s i a 1 题( 1 4 ) 的一个( 全局) 最优解， 并且存在对称阵a 满足 a t a q + q a = a t b t 7 i ，t = 1 ，竹，是a 的奇异值，九，i = 1 ，七，是a 的特征值，并且它们均按降序 扫 歹0 贝0 凡一酲一州，t = 1 ，2 ，k 接下来我们将讨论问题( 1 4 ) 局部最优解所满足的条件 定理2 2 4 ：假设存在对称阵a ，使得标准正交阵q 满足a t a q + q a = a t b 若对 任意满足q 丁反对称的非零矩阵，满足不等式： a a i i ；+ t r ( a a a t ) 0 ( 2 5 ) 那么q 是非均衡p r o c r u s t e s i h 题的局部最优解 证明：假设q 不是( 1 4 ) 的局部最优解，那么存在矩阵序列 q ( ) ) 使得q ( ) 一q 并 且，( q ( 。) ，( q ) 记 ( 4 ) = q ( ”一q ， q ( ) = i l ( 4 l l ，厶( 2 ) = ( 4 n ( 4 ) 由于 厶( ) 有界，因此我们可以假设 厶( t ) 收敛令= l i r a t 。厶( ”又因 为q 与q ( 2 ) = q + ( ) 均是标准正交阵，所以我们有 q 了1 ( 2 + ( ( 2 ) 7 q + ( ( 4 ) 丁( 。) = 0 1 1 第二章正交约束下的p r o c r u s t e s f n 日题的解的性质 上述等式两边同除于。o ) 并令i 一。，可得丁q 是反对称的另一方面，由弓 理2 2 1 我们有 l i a a ( | | ；+ t r ( ( ( 4 ) t ( ) a ) 0 从而有 这与假设相矛盾 a a x l l ；+ t r ( a a ( a ) t 1s 0 如果矩阵a 7 p 妯使得矩阵q t 反对称，则我们称为q 在s t i e f e l 流形s ( 1 2 ) 上的切向量下面的结论表明不等式( 2 5 ) 对s t i e f e l 流形上的局部最优解的判 定是非常重要的 定理2 2 5 ：假设存在对称阵a 使得标准正交阵q 满足a t a q + q a = a t b 若存 在一非零矩阵使得q t 是反对称的并且不等式： a a i i ；+ t r ( a a a t l 0 成立，那么q 不是非均衡p r o c r u s t e s i q 题的局部最优解 证明：假设q ( t ) 是定义在流形5 局部的可导曲线，也就是说是比较小的，并且满 足q ( o ) = q 以及0 ( o ) = a ，那么t h 弓l n 2 2 1 ，可得 旦垒翌生! _ 二兰坐冬；堂= f i a 望壁之二旦| | ；+ t r ( a 尘里竺l 二里笔掣) 令t 一0 ，则有 姆螋坠譬掣垒生盟+ 0f o a a l l 刍+ t r ( a a 丁a 1 0 成立另一方面，假设a = u d i a g ( a 1 ，扎) 护是a 的特征值分解对x 0 记w = x u 0 则有 定理得证 t r ( x 7 2 ( 硼) 一i i a h x t ；+ t r ( a x r x ) = i i a h w i 十t r ( d i a g ( a l ，k ) 7 ) = 1 2 ( i a h w j i l 2 + bj q j ( ；。( a 何) + a ，) 2 0 ， ， 在下一章中，我们将在第3 1 i e l , 。- p r o c m s t e s 问题的持续投影算 法；并在第32 节讨论持续投影算法计算过程中可能出现的问题；在! 1 9 3 f 3 节中，找 们将结合我们所提出的算法对非均衡p r o c n l s t e s 问题解的充分条件和必要条什做 进一步的讨论 第三章求解非均衡p r o c r u s t e s i 日 题的持续投影算法 第三章求解非均衡p r u c r u s t e s 问题的持续投影算法 本章中我们将在持续投影算法的基础上讨论持续投影算法迭代过程中出现 的问题以及迭代解的收敛性 3 1 持续投影算法 在本节中我们将提出一个迭代算法：持续投影算法，该算法基于文 8 s s 求解 二次等式约束下的最小二乘问题+ ： r a ：i ：n 1 i i a z b i l 2 ，给定a 缈”，6 冗” ( 3 1 ) 的投影算法对于l s q e i h 题，其法方程为 f 舻a + m ) x = a t b 其中a 为乘子若a 一田( a ) ，j = 1 ，扎，则法方程有唯一解 因而可得如下特征方程 z = ( a t a + a ，) _ 1 a t b ( a t a + a ，) 一1 a t 6 l | ! = l ( 3 2 ) 已经证明，l s q e f 司题的最优解z + 就是特征方程( 3 2 ) 的最大解”所对应的z h 并且a + 一磅( a ) 当a + 一( a ) 时，l s q e i h q n ( 3 1 ) 的解唯一；若”= 一2 ( a ) ， j j l s q e i h l 题( 3 1 ) 有多个解 对l s q e i h 题( 3 1 ) 多解情形，我们引入如下定理 定理3 1 1 ： 8 ，定理2 2 l s q e ( 司题( 3 1 ) 存在多个解当且仅当 1 ) 奇异方程( a 7 a 一口：( a ) ，) q = a 至少有一个解， 并且 4 _ 次等式约束下的最小_ 二乘问题( l s q e ) ，即为女= l 的a # 均衡p r o c r u s t e s l h q 题 一1 6 第三章求解非均衡p r u c r u s t e s 问题的持续投影算法 2 ) 若q + 是奇异方程的最小范数解，那么l 扩i l l 的情形记q = q l ，9 2 ，- 一，】，b = b l ，6 2 ，一，6 ，则 k ，( q ) = i i a q 日l l 刍= i l m q j 一幢 i = 1 记q = q l ，q j - 1 ) 吩+ 】 ，鲥，固定矩阵q 中除第j 列外的所有列，则我们可以 通过求解如下约束问题： 9 1 。r a ，i i i g n l i 。：1 i i a q b | | ! 来修正标准正交阵q 因此可以得出下面的定理 定理3 1 2 ：若q 是非均衡p r o c r u s t e s 问题( 1 4 ) 的解，则 ( 3 4 ) a 一b i l l2 q l g m ，i n l ：1i i a q b i l l ，j = 1 ， ( 3 5 ) 1 7 第三章求解非均衡p r u c r u s t e s 问题的持续投影算法 通过q 的正交补h 可以简化约束问题( 3 4 ) 由于g j = 乜，明是q 的j 下交补， 那么单位向量q 上q 就可以写成口= g i x ，其中z 冗”+ 1 是单位向量因此约束 问题( 3 4 ) 等价于如下的l s q e i h 题： | | 骝，i l a q z 一堋 ( 3 6 ) 用西= g j x + 替代劬来修正q ，其中z + 是l s q e 问题( 3 6 ) 的最优解把修正后的标准 正交矩阵记为国显然，如果w 是z + 的零空间的正交基，那么矗= q w 就是0 的正 交补 上述修正过程可以让j = 1 ，反复进行在这里我们枷= 1 ，的七 个修正为一个扫描过程显然，如果q 满足( 3 5 ) ，那么这样的扫描过程将不会 使，( q ) 下降因此有必要在每个扫描过程完成后做一个全局修正，即求解；b t 均 衡p r o c r u s t e s 问题： i n i l l i a q p b 慷 p t p = i 。 。 ( 3 7 ) 然后令国= q p 显然，对现有的0 来说国= 亩p 是一个更好的逼近，其中p 是( 3 7 ) 的解 根据上述分析，我们提出持续投影算法 1 8 第三章求解j 均衡p r u c r u s t e s 问题的持续投影算法 持续投影算法( s p m 算法) 给定a 冗“，b 冗”，礼k ，求标准 正交阵q 冗“使得i i a q b i i f 最小 1 初始化取a t b 的相空间的一组基q ( o ，o ) = k i o ，0 1 ，q l o , o ) 及其 正交补日( o ，叭令r 0 = l i a q ( o , o ) 一日怯 2 i = 0 ，1 ， 2 1 j = 1 ，2 ，一，k ， 2 1 1 记g ( ，) 一博m ，h ( t ，卜1 】，求解l s q e 问题： 扣l a r g l 器i t a c 埘z 一吼 ( 3 8 ) 并令碰。) = g ( i ，j ) x ( i ，计， 班，) _ ，移西骝，q 2 1 2 计算。( ，j ) 的正交补w ( 川，则q ( ) 的正交补为： 丑( t j ) = g ( k j ) w ( i j ) 2 2 求解均衡p r o e m s t e s 问题： 尸d = a r g n p 蜒。p n a q ，砷p b i i f 并令q ( + 1 ，o ) = q ( ，) p ( ”，日o + 1 ，o ) = 日( i ，m 2 3 r i + 1 = i i a q ( + i , o ) 一b 峙若i n + 1 一t i l 卢或o l = 卢并且s 时，不等式 ，i i l i nl i a q 一岛 q i q ：i , j - 1 ) i l q l l = l l l a b i l l 0 ，( q ( ) ，( q ( ) 成立因此序列 ，( q ( j ) ) 是单调收敛的 然而在局部扫描和全局修正的求解过程当中都可能出现多解如果在一个 迭代步骤出现多解时取不同的解，那么s p m 算法可能得到不同的迭代序列和结 果下面，我们将讨论在迭代过程中出现多解的问题， 由定理3 1 1 可知，l s q e i h 题( 3 8 ) 存在多个解当且仅当奇异方程 ( ( a g “j ) ) 丁a g ( ，j ) 一a 2 i ) x = ( a g ( ，) ) t 有解并且其唯一的最小范数解矿满足i l 矿1 1 2 0 所对应的左奇异向量，并且b 丁u 与勺不成比例， , l j m i n 。- l 奶，：1 i i a q b | | 存在一个最优解西使得( a 国) t b t p 对称，其中国= q 1 ，毋一1 ，西，q 3 + 1 ，q k 证明：我们取西= g j ( x + + 卵 r 二_ i ；可习) ，其中 是a q 的与“相对应的右奇异 向量，卵= 1 或者一1 叼选取不同的值，我们得到两个标准正交矩阵囝( + ) 与国( 由 于矩阵 b 丁a ( 国( + ) 一0 ( 一) = 2 、丁二i w j i 砰b t a g a v e t = 2 a n u 。、，二i ；可f b t u e 是非对称的，则日丁a 国( + ) 与b t a o ( 一) 两者之间必定有一个不对称假设是矩 阵国使得b r a 国不对称l j m i n p r p ： f ( q p ) o 都成立 注记3 2 2 ：若a 不是列满秩的，那么对应于r n j n 叮上。，i i q i i ：1l i a q b , i i 的不同的解 的0 是不同的，但是b t a 国是相同的 下面我们考虑全局修正是如何使，下降的下述引理很简单，但却论证了我 们的关于在每个扫描过程之后使矩阵b 丁a q 非对称的观点 引理3 2 2 ：假设q 冗n x k 是标准正交的贝j j f ( q ) = m i r l p t p ：“f ( q p ) 当且仅 当( a q ) 丁b 是对称正半定的 证明：假设( a q ) t b = u ，d i a g ( a ”，听) 咿是( a q ) t b 的奇异值分解，r = r a n