（基础数学专业论文）主（小）成分分析的实时算法.pdf

中文摘要 摘要 在图像处理、通讯技术等信息处理领域中，主成分分析( p c a ) 和小成分 分析( m c a ) 是很常用的方法。本文将会给出了能同时得到主成分分析或小成 分分析所要求的特征值和特征向量的实时算法。 本文的主要内容如下：在第一章中，我们将对主成分分析及小成分分析作 一个简介。接下来的第二章中，我们将在 7 的基础上，给出一个新的目标函 数，并由这个目标函数出发推出梯度方程。梯度方程的稳定性证明将在第三章 中给出。在接下来的第四章，我们将随之给出实时算法。这以上的讨论都是针 对第一个主成分d 成分的。在第五章中，我们将在第四章中算法的基础上进一 步给出能计算余下主成分，j 、成分的实时算法。在第六章中，我们将把我们的算 法和已经存在的一些算法作比较，同时还将给出几个数据模拟实例。 关键词：主成分分析；小成分分析；实时算法 英文摘要 a b s t r a c t p r i n c i p a lc o m p o n e n ta n a l y s i s ( p e a ) a n dm i n o rc o m p o n e n ta n a l y s i s ( m c a ) p r o - v i d ep o w e r f u ls t a t i s t i c a lt e c h n i q u e si nm a n yi n f o r m a t i o np r o c e s s i n gf i e l d ss u c ha si m - a g ep r o c e s s i n g ，d i r e c t i o n - o f - a r r i v a lp r o b l e m s ，c o m m u n i c a t i o nt e c h n o l o g y , a n ds oo n i nt h i sp a p e r , w cw i l lp r o p o s ean e wo n l i n ec o u p l e da l g o r i t h mf o rp c aa n dm c a w h i c ht a i ls i m u l t a n e o u s l ye x t r a c tt h ee i g e n v e c t o r sa n de i g e n v a l u e so ft h ec o v a r i a n c e m a t r i xw i t hc o u p l e di t e r a t i o n s t h i sp a p e ri so r g a n i z e da sf o l l o w ：i ns e c t i o n1 ，w ew i l li n t r o d u c ep e aa n dm c a p r o b l e m i nt h ef o l l o w i n gs e c t i o n2 ，an e wi n f o r m a t i o nc r i t e r i o nw h i c hm a k et h ea n a - l y z em u c h e a s i e ra n dc l e a r e rw i l lb ep r o p o s e db a s e do n 7 】t h ea n a l y s i so ft h es t a b i l i t y o ft h ec o u p l e dp c a m c as y s t e mi si ns e c t i o n3 a n di ns e c t i o n4 ，t h eo n l i n ea l g o r i t h m o fc o u p l e dp c a f m c as y s t e mi sf o c u s e do n ，b u tt h ec o u p l e ds y s t e ma n di t so n l i n ea l g o r i t h m c a no n l yw o r ko nt h ef i r s tp r i n c i p a l m i n o rc o m p o n e n t i ns e c t i o n5 ，w ep r o p o s e t h ea l g o r i t h mw h i c hc a ng e tt h ef i r s tpp r i n c i p a l m i n o rc o m p o n e n t sb a s e do nt h ea l g o r i t h mi ns e c t i o n4 i ns e c t i o n6 ，w ec o m p a r eo u ra l g o r i t h mt os o m ee x i s t e n ta l g o r i t h m s a n dg i v es e v e r a ls i m u l a t i o n s k e yw o r d s ：p r i n c i p a lc o m p o n e n ta n a l y s i s ；m i n o rc o m p o n e n ta n a l y s i s ；o n l i n ea l g o r i t h m 第一章介绍 第一章介绍 在图像处理、通讯技术等信息处理领域中，主成分分析( p c a ) 和小成分 分析( m c a ) 是很常用的种方法。p c a 通过分析输入数据性质，找出数据中 起主导作用的一个或几个主要成分，固被称为主成分分析。而m c a i j 致力于寻 找数据中作用最不明显的一个或几个成分，进而可以剔除他们，起到数据降噪 的作用。在数据已知的情况下，蚍一p _ i 作就变得很简单而显得没有意义。但当 数据不断流八时，p c a d m c a 要求我们在不断流入的数据中找出我们需要的成 分，也就是所谓的实时算法。由于实时算法针对不断流入的数据，所以比较适 合处理维数比较高的数据( 这种商维数据由于协方差矩阵过于庞大而不适合直 接计算) ，以及那些协方差矩阵随时间微小变化的数据。 p c a 已经有了很多可以实现的实时算法，例如o j a 在 1 】中和s a n g e r 在【2 】 中分别提出了算法。随后在【3 3 中，d i a m a n t a r a s 和k u n g 两个人给出了一个综 述。至于m c a 分析，在 4 中，c i r r i n c i o n eg 和c i r r i n c i o n em 给出了综述，其 中包括了几种可以实现的实时算法。 在实际中，我们用学习算法训练连接权使其收敛到数据协方差矩阵最大 ( 最小) 的特征值对应的特征向量，从而实现p c a ( m c a ) 的要求。采用这种方 法只考虑使连接权收敛到特征向量的方向上去，而对于特征值不关心。但这里 有个问题：连接权的长度有可能发散。为解决这个问题，有的算法将连接权长 度限制在单位长度上，如 1 ；有的算法则将连接权长度限制到一个与特征值有 关的数上，如【5 】；还有些算法索性固定连接权长度为常数，如【4 。除了在【6 】 中的算法是基于特征值估计之外现有的几乎所有算法都只关心连接权是否收敛 到特征向量的方向，而不考虑特征值。 而在【7 】中，r a l f 干d a x e l 两个人提出了一个能同时得到特征值和特征向量 的学习算法的框架，并提出了可以计算p c a ( m c a ) 要求的第一对特征值和特征 向量的算法。我们称这种能同时计算出所需的特征值和特征向量的算法为连接 算法 本文将基于 7 】中提出的框架，给出一个新的目标函数使算法推导过程更 简单明了，并得到能计算p c a ( m c a ) 要求的所有特征值和特征向量的实时连接 算法。 本文的主要内容如下：在第二章中，我们将在 7 】的基础上，给出一个新的 第一章介绍 目标函数，并由这个目标函数出发推出梯度方程。梯度方程的稳定性证明将在 第三章中给出。在接下来的第四章，我们将随之给出实时算法。这以上的讨论 都是针对第一个主成分，j 、成分的。在第五章中，我们将在第四章中算法的基础 上进一步给出能计算余下主成分，j 、成分的实时算法。在第六章中，我们将把我 们的算法和已经存在的一些算法作比较，同时还将给出几个数据模拟实例。 2 第二章连接算法的梯度方程 第二章连接算法的梯度方程 设o ( ) ，k = 1 ，2 ，是一个均值为零的平稳的随机过程产生的数据，其 中k 表示时间，所有的z ( 女) 都是礼莹向量。c = e x x 7 是数据的协方差矩阵， 则e 是对称的且有n 个正的特征值。我们把这n 个特征值从大到小排序，设 为a l a 2 h ，它们对应的正交特征向量分别是w 1 ，w 2 ， ，。在诸如 特征提取、数据压缩等应用中，我们需要得n c 的前p 个特征值及其对应的特征 向量，也就是前面提到的p c a 问题，这里我们假定a 。a 1 ，m n c 的第p 个特 征值和第p + 1 个特征值混在一起就分不出来了。至于m c a 问题，就要求我们得 到g 的最后p 个特征值及其对应的特征向量，我们同样假定a 。一。a 。一。+ - 。 首先，让我们先关注如何求出第。个( 最后个) 特征值及其对应的特征 向量。r a l f 和a x e l 两个人在 7 】中给出了一个目标函数： p 2 w r c w a 一1 一w 丁w 4 l n a 并由此目标函数导出了一个能同时得到第一个( 最后一个) 特征值及其对应的 特征向量的实时算法。但这个目标函数取得不好，使得推导过程显得过于繁 琐。这里，我们提出一个新的目标函数，使得推导过程显得更清晰明确 p = w r c w 一 t w a + a 这里e = e x x 7 ) 是数据的协方差矩阵；而 是一个n 维权向量，也就是特征向 量的估计；a 是特征值的估计。则目标函数p 满足： 所以平衡点( 仍，五) 满足 c 面= 面j 面面= l ( 2 1 ) 并且可以推出面r g 面= 天。有上面三个式子可咀看到目标函数的平衡点就是协 3 n 2 卜 一 w 踟 矿 2 一 = | | 却丽却丽 第二章连接算法的梯度方程 方差矩阵的特征值和对应的特征向量。 下面我们证明由( 2 1 ) 导出的梯度算法在第一个特征值和对应的特征向量上 不一定是稳定的。 首先我们考察( 2 1 ) 在平衡点( a t ，w 1 ) ( 第一个特征值和对应的特征向量) 处 的h e s s i a n 矩阵： a ( a t ，”- ) = ( 2 一c 。a 。 1 - 1 e - 。i 2 。1 很明显可以得到 d e t ( a ( a 1 ，w 1 ) ) a 。是由g 的特征值按大小顺序排在对角线上 生成的对角阵，u 是g 的正交特征向量组排成的正交阵。设： 疗= ( u 。) 则 。= 驴r 。驴= z a - a i u 。t ”) 在p c a 问题中，我1 丁设叫 1 ，a a l ，则u t w e l = ( 1 ，0 ，o ) t 。那么我们 4 、i， 汀 。 一 a 3 眦百聊耳 乳 第二章连接算法的梯度方程 得到 毗( a = 7i 1 ) 所以d 一1 肯定有如下形式： 伊z ；( 名i 1 ) 这里a 满足j 4 a a a e l e = ，以及a e l = 0 。由此，我们可以得到 a = 0 2 一a 由p c a i h 题的条件a l a 2 a 3 a 。，我们得到 们有 a p g a - 1 ( e i e 一j ) 又因为d 一1 = 疗西一1 9 r 7 我们最终得n p c at a 3 题中d 一1 的近似 。；苫。z ；( a 一“w w 。t ，一7 - - 。w ( 2 2 ) 至于m c a 问题，我们设w w 。，a k ，n u 7 w e 。= ( 0 ，0 ，n ) 7 。我 d 2p 0 71 n 一t o 所以西。一定有如下形式： 西一l 一1f a 一 2 一e 。t 0 5 ，jjj，iii、 、 、 第二章连接算法的梯度方程 这里a 满足a a a a e 。e t ，。= 及a e 。= 0 。所以 f 0 i 由m c a 条件h a 。一l a 。一2 a l ，我们得到 a m c a a 一1 一a e 。e ： 又由于d 一1 = 驴d 一1 驴7 我们最终得到m c a 问题中d 一1 的近似 n - 11 c l a - 1 w c l j 丁一甜、 “g 42 互 一。， o ( 2 3 以上我们得到t d 一1 的近似，对( 2 1 ) 在p c a 近似式( 2 2 ) 下得到p c a 连接系 统的梯度方程是： 曲= g 似a 一1 一w w ? g 叫a 一1 一；- w ( 1 一w t 1 ： 7 e 一”r a 。 ( 2 f 4 ) 而在m c a 近：似式( 2 3 ) 下得到m c a j 奎接系统的梯度方程是 曲= e - 1 w a + w 7 c r 一一；邮+ 3 w t ) j = u t c w 一t 1 u a 我们得到的p c a 及m c a 梯度方程和r a l f 同a x c l 在 7 】中得到的是一样的。但 明显我们的推导过程比 7 】中的更简单明了。 6 第三章连接算法梯度方程的稳定性 第三章连接算法梯度方程的稳定| 生 在前一章中，我们得到了连接算法的梯度方程。在这章中，我们将讨论梯 度方程的稳定性。 3 1p c a 连接算法梯度方程的稳定性 下面我们将i t 羽p c a 连接算法梯度方程( 2 4 ) 在协方差矩阵c 的第一个特征 值及其对应的特征向量处是稳定的，而在其他平衡点是不稳定的。 对于梯度方程( 2 4 ) ，它的平衡点是以下方程的解： c w a 一2 l j t c a 一1 7 c w 一7 a ：0 所以，平衡点( j ，面) 满足 面。面= 1 面r a 面= 天 g 面= 面a 这意味着( 2 4 ) 的平衡点是g 的所有特征值及其对应的特征向量。 则( 2 4 ) 在平衡点( 丸，) 处的h e s s i a n 矩阵是： h p c a ( a i , t o i ，= ( g a i l 一：一似，! ，) 沿用前章里的口，我们可以化简得到： 诉c a ( 凡) ：驴f a 扩1 f - - e t e o1 驴r 0 1 7 第三章连接算法梯度方程的稳定- 性 这里e 的分量除了岛( t ) = 1 外全为零。则日( a 。 ，) 的特征值啦，1 ，n ”+ 1 是 啦l t ：a i , n + l ：一1 ，。；荨一l ，j ：l ，n ，j i 、z 由此我们可以得到只有在平衡点( a 1 ， 3 - ) ，h e s s i a n * g 阵日的所有特征值都 是负的。而在其他平衡点处，都至少有一个特征值非负。这意味着只 有( a l ，训1 ) 是( 2 4 ) 的稳定平衡点。 3 2m c a 连接算法梯度方程的稳定性 接着是m c a 连接算法梯度方程的稳定性 对于梯度方程( 2 5 ) ，它的平衡点是以下方程的解： c - - 1 w a - i - w w t c w a 一1 u 3 t c w 一埘7 ”a = 0 所以，平衡点( 亩，i ) 满足： ；w ( 1 + 3 w v w ) ：0 面1 由= 1 面了1 g 面= 工 g 面= 面a 这意味着( 2 5 ) 的平衡点是g 的所有特征值及其对应的特征向量。 则( 2 5 ) 在平衡点( a 。) 处的h e s s i a n 链i 阵是： 砌“k 毗) ：f 伊u t 一舛o1 01 沿用前一章里的驴，我们可以化简得到 川= 驴( 护u 一 三) 驴7 8 第三章连接算法梯度方程的稳定一l 生 i j h m c a ( a i ， ) 的特征值6 钳，一，魄 1 是： b i ，t = 6 t ，n + 1 = 一1 ，b i ，= 1 ，j = 1 ，一，n ，j i 由此我们可以得到只有在平衡点( a 。，w n ) ，h e s s i a n 矩阵日的所有特征值都 是负的。而在其他平衡点处，都至少有一个特征值非负。这意味着只 有( a 。，u 。) 是( 2 5 ) 的稳定平衡点。 9 第四章实时算法 前面，我们给出了连接算法的梯度方程，并证明了梯度方程只有 在p c a 或m c a 需要的平衡点上是稳定的。在这章中，我们将由梯度方程导 出实时算法。 4 1p c a 的实时算法 由于数据是不断流入的，所以我们不能直接得到数据的协方差矩阵g 。在 此我们将g 看成一个关于时间的变量，并由以下递归式决定： e ( ) = a c ( k 一1 ) + 肛( ) z ( 七) 丁 这里。是给定的遗忘因子，而卢= l q 。在实际应用中，一般。( 0 9 9 ，1 0 ) 。 那么基于( 2 4 ) 的实时算法就是： 加( 七+ 1 ) = 加) + 叩 ( q g ( 七) + 卢z ( 南+ 1 ) 茹( 南+ 1 ) t ) 埘( 七) a 一1 ( 七) 一 ( 七) 叫( 惫) t ( n g ( 七) + f l x ( k + 1 ) z ( 七+ 1 ) t ) ( 七) a 1 ( 七) 一i ”) ( 1 一叫) 7 伽( 自) ) ) ( 4 1 ) j 、 a 忙+ 1 ) = a ( 七) + _ ( 自) 7 ( 口c r ( 七) + 励( 女+ 1 ) 。+ 1 ) 7 ) 砸( ) 一 ( 血) t u ( 惫) a ( 七) ) 这里表示迭代的步长。如果直接计算， ( 基本运算就是电脑中进行一次加法) 。 法进行改进，减少算法的计算量。 算法每次迭代需要0 ( 2 ) 次基本运算 这个计算量太大了，下面我们将对算 显然当遗忘园子口非常接近1 ，而观察数据的统计性质变化不大时，e ( + 1 ) 同g ( 七) 之间的差别非常小，所以一般有以下假设： a ( 七) 叫( 七) e ( 七) 锄一1 ) 这个假设在e 随时间变化很小时对减少计算量很有帮助。由以上假设，我们 可以不显式地求出g ( 七) t 就得到g ( ) ( 一1 ) 。丽在( 4 】) 中我们可以看到整个 i o 兰婴童塞堕堡鲨 迭代过程，r 用至u c ( k ) w ( k 1 ) 。所以我们可以省去每次迭代中计算g ( ) 的工 作，取而代之的是计算g ( ) ( 一1 ) 。这省下了不少计算量。整理后的算法及 没步需要的计算量一同列在表一中： 表一p c a 实时算法( 第一个特征值) 给定初始值：o ( o ) ，6 ( o ) ，w ( 0 ) ，a ( 0 ) 对k = o ，1 做： f i t e r a f i o n ：c o m p l e x i t y ： i 口( 后+ 1 ) = a a ( k ) + 卢洳+ 1 ) t 叫( 七) ) 茁( 角+ 1 ) 3 n i6 + 1 ) = a 6 ( 女) + p ( z + 1 ) 7 ( 女) ) 2 o ( n ) l 叫( 七+ 1 ) = 叫( 七) + 即 o ( 七+ 1 ) a _ 1 ( 七) 一6 ( 南+ 1 ) w ( k ) a 一1 ( 七) lj ( k ) ( 1 一叫( ) 7 ( k ) ) ) 4 n 【! ! ! ! ! 三查! ! ! ! ! 丛! 1 2 二竺! 堕：竺! 1 2 11 11 1 1 1 1 1 其中o ( 女) = o ( k ) w ( k 一1 ) 及b ( ) = ( 一1 ) 7 g ( ) 叫( 一1 ) a 在计算量统计中o ( n ) 表示计算量是和n 无关的数。 从表一可以得到我们的计算第一个特征值的p c a 实时算法每次迭代需要7 n 次基本运算。 4 2m c a 的实时算法 同p c a 算法一样，我们做如下近似： g ( 盘) 叫( 惫) a ( 匙) ( 患一1 ) m c a 算法中还需要用n c _ 1 c 一1 ( 后+ 1 ) = ( a g ( 七) + f l x ( k + 1 ) x ( k + 1 ) 丁) 一1 = 1 。c 。1 ( 旷参g _ 1 ( 啦( + 1 ) m + 1 ) 可1 ( 叶o ( 3 2 ) 这里0 ( p 2 ) 表示p 的高价项，由于卢z0 ，所以可以略去a 我们得到 c - 1 ( 七十1 ) z 三( ) 一景g 一1 ( 女) z ( + 1 ) z ( + 1 ) 盱1 ( 自) 第四章实时算法 那么基于梯度方程( 2 5 ) 的m c a 迭代过程如下 w ( k + 1 ) = ( 七) + v c 一1 ( 七+ 1 ) w ( 南) a ( 七) + 叫( 七) 叫( 南) r c ( k + 1 ) w ( k ) a 一1 ( 七) 一；w ( 女) ( 1 十3 ”( k ) 7 ” ) ) a ( 后+ 1 ) = a ( 七) + 町 w ( 忌) r c ( k + 1 ) 埘( 南) 一训( 七) r 坩( 角) a ) ) 表二中给出的是经过精简计算量的计算最后一个特征值的m c a 实时算法： 表二 m c a 实时算法( 最后一个特征值) 给定初始值：。( o ) ， ( 0 ) a ( o ) ，c - 1 ( o ) 对k = 0 1 做： 这个算法每次迭代需要3 5 n 2 + 6 n 次基本运算。 衄。“ 瓿盟翥 砷 一 留旷 一 即驴 一 、忙 动一 m 眦一 + 蜘 “一 尸糌，一删懈螂删蚪一 忡惭岬型 g十吣，一+景n一 书岍一 扛0 一c + 圳一 删卅胪一 十0一 扣小雌 一 戮拦 姐d + u u 一 拙+ 协汁 + 一 量m 吣 m 一 第五章其他的主成分，j 、成分 第五章其他的主成分小成分 前面的p c a f m c a 实时算法都是针对第一个主成分j 、成分的。但在实际 中，往往要求得到前几个主成分，j 、成分。在这章中，我们将给出计算余下的主 成分，j 、成分的实时算法 5 1p c a 问题 假设前i l ( i 0 1 ) 对特征值、特征向量已经得到，现在我们考虑第i 个特征值及 其对应的特征向量设玑= ( j 一嘶嵋) 茹，则k 的协方差矩阵是： ，= q = e 玑) = f ， = c 一 ，码霹 则& 最大的特征值及其对应的特征向量是原来c 的第i 个特征值及其对应的特征 向量将玑作为新的数据，运用表一中的算法，就能得到我们想要的c 的第i 个特 征值及其对应的特征向量。这样，我们就能通过反复运用表一中的算法，来得 到我们想要的前p 个特征值及其对应的特征向量( 也就是前p 个主成分) 。整合 起来的算法见表三： 1 3 哼嘶 埘 一， q ，0 u q 羞 第五章其他的主成分，j 、成分 表三p c a 实时算法( 前p 个特征值) 给定初始值：a l ( 0 ) ，b l ( o ) ，w l ( o ) ，aa ( o ) ，邮( 0 ) ，b y ( o ) ，u - ( o ) ，a p ( o ) 对k = o 1 做： 玑( + 1 ) = z + 1 ) a l ( 七+ 1 ) = 。o l ( 七) + 卢扫1 + 1 ) r 加( 七) ) 可1 ( 七+ 1 ) b l ( + 1 ) = a b l ( ) + 卢( y l ( + 1 ) 7 ( ) ) 2 1 ( + 1 ) = 叫l ( ) + v a i ( k + 1 ) a i l ( ) 一b l ( k + 1 ) l ( 自) a i l ( ) 一 叫l ( 七) ( 1 一叫1 ( 七) t 叫，( 膏) ) ) a l ( 惫+ 1 ) = a l ( 南) + 卵 6 i ( 南十1 ) 一埘1 ( 七) ? w 1 ( 南) a i ) ) y 2 ( k + 1 ) = ( i 一l ! 。) 敬( + 1 ) n 2 ( + 1 ) = a a 2 ( k ) + 卢( 9 2 ( 女+ 1 ) 丁 ( m ) ) 口2 ( + 1 ) b 2 ( k + 1 ) = a b 2 ( k ) + 卢( 伽( + 1 ) 7 ( ) ) 2 2 ( + 1 ) = w 2 ( k ) + q 。2 ( + 1 ) 入i 1 ( k ) 一b 2 ( k + 1 ) 2 ( m ) 入i 1 ( ) 一； 2 ( ) ( 1 一 2 ( 女) 7 吡( ) ) ) a 2 ( 七+ 1 ) = a 2 ( 七) + 印d 2 ( 七+ 1 ) 一叫2 ( 七) 丁叫2 ( 七) a 2 ( 七) ( + 1 ) = ( ，一w 1 w ) 一1 + i ) o ( n ) 唧( 七十1 ) = o 唧( 七) + 卢( 蜘( 七+ 1 ) r 伽( 七) ) 铷( 克+ 1 ) 3 n b ( k + 1 ) = o b ( ) + 母( 勤 + 1 ) 7 蜘( 如) 2 o ( a ) 2 ( + 1 ) = w p ( k ) + q o p ( + 1 ) a p - 1 ( ) 一b p ( k + 1 ) t ( ) a i l ( ) 一；嘶( ) ( 1 一嘶( 女) t 坼( 女) ) ) 4 n a p ( 七+ 1 ) = k ( ) + q ( 女+ 1 ) 一“乍( ) 了1 u p ( k ) a ，( 女) ) o ( n ) 这个算法每次迭代需要7 n p + 8 p 次基本运算。 5 2m c a 问题 我们已经得到了能计算最后一个特征值及其对应的特征向量的m c a 算法。 但f b f i m c a 算法中要用n c 一1 ( ) ，所以前面的把p c a 算法推广的方法并不能套 用过来。现在，我们试图在( 2 5 ) 中加上几项使得它收敛到口的第n i + 1 个特征值 1 4 咖轨咖 轨咖如轨咖 轨咖 第五章其他的主成分川、成分 及其对应的特征向量。得到的梯度方程如下 - 肛霎譬w 。j w + w w t c w a - i - 烈1 - j拙 ， ，= o n “ f 5 1 ) ：w t c 一w t w a 接下来我们证n ( 5 1 ) 收敛到g 的第n 一“1 个特征值及其对应的特征向 量( a n 一。+ 1 t j 竹一t + 1 ) 。 容易得到梯度方程( 5 1 ) 的所有平衡点是c 的前n i + 1 个特征值及其对应的特 征向量。它在平衡点( a 。一件l w , n 一州) 的h e s s i a n 矩阵是： 队州州，= i - 2 a a 吩悱嘏州二) 驴7 h ( a “+ 1 l 一薹斡0 _ j e 一_ ? 1 一 则日( k 一一t + 1 ) 的特征值是 = 守一1 a n i + 1 。一1 ， a n _ i + j = 一2 口n + 1 2 - 1 j = 1 ，佗一z j = 2 ，i 由a 。 a n - 1 a l ，我们看到所有的特征值都是负的。容易看 出( a ，w j ) ，j = 1 ，7 z - - 稽b 不稳定。而( a 。 t o n - j ) ，j = 0 ，i 一2 都不是( 5 1 ) 的 平衡点。所以( a 。l ，一1 ) 是( 5 1 ) 唯一稳定的平衡点。 通过变化( 5 1 ) 中的i ，可以得到m c a 问题要求的最后p 个特征值及其对应的 特征向量。整合后的算法在表四中给出： 1 5 + = 卜 归 件 a ( 釜至至基丝塑圭盛坌! 尘盛坌 表四 m c a 实时算法( 最后p 个特征值) 给定初始值：o ( o ) ，c 一1 ( o ) ，w 。( o ) ，h ( o ) ，w n 一，+ 1 ( o ) ，a n - p + l ( 0 ) 对k = o 1 做： 1 t e r a t i o n ： a ( k + 1 ) = a a ( k ) + 卢( z ( + 1 ) 7 ( ) ) 2 c 一1 ( 七+ 1 ) = j g 一1 ( 七) 一参e 一1 ( 七) z ( 七+ 1 ) z ( 詹+ 1 ) t c 一1 ( 七) t ( + 1 ) = w n ( k ) + c 1 ( 自+ 1 ) w 。( ) a 。( m ) + 口( 七+ 1 ) a i l ( 七) 2 f n ( 七) 一 n ( ) ( 1 + 3 t ( ) 7 w 。( k ) ) ) 支n ( 玉+ 1 ) = k ( 七j + 露 8 辑+ 1 ) 一t ( 奄j r 。( 女) a 。( ) n l ( + 1 ) = n 1 ( ) + q c 一1 ( + 1 ) w 。一1 ( k ) a 。一1 ( m ) 一盐垡 j 鲁产盟w 。( ) ”：( 女) w 。一l ( ) + o ( + 1 ) a 矗1 ( ) 。一l ( k ) 一j w n 一1 ( 七) ( 1 + 3 w 。一l ( 女) t w 。一l ( ) ) ) a n l ( 七+ 1 ) = a n l ) 十叮 o ( 七+ 1 ) 一。一l ( 七) 丁w 。一1 ) a 。一l ( 南) ) c o m p l e x i t y n 3 5 2 + 2 n 3 n 。) 2 n o ( n ) 训n - p + l ( k + 1 ) = w n - 一卅i ( 惫) + 叩 c 一1 ( 七+ 1 ) 札k - - p + l ( 七) a 。一p + 1 ( 七) 一薹蜘鼍臻产趔舭) 吧( 啪。“) + 口( + 1 ) a 芒p + 1 ( ) - p + l ( ) 一 n p + l ( ) ( 1 + 3 w n - p + l ( ) 7 。一p + 】( ) ) )2 n ( p 1 ) a n p + l ( k + 1 ) = a 。一p + l ( ) + 1 n ( a + 1 ) 二坠二壁! 塑! 坠二肘z ( 女) a n p + l ( 七) ) 。( n ) 这个算法每次迭代要花费3 5 n 2 + n 一1 ) p + 6 n 次基本运算。 而如果把这种推广方法运用到p c a 算法上去，将产生n ( p 一1 ) p 次运算的负 担- 比前面的p c a 算法多出不少，所以这种推广方法并不适用于p c a 算法。 j 6 第六章比较及数值模拟+ 第六章比较及数值模拟+ 在这章中，我们将列出几种已经有的p c a 和m c a 算法，并将它们与我们的 算法进行比较。同时，我们将给出3 个数值模拟的例子。 现在已经有了许多的p c a 实时算法如： 8 中的b i s v d 3 算法； 9 仲 n w m c 算法；1 1 0 的c a l 算法： 1 1 中n x u 算法及1 1 2 1 0 0 雕j w s a 算法。 每一种算法的计算量如下： 算法 每次迭代需要的计算量 b i 。s v d 3 w v c c a l x u w s a l o n p + 7 5 p 2 + 1 65 p 5 r i p + 舻+ 4 p 4 n p + 2 p 4 n p + 2 p 4 n p 同样，现在也有许多m c a 实时算法如： 8 中l 筝b i s v d 3 算法及 1 3 1 中 的s r i m s 算法。他们的计算量如下： 算法 每次迭代需要的计算量 b i s v d 3 m 3 5 n 2 + 5 5 n + l o n p + 7 5 p 2 + 1 6 5 p s r i i m s 礼2 p + 2 5 n 2 + 2 r i p 2 + n p + 4 5 n 而我们的p c a 算法每次迭代需要：7 n p 十印次基本运算，i i i m c a 算法需 要3 5 礼2 + n ( p 一1 ) p + 6 n 次。这与前面几个算法在数量级上是一样的，而具 体数字上也差不多。而且我们的算法还能在计算特征向量的同时得到一些问题 中需要的特征值。从这个角度上讲我们的算法是优秀的。 以下是我们进行的3 个数值模拟： 在数值模拟中，我们取最常用的n = o ，9 9 9 及口= 1 一d = 0 0 0 1 。 1 7 第六章比较及数值模拟 数值模拟一 取n = 6 ，z ( 自) 是随机数据。在图一中我们给出运用表一中的算法得到的主成 分，同时我们还给出t w i n c 算法及b i s v d 3 算法得到的主成分作为比较。 10 1 1 矿 ，0 1 蚕” 1 一 ，d 特征值 特征向量 图一数值模拟一一 1 8 第六章比较及数值模拟 数值模拟二 同样取n = 6 ，同时给定协方差矩阵的最后两个特征值为a 6 = 0 0 l 及沁= 0 0 5 而其他的特征值都大于0 1 ( 用随机数据的话，最后几个特征值相差很小， 很难区分) 。在图二中我们给出运用表二中的算法得到的小成分，同时我们还 给出了b i - s v d 3 m 算法得到的小成分作为比较。 特征值 特征向量 图二 数值模拟二的第一个小成分 在图三中我们给出运用表四中的算法得到的第二个小成分，同时我们还给出 了b i - s v d 3 m 算法得到的小成分作为比较。 1 9 第六章比较及数值模拟 特征值 特征向量 图三 数值模拟二的第二个小成分 铲 r ” 神 ” 第六章比较及数值模拟 数值模拟三 现在我们考虑一个比较大规模的例子：取n = 2 0 ，同时给定协方差矩阵的特 征值为a l = 2 0 ，a 2 = 1 9 ，a 3 = 1 8 ，a 2 0 = 0l 。在图四中我们给出运用表四中 的算法得到的4 个最小特征值。 特征值 图四数值模拟三 2 1 在数值模拟巾，我们看到在a 收敛到真实的特征值的过程中有波动，这是因 为 一 。的符号在变化导致的。 从数值模拟中我们可以看到我们的算法的收敛速度e l b i s v d 3 算法稍慢，这 是因为我们的算法在计算特征向量的同时还要顾及到特征值。而我们的算法得 到的特征值的精度比特征向量低，但我们可以使选代中的随时间变化而改善特 征值的精度。 结论 结论 在本文中，我们通过研究连接系统得到了能同时计算特征值的p c a 算法以 及m c a 算法。我们的算法与以前的算法的计算量差不多，而在同时我们的算法 能得到一些问题中需要的特征值。而且我们的算法在收敛速度及精度上也表现 的很好。 在一些现实问题中( 例如图像处理的某些领域中) ，对主成分及小成分分 析的要求不局限在特征向量上，它要求同时得到特征值。在这些问题中，以前 的算法就显得不是很有力，而我们的算法却能同时得到这些问题中需要的特征 值及特征向量。所以可以说，我们的算法更适合这些问题。 叁耋皇堕 参考文献 1 】o j ae as i m p l i f i e dn e u r o nm o d e la sp r i n c i p a lc o m p o n e n ta n a l y z e r j 】上m a t h - b i o l ，1 9 8 2 ，1 5 ： 2 6 7 2 7 3 2 1s a n g e rtd o p t i m a lu n s u p e r s i s e dl e a r n i n gi nas i n g l e l a y e rl i n e a rf e e d f o r w a r dn e u r a ln e t w o r k 【j n e u r a ln e t w o r k s ，1 9 8 9 ，2 1 6 ：4 5 9 - 4 7 3 【3 】d i a m a n t a r a ski ，k u n gsy p r i n c i p a lc o m p o n e n t n e u r a ln e t w o r k s t h e o r ya n da p p l i c a t i o n s m n e wy o r k ：w i l e y , 1 9 9 6 【4 】c i i t i n c i o n eg ，c i r r i n c i o n em ，h 6 r a u l tj ，v a i lh u f f e ls t h em c a e x i nn e u r o nf o rt h em i n o r c o m p o n e n ta n a l y s i s 【j 】i e e et r a n sn e u r a ln e t w o r k s ，2 0 0 2 ，1 3 ：1 6 0 - 1 8 6 【5 】o u y a n gs ，b a oz ，l i a og s r o b u s tr e c u r s i v el e a s ts q u a r e sa l g o r i t h mf o rp r i n c i p a lc o m p o n e n t a n a l y s i s j 】i e e et r a n sn e u r a ln e t w o r k s ，2 0 0 0 ，1 1 ：2 1 5 2 2 1 6 】c h e nlh ，c h a n gs a na d a p t i v el e a r n i n ga l g o r i t h mf o rp r i n c i p a lc o m p o n e n ta n a l y s i sf j 】i e e e t r a n s n e u r a l n e t w o r k s 1 9 9 5 6 ：1 2 5 5 一1 2 6 3 7 m o i l e r r ，k 0 n i e s a c o u p l e d p r i n c i p a l c o m p o n e n t a n a l y s i s j li e e e t r a n s o n n e u r a l n e t w o r k s ， 2 0 0 4 ，1 5 【1 ：2 1 4 - 2 2 2 【8 】s t r o b a c hrb i - i t e r a t i o