（计算数学专业论文）shapefrommoments问题敏感性分析的一些结果.pdf

复旦大学硕士学位论文 摘要 s h a p e - f r o m - m o m e n t s 问题是指通过平面多边形的一组m o m e n t s 重构这 个多边形重构一个多边形实际上包括计算顶点和顶点次序两部分一些系 数对于计算顶点次序是十分重要的，对于这些系数我们定义了敏感因子，并 且通过敏感因子来做敏感性分析这些敏感因子对于多边形顶点的敏感性分 析同样有用数值例子表明这些敏感因子的大小反映出系数的敏感性。 关键词：s h a p e - f r o m - m o m e n t s ，敏感性分析 复旦大学硕士学位论文 2 a b s t r a c t t h i sp r o b l e m 肌印e 伽m m o m e n t si st or e c o n s t r u c tap l a n a rp o l y g o n f r o mas e to fi t sc o m p l e xm o m e n t s t or e c o n s t r u c tap o l y g o nm e a n st oe s t i m a t et h ev e r t i c e sa n dt h eo r d e r i n go ft h ev e r t i c e s s o m ec o e m c i e n t sa r ev e r y i m p o r t a n ti nf i n d i n go u tt h eo r d e r i n go ft h ev e r t i c e s w ei n t r o d u c es e n s i t i v e f a c t o r sf o rc o m p u t i n gt h ec o e f f i c i e n t sa n du s et h e mt o a n a l y z es e n s i t i v i t y t h e s ef a c t o r sa r ea l s ou s e f u lf o rt h es e n s i t i v i t yo ft h ev e r t i c e s n u m e r i c a | e x a m p l e ss h o wt h a tt h em a g n i t u d eo ft h e s ef a c t o r ss t a n d sf o rt h es e n s i t i v i t y o ft h ec o e f f i c i e n t s k e y w o r d s ：s h a p e - f r o m m o m e n t s ，s e n t i v i t ya n a l y s i s 复旦大学硕士学位论文 1 问题介绍 s h a p e - f r o m m o m e n t s 问题指的是从一组复的m o m e n t s 中重构出原来的 平面多边形这个问题在纯数学和应用数学中都有广泛的应用，比如：x 线 断层摄影术，数理统计f 2 0 1 ，数字信号处理 2 1 等等长期以来， s h a p e 一 舳m m o m e n t s 问题被认为是一个困难的反问题，因为早期的方法经常导出 一个坏条件系统，求解这个系统是数值不稳定的，而且在很多情况下解不唯 m i l a n f a r 和k a r l 1 6 1 做了一系列的工作，发现平面上简单多边形的顶点 是被这个多边形的有限个m o m e n t s 所决定的近期在s h a p e - f r o m m o m e n t s 问题上采用一些数值代数的技术表明该问题是可以得到一个完全的，完整形 式的解这里用到的数值代数技术主要包括最i j 、- - 乘问题、广义特征值问题； 令人兴奋的是在最小二乘、广义特征值问题上现在都有很多成熟的技术，存 在着很多稳定高效的算法这些对于s h a p e - f r o m m o m e n t s 问题的最终求解 都是有很大帮助的更多的细节请读者参考9 1 _ t g g 个多边形实际上包含两个步骤：1 、计算出多边形的顶点 ) 墨。； 2 、计算出多边形的边( 顶点的次序) 在第一步中，有很多种方法 l s p r o n y 方法1 1 6 ，1 8 】巧妙的将s h a p e - f r o m m o m e n t 3 问题和差分方程联系起 来p e n c i l 方法【9 将s h a p e - f r o m m o m e n t s 问题转化为一个广义特征值问 题：t l u = z t s u ，其中的广义特征值z j 就是我们要求的多边形顶点后来 h u a 和s a r k a r 提出了g p o f 方法( 广义的p e n c i l 方法) 一个问题是：对于 给定的含有误差的m o m e n t s ，或者在有限精度计算的条件下，怎么去检验 计算出的顶点的正确性? 如果采用的p e n c i l 方法，可以利用广义特征值问 题的扰动分析理论来分析顶点的敏感性【9 】在第二步中，在精确计算出顶 点的基础上，精确的计算出系数a ，( 其定义在第二节) 对于求解出顶点的次 序是非常重要的这篇文章中，我们的主要工作是系数o f 的敏感性分析， 并且对于每一个0 j ，我们定义了敏感因子也就是说如果实际计算中过程 中发现得到的敏感因子比较大，那么计算得到的q 很可能不精确数值例 子显示我们得到的敏感因子对于顶点的敏感性分析也很有帮助 在第二节中，我们介绍一些s h a p e - f r o m m o m e n t s 背景知识，并且简要 介绍l s - p r o n y 方法和p e n c i l 方法这两大主流算法，同时讨论系数a s 的计 4 复旦大学硕士学位论文 算方法第三节中包含我们的扰动分析结果，对于每一个顶点和系数，定义 了敏感因子第四节包含一些数值例子文章最后是我们的总结 2 数学背景与常用算法 2 1 数学背景 定理2 1 ( d a v i s 定理【3 】) 给定f ( z ) 是定义在复平面上多边形p 上的全 纯函数，2 1 ，砘，z _ 是p 的个顶点那么我们可以找到一组常数系 数口1 ，a 2 ，a n 与钆，z 2 ，z n 有关，但是与( z ) 无关，满足： ，”( 。) d z d 可 j3 p n 。j f ( z a ( 1 ) 如果顶最z j 按照顺时针方向排序，并且z o = z n ，。1 = 。+ 1 那么 系数q 可以被表示为； q = ；( 鬻一鬻) 在( 1 ) 式中，令f ( z ) = z ，我们有 以，d x d y = k ( ) i v z 一- 2 d x d y = 翻n 地) ：塞蟛 j = 1j = 1 多边形的第个m o m e n t 被定义为 = 苟 ( 4 ) j = l 从( 3 ) 式我们可以得到= n = 0 假设0 曼k m ，我们把( 4 ) 式 写成矩阵形式t 5 复旦大学硕士学位论文 三 = ( 曼至j ；妻 ( 三) 亍住m “) = 坼1 ，m + i n a l ， ( 6 ) 多边形重构问题( s h a p e - f w m m o m e n t s ) 是这样定义的；假设某个多边 形的肘+ 1 个复的m o m e n t s 取 丝。是已知的，1 、如何计算出该多边形 的顶点 句) 墨。? 2 、计算出多边形的边，也就是顶点的次序对于一个凸 多边形，第二步不是一个问题，但对于一般的多边形，就必须考虑边的重构 问题有兴趣的读者可以参考 1 7 】这里需要指出的是重构边是通过系数o ， 的，所以精确的计算出系数a ，是重构多边形的边的前提 2 2 基于l s p r o n y 技术的方法 我们这里先介绍l s p r o n y 方法 1 8 ，1 6 】从公式( 4 ) 。m o m e n t s 住) 楚。 满足一个阶差分方程： p n t k + p n 1 + 1 + + p l r k + n 一1 + r k + n = 0 ， k = 0 ，1 ，2 i ，m 一( 7 ) 并且多边形顶点 ) 墨。就是这个差分方程特征多项式的根，特征多项式为 nn q ( z ) = ( ：一) = z + 聊z n - j = lj = l ( 8 ) 6 复旦大学硕士学位论文 因此可以得到一个m + + 1 阶的线性方程组 _ 、f 罚 肌 1 0 1 卜i 一旷 通过对方程( 9 ) 重新编排，我们可以得到一个新的线性方程组 f ：芝 一i ? 2 | = l ! ； m “啊“ 记这个方程为 7 - 一 t a r ： 7 m 一 卜 ( 1 0 ) 一亍 m 一+ 1 2 丑o m n + i ，n l p n ，l ( i i ) 我们可以通过公式( 1 1 ) 计算出特征多项式各项系数 功) 墨。，然后计 算特征多项式的根。也就是多边形的顶点 勺 饕1 注意如果m o m e n t s 精确 的- 公式( 1 1 ) 是一个线性方程组但是由于m o m e n t s 扰动以及计算误差的 影响，公式( 1 1 ) 实际上是在最小二乘意义下成立的，也就是说： p n ，1 ) = 一丁茹，吖一+ l ，l 亍 m 一+ 1 ) ( 1 2 ) 其中t + 表示t 的m o o r e - p e n r o s e 广义逆 2 3 基于p e n c i l 技术的方法 p e n c i l 方法【9 将s h a p e - f r o m - m o m e n t s 问题转化为一个广义特征值问 题 从公式( 6 ) 和( 1 1 ) 我们得到： 丑。，m 一+ l n i 2 k i ， 彳扎) d i 妁 8 j ) 曙，m 扎( 1 3 ) 7 复旦大学硕士学位论文 所以 孔l ，m 一+ 1 = k l ，m + l ， d i a g a j d i a g z j 曙，m + l ，) ( 1 4 ) 孔l ，m n + l ，_ v ) y i ，t + 1 ，_ ) = 孔o m 一_ v + l ，t o v 石，t 村+ 1 ，d i a g z j ( 1 5 ) ( 1 5 ) 中的广义特征值就是我们要找的多边形的顶点，并且相应的特征向 量与西“) 中相应的列只差一个常数倍数 为了方便起见，我们将公式( 1 5 ) 记为： ( 1 6 ) 应当注意这个特征系统是长方的，最简单的处理技术是选择这个特征系 统的前行，当然，你也可以选择任意的行，最后再把结果做平均 在系统( 1 5 ) 中，如果我们用l 列来计算而不是列又会怎么样( l | ) ? 这其实是g p o f 方法的核心思想，有兴趣的读者可以参考 1 2 ，1 3 】 2 4 系数q 当顶点= ，已经确定了，有许多方法来计算系数由于我们还不知 道顶点的次序，所以不能用公式( 2 ) 来求解也许最简单的方法就是用公式 ( 6 ) ，由于扰动和计算误差的关系，这将是一个最t j 、- - 乘问题 另一个方法可以很自然的从p e n c i l 方法导出如果我们用前行来计 算特征系统，我们得到的广义特征向量是y 。的列的倍数如果矩阵x 由 广义特征向量所组成，那么： x 一，t v ，m d i a g s j ( 1 7 ) 这里 8 。，n ：l 表示广义特征向量与相应的v 4 相差的倍数 假定已经知道多边形的顶点，我们就可以得到顶点的v a n d e r m o n d e 矩 阵k n ) ，这样我们就可以计算出 8 。，n ：1 ： x 嵋，) = 呕_ v t i ，- t 札) d i a g 唧) _ d i n 9 b ) ( 1 8 ) 知道了相差的倍数s j ，我们就可以从x 计算出， 那么： 8 复旦大学硕士学位论文 瓦 1 ，) = y i k + l 。 亍 o ，m + 1 卜 ( 1 9 ) 大量的数值例子表明，上述两种方法求解出的q 精度是差不多的 下面我们简单分析一下系数与边的关系 从( 2 ) 式中可以看出系数q 只与三个顶点一1 ，z 3 ，z j + 1 有关并 且更进一步的，令吼表示复数z j 一一z a 的幅角，那么： 从( 2 ) 式可以得到 互= l 二圣：e 一“屯 z 3 一l 一 ( 2 0 ) = s i n ( o i 一1 一如) e 一( 虬一1 + 白( 2 1 ) 从式( 2 1 ) 中我们可以得到如下结论： 注记2 1 - 设p 为一个简单多边形，系数都是非零的当切仅当p 是非退 化的h 目邻两边不共线，当p 是非退化的时候，0 1 0 j l 1 而且i 越 接近0 ，说明在顶点句处多边形越近似退化慨一l 岛，两边近似共线j ； l q l = 1 ，说明顶点处的顶角是直角 3 敏感性分析 3 1 顶点的敏感性分析 基于p e n c i l 方法的扰动分析可以参见 9 】，这里我们简要介绍一下考 虑广义特征值问题五“= z t o u ，对该系统做e 扰动分析： ( 乃+ e f ) ( u + e t 1 + ) = 0 + e = 1 + ) ( 蜀+ e g ) ( 钍+ e u ( 1 十) ( 2 2 ) 通过化简，扔掉高阶小量，我们得到； z ( 1 ) = _ u r ( f 而- f z o ) u ( 2 3 ) 我们注意到在公式( 2 3 ) 中，所有的广义特征向量都需要被计算出来但 是广义特征向量实际上是一个额外的计算，因为它们对于我们的重构问题是 9 复旦大学硕士学位论文 没有用的还有一点需要指出的是，在一些情况下p e n c i l 方法会变得异常敏 感和不稳定，使得计算出来的结果很差，这可能是由于s h a p e - f r o m m o m e n 拈 问题本身的非线性造成的【1 8 1 对于l 8 一p r o w 方法，直接应用这样的扰动 分析技术是困难的，因为l s - p r o n y 先是求解一个最小二乘问题得出特征多 项式的各项系数，然后再求出特征多项式的根( 多边形的顶点) 一个值得注 意的现象是大量的数值例子表明系数n ，与顶点z ，的计算精度有着某种相关 性，也就是说如果计算的精确，那么计算出来的o ，也会有较高的精度， 反之亦然 3 2 系数的敏感性分析 从第一节中我们知道町对于计算出顶点的次序是很重要的这一节中 我们介绍一下关于吗的扰动分析理论如果多边形顶点已经计算好了 那么系数可以从仉的定义式来计算 设勺的v a n d e r m o n d e 矩阵是y ，也就是说 ( 2 4 ) y 俘国 1 0 乒0 町 脚 = 复旦大学硕士学位论文 给定一个m 行n 列的矩阵y 和一个长度为m 的列向量r ，最t j 、z 乘 问题事实上是寻找一个长度为n 列向量n ，满足：| i v a r 0 2 最小 定理3 1 设向量n 使得1 1 w r l 2 最小我们做如下分裂：v = 【矿( ，k ， a = a ( ”) ， ，其中k 表示矩阵v 的最后一列，a n 表示列向量a 的最后 一个元素那么n 。将使得0 k 。一到2 最小，其中i = r y 机) a ( 证明如果存在其他的o 。o ，满足： l k o 一钏2 i | k 8 。一钏2 ， 因为 y n = ( 矿c ，k ) ( 乏：) = 矿( n ) a t h ) + 吒。， 所以 y n t l l 2 = l i k 。一( r 一矿( “a ( “) 0 2 = i k a 。一? i 2 同理可得 ”y ( 甜a n 哪o ) 一r 忆= ”k 。一c r 一矿( n ) 副曲川。= “v n a n o - 忆 那么 阿( ：) 刮妊r 此 因此a 不是v a = r 的最t b - - 乘解，矛盾 口 定理3 1 实际上是说a 。是一个新的最小二乘系统o 。= 的最小二 乘解上述定理中，如果把k 用v 中任意的第j 列k 来代替；把。用n 中任意的第j 个元素奶来代替，定理3 1 也是正确的 如果固定y ，让r 变成r + 打，那么最小二乘解变成o + 乩，此时我 们有下述定理 定理3 2 1 9 ，s e c t i o n4 3 】设v g n “，并且v 是列满秩的记f i = v v + 是一个从c ”到孵) 的投影算子，记r 1 = p v r 如果r 1 0 ，那么； 糌细d 2 ( ”黜 ( 2 7 ) 这里c o n d 2 ( v ) = | | y + i h lr v ) ) 2 复旦大学硕士学位论文 推论3 1 如果定理3 2 中的矩阵v 是一个列向量，那么公式俾刀可以简 化为： i i 乩l 【：，1 1 6 t 1 i l 。 i l a 1 ：2i l r - i j 。 敏感因子c 定义为c = lj r l 怯1 ，那么( 2 8 ) 可以记为； 甓哪r 1 i i ：，2 2 “ ( 2 8 ) ( 2 9 ) 最后我们总结一下0 j 敏感性分析算法的整个步骤： 对于给定的m o m e n t sn ，计算得到的多边形顶点，计算得到的系数 q ( 用来计算多边形顶点的次序) ，设y 是勺的v a n d e m o n d e 矩阵，嵋表 示y 的第j 列，我们有下述算法； 算法 镟蚓防。 ( 3 0 ) 我们将上述公式中的q 称为a j 的敏感因子 值得注意的事情是，敏感因子勺不仅对于系数q 的敏感性有指示作 用，对于顶点的敏感性也同样有指示作用，这一点在随后的数值例子中 可以很清楚的看到我们目前还不清楚这是什么原因，也许系数q 和顶点 勺之间还有某种更深刻的联系 1 2 复旦大学硕士学位论文 g i v e np o l y g o n ，n = 8 图1 ：“e ”型多边形，8 个顶点 4 数值例子 4 1 例一 这个经典的例子出自9 ，1 2 ，1 8 1 ，如图1 所示，这是一个“e ”型的多 边形，所有的顶角都是9 0 度( 2 7 0 度) 我们选择l s p r o n y 方法来计算， 并且对比精确m o m e n t s 和含误差( 1 0 “) 的m o m e n t s 两种情况下的计算 结果( 图2 ) 表1 列出了图2 右中的具体数据，包括计算得到的顶点的相 对误差，系数的相对误差，敏感因子e j 从表1 中，我们可以看到系数 n 3 、4 ，n 5 、口6 的相对误差明显较大，同时敏感因子c 3 ，c 4 ，c 5 ，c 6 也比较 大，这一点与我们的分析理论符合的很好值得注意的是顶点z 3 ，z 4 ，2 5 ，。6 的相对误差也明显较大，这一点在图2 右中更加直观p e n c i l 方法和g p o f 方法在这个例子上都有着相似的精度和现象 4 2 例二 这是一个一般的例子，如图3 所示顶点z 。是近似退化的，也就是说相 邻的三个顶点z s ，z s ，z 1 0 是近似共线的；顶点z 3 ，z 6 处的顶角是非常锐的内 角；顶点z 5 与其他的顶点离得比较远我们分别用l s p r o n y 方法、p e n c i l 1 3 塞呈盔堂塑圭堂垡堡塞 1 4 l sp r o n ym e t h o d n f f i 8 ，m a 2 0 6 l sp m n ym e t h o dw i t hn o i s en = 8 m - 2 0 图2 ：l s p r o n y 方法，左：m o m e n t s 精确，右：m o m e n t s 扰动1 1 d t r 1 1 2 1 0 o ：原来多边形的顶点；+ 一计算得到的顶点 j i z l 一毛i 倩 l 町一奶i 屯q 10 3 + o 9 i0 0 0 0 30 0 0 40 3 3 2o 4 + o 9 io 0 0 0 6o 0 0 9o 2 5 30 4 + o ，5 i0 0 3 2 10 2 0 60 8 9 40 0 5 + 0 5 i0 0 9 3 80 2 5 21 0 6 5o 0 5 0 5 i00 9 3 80 2 5 21 0 6 60 4 o 5 i00 3 2 1 0 2 0 60 8 9 7 o 4 0 9 i0 0 0 0 60 0 0 90 2 5 8o 3 0 9 i0 0 0 0 30 0 0 40 3 3 表1 ：l s p r o n y 方法，m o m e n t s 扰动l f 打r l l 2 1 0 3 复旦大学硕士学位论文 g i v e np o n n ；1 q 图3 ：1 0 个顶点的多边形 方法、g p o f 方法来计算图4 左、图4 右和图5 左分别是m o m e n t s 精确 情况下l s p r o n y 方法、p e n c i l 方法和g p o f 方法的计算结果从图上我 们就可以看出l s - p r o n y 在顶点弼，z 6 ，z 7 ，z 9 有较大的计算误差，p e n c i l 方 法和g p o f 方法在这四个顶点上计算结果相似或略好。根据经验，这是因 为顶点施，翔处是凹的，顶点z 7 与如离得很近，硇是近似退化的顶点由 于这个例子包含了一些极端的情况，所以即便有微小的扰动( 1 0 “) ，也会 对最终的计算结果产生很大的影响( 图5 右) 表2 列举了m o i i l e n t s 精确情 况下使用g p o f 方法( 图5 左) 的计算结果，我们可以看到c 3 和c 6 比别的 敏感因子大得多，按照我们的分析理论，这意味着计算得到的口3 和a 6 会有 较大的误差，实际情况也的确如此其次的几个较大的是c 9 ，c 7 和c 4 ，这意 味着0 9 ，口7 和a 4 也不会有太高的精度值得一提的是c 5 = 0 ，按照我们的 分析，这表明是完全精确的，表中a 5 的相对误差的确为零。这个例子中 我们同样观察到顶点与系数口，在计算结果上的相关性( 要么同时比较精 确，要么同时比较不精确) 1 5 复旦大学硕士学位论文1 6 l sp r o n ym e t h o dp e n c i im e t h o d 图4 ：左：l s - p r o n y 方法，右：p e n c i l 方法 ot 原来多边形的顶点；：计算得到的顶点 g p o fm e l h o d g p o fm e t h o d 图5 ：左；g p o f 方法，右；g p o f 方法，并且m o m e n t s 扰动归r r | | 2 1 0 一 o ：原来多边形的顶点；t 计算得到的顶点 复旦大学硕士学位论文 j习i 一e j l z ji q a j l a j勺 1一o 3 + 0 9 i00 0 0 0 30 0 0 904 6 20 4 + 0 9 i0 0 0 0 0 40 0 0 5o 2 7 30 0 0 0 5 + 0 0 0 0 5 i0 9 9 6 0 71 0 0 08 45 5 40 4 + 0 5 i0 0 0 1 4 10 0 9 60 ，8 6 5a o o0 6 0 0 5 0 5 i0 1 3 1 7 51 0 0 09 9 2 6 70 4 0 5 i0 0 0 2 3 40 2 1 51 7 5 8o 3 一o 9 i0 0 0 0 0 50 0 0 4o 3 3 9一0 6 一o 3 i0 0 0 3 2 4 0 1 8 9 3 2 3 1 01 + 0 2 l0 0 0 0 0 10 0 0 20 1 7 表2 ：c - p o f 方法 5 总结 重构一个多边形包含计算顶点和顶点次序这两部分内容系数a j 对于 计算顶点次序是十分重要的这篇文章中我们对系数。，作了敏感性分析， 并且对每个q 定义了敏感因子从数值例子中可以看到敏感性因子是有效 的并且算起来也很方便一个值得注意的现象是事实上系数a j 与顶点卸的 计算精度有着某种相关性，这一点在目前看到的所有例子( 不只是文章中的 这两个例子) 中都有出现从这个意义上说，我们定义的敏感因子对于顶点 的敏感性分析同样是有用的有一点需要说明的是，公式( 3 0 ) 中给出的 误差的界比较松，怎么样给出一个比较紧的误差的界还是一个有待进一步研 究的问题 1 7 塞呈盔堂塑圭堂焦煎塞一 1 8 参考文献 1 1e b o g o m o l n y , 0 b o h i g a s ，p l e b o e u f , d i s t r i b u t i o no fr o o t so fr a n d o mp o l y n o m i a l s ，p h y s i c a lr e v i e wl e t t e r s ，v 0 1 6 8 ，n o 1 8 ，p 2 7 2 6 - 2 7 2 9 ，4m a y1 9 9 2 【2 1y b r e s l e r ，a m a c o v s k i ，e x a c tm a x i m u m l i k e l i h o o dp a r a m e t e re s t i m a t i o no f s u p e r i m p o s e de x p o n e n t i a ls i g n a l si nn o i s e ，i e e et r a n s o na c o u s t i c s ，s p e e c h ， a n ds i g n a lp r o c e s s i n g ，v 0 1 3 4 ，n o5 ，p p 1 0 8 1 - 1 0 8 9 ，o c t1 9 8 6 f 3 】p d a v i s ，p l a n er e g i o n sd e t e r m i n e db yc o m p l e xl n o m e n t s ，j a p p r o x i m a t i o n t h e o r y ，v 0 1 1 9 ，p p ，1 8 - 1 5 3 ，1 9 7 7 ， f 4 】b d em o o r e ，s t r u c t u r e dt o t a ll e a s ts q u a r e sa n dl 2a p p r o x i m a t i o np r o b l e m s ，l i n e a ra l g e b r ae n di t sa p p l i c a t i o n s ，v 0 1 1 8 8 - 1 8 9 ，p p 1 6 3 - 2 0 5 ，j u l y a u g 1 9 9 3 【5 】5l k a u f m a n ，v p e r e y r a ，am e t h o df o rs e p a r a b l en o n l i n e a rl e a s ts q u a r e sp r o b l e m sw i t hs e p a r a b l yn o n h n e a re q u a l i t yc o n s t r a i n t s ts i a mj o u r n a ln u m e r i c a l a n a l y s i s ，v o l ，1 5 ，v 0 1 1 2 2 0 ，1 9 7 8 6 】m k a h n ，m s m a c k i s a c k ，m r o s b o r n e ，g k s m y t h o nt h ec o n s i s t e n c y o fp r o n y sm e t h o da n dr e l a t e da l g o r i t h m s j o u r n a lo fc o m p u t a t i o n a la n d g r a p h i c a ls t a t i s t i c s ，v 0 1 1 ，p p 3 2 9 3 4 9 ，1 9 9 2 f 7 】g h g o l u b ，v p e r e y r a ，t h ed i f f e r e n t i a t i o no fp s e u d o - i n v e r s e sa n dn o n l i n e a r l e a s ts q u a r e sp r o b l e m sw h o s ev a r i a b l e ss e p a r a t e ，s i m aj o u r n a lo nn u m e r i c a l a n a l y s i s ，v 0 1 1 0 ，n o 2 ，p p 4 1 3 - 4 3 2 ，1 9 7 3 8 】g h g o l u b ，c v a nl o a n ，m a t r l xc o m p u t a t i o n s ，3 r de d i t i o n ，t h ej o h n s h o p k i n su n i v e r s i t yp r e s s ，b a l t i m o r e ，m a r y l a n d ，1 9 9 6 f 9 1g h g o l u b ，pm i l a n f a ra n dj v a t a h ，as t a b l en u m e r i c a lm e t h o df o ri n v e r t i n gs h a p ef r o mm o m e n t s ，s i a mj o u r n a lo ns c i e n t i f i cc o m p u t i n g ，v 0 1 2 l ， n 0 4 ，p p 1 2 2 2 1 2 4 3 ，1 9 9 9 ， f i 0 】g g o l u b ，v p e r e y r a ，s e p a r a b l en o n l i n e a rl e a s ts q u a r e sa n dt h ev a r i a b l e p r o j e c t i o nm e t h o d ，i np r e p a r a t i o n ，j u n e ，2 0 0 2 ， 1 1 】b g u s t a f s s o n ，c h e ，p m i l a n f a r ，m p u t i n a r ，r e c o n s t r u c t i n gp l a n a rd o - m a i n sf r o mt h e i rm o m e n t s ，i n v e r s ep r o b l e m s ，v 0 1 1 6 ，n o 4 ，p p 1 0 5 3 1 0 7 0 ， a u g 2 0 0 0 1 l2 】y h u aa n dt k s a r k a r ，m a t r i xp e n c i lm e t h o df o re s t i m a t i n gp a r a m e t e r so f e x p o n e n t i a l l yd a m p e d u n d a n l p e ds i n u s o i d si nn o i s e ，i e e et r a n sa c o u s t i c s ， 复旦大学硕士学位论文 1 9 s p e e c ha n ds i g n a lp r o c e s s i n g ，v 0 1 3 8 ，p p 8 1 4 - 8 2 4 ，1 9 9 0 1 3 】yh u na n dt ks a r k a r ，o ns v df o re s t i m a t i n gg e n e r a l i z e d e i g e n v a l u e so f s i n g u l a rm a t r i xp e n c i li nn o i s e ，i e e et r a n s s i g n a lp r o c e s s i n g ，v 0 1 3 9 ，p p 8 9 2 9 0 0 ，1 9 9 1 【1 4 p l e m m e r l i n g ，l v a n h a m m e ，s v a nh u f f e l ，bd em o o r ，i q m l l i k ea l g o - r i t h m sf o rs o l v i n gs t r u c t u r e dt o t a ll e a s ts q u a r e sp r o b l e m s ：au n i f i e dv i e w ， s i g n a _ lp r o c e s s i n g ，v 0 1 8 1 ，n o9 ，p p 1 9 3 5 - 1 9 4 5 ，s e p t 2 0 0 1 【1 5 lyl i ，kj r l i u ，jr a z a v i l a x ，ap a r a m e t e re s t i m a t i o ns c h e m ef o rd a m p e d s i n u s o i d a ls i g n a i sb a s e do nl o w - r a n kh a n k e la p p r o x i m a t i o n ，i e e et r a n s a c - l i o n so ns i g n a lp r o c e s s i n g ，v 0 1 4 5 ，p p4 8 1 4 8 6 ，f e b ，1 9 9 7 【1 6 l pm i l a n f a r ，g b e r g h e s e ，w k a r la n daw i l l s k y ，r e c o n s t r u c t i n gp o l y g o n s f r o mm o m e n t sw i t hc o n n e c t i o n st oa r r a yp r o c e s s i n g ，i e e et r a n s s i g n a lp r o - c e s s i n g ，v o l4 3 ，n o 2 ，p p 4 3 2 4 4 3 ，1 9 9 5 【l7 】s d u r o c h e r ，g r a p h - t h e o r e t i ca n dg e o m e t r i ca l g o r i t h m sa s s o c i a t e dw i t h m o m e n t b a s e dp o l y g o nr e c o n s t r u c t i o nm s t h e s i s ，c o m p u t e rs c i e n c ed e - p a r t m e n t ，t h eu n i v e r s i t yo fb r i t i s hc o l u m b i a ，a u g 1 9 9 9 1 1 8 】m e l a d ，p m i l a n f a ra n dg h g o l u b ，s h a p ef r o mm o m e n t sa ne s t i m a