（计算数学专业论文）基于lanczos双对角化过程的非负矩阵快速分解的初始化方法.pdf

基于l a n c z o s 双对角过程的快速的非负矩阵初始化方法 摘要 n a t u r e 在1 9 9 9 年刊登了两位科学家l e e 和s e u n g 对数学中非负矩阵研究 的突出成果该文提出了一种新的矩阵分解思想一一非负矩阵分解( n o n - n e g a t i v e m a t r i xf a c t o r i z a t i o n ，n m f ) 算法，即n m f 是在矩阵中所有元素均为非负数约束 条件之下的矩阵分解方法由于非负矩阵分解在现实生活中有着广泛的应用，该 论文的发表迅速引起了些研究领域中的科学研究人员的重视：方面，科学研 究中的很多大规模数据的分析方法需要通过矩阵形式进行有效处理，而n m f 思 想则为 类处理大规模数据提供了种新的途径；另方面，n m f 分解算法相 较于传统的些算法而言，具有实现上的简便性、分解形式和分解结果上的可解 释陛，以及占用存储空间少等诸多优点 在【2 】中，c b o u t s i d i s a 和e g a l l o p o u l o s 提出了种基于奇异值分解( s v d ) 的非负矩阵分解的初始化策略在这种策略下，和原来未经过初始化的非负矩阵 分解的算法相比较，收敛速度得到了很大的提高对于个大型的非负矩阵，我 们可以利用l a n c z o s 双对角化得到其个低秩近似；正如【2 】2 所应用的；b 撇- - t $ ， 我们可以进步得到它的非负近似由此我们得到了非负矩阵分解种新的初始 化方法；它虽然带有一点随意i 生，但是可以和现存的非负矩阵分解算法相结合 从数值实验可以看出，和基于奇异值分解的f 2 】初始化算法相比，这种新的初始化 算法效果更好 本文主要由5 部分构成第部分，我们介绍了非负矩阵分解和非负矩阵分解 初始化的些背景，以及前人做的一些贡献第二部分，我们回顾了l a n c z o s 双对 角化过程，并得到个低秩的近似第三部分，我们介绍了我们的策略：从l a n c z o s 双对角化过程中得到矩阵的非负近似，即初始化的( 彬日) 第四部分，我们做了 一j 些实验，与c b o u t s i d i s 和e g a l l o p o u l o u s 的方法作了比较，说明了我们方法的优 势第五部分，我们对我们的论文做了个总结 关键词：l a n c z o s 双对角化；非负矩阵分解；奇异值分解；低秩近似 a b s t r a c t i n1 9 9 9 ，n a t u r e p u b l i s h e dap a p e rs h o w i n ga no u t s t a n d i n gr e s u l ti nt h e r e s e a r c ho fn o n n e g a t i v em a t r i xo fm a t h e m a t i c s ，w r i t t e nb yp r o f e s s o rl e e a n d p r o f e s s o rs e u n g i nt h i sp a p e r ，t h ea u t h o r sp r e s e n tan e wm e t h o do fm a t r i x d e c o m p o s i t i o n ，n a m e dn o n - n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f ) a l g o r i t h m ， am e t h o da p p l i e do nt h ec o n d i t i o nt h a ta l lt h ee l e m e n t si nt h em a t r i xa r e n o n - n e g a t i v e b e c a u s eo ft h eb r o a da p p l i c a t i o no fn o n n e g a t i v em a t r i xf a c t o r - i z a t i o ni nr e a ll i f e ，t h ep u b l i c a t i o no ft h i sp a p e rc a u g h tt h ee y e so fan u m b e r o fr e s e a r c h e r ss t u d y i n gi ns o m es p e c i f i cf i e l df o rt h ef o l l o w i n gr e a s o n s ：o nt h e o n eh a n d ，m a n yl a r g e - s c a l ed a t aa n a l y s i si ns c i e n t i f i cr e s e a r c hn e e d st ob ep r o - c e a s e de f f e c t i v e l yi nt h ef o r mo fm a t r i x e s ，a n dn m fc a np r o v i d ean e w w a yf o r h u m a ni np r o c e s s i n gt h el a r g e - s c a l ed a t a ；o nt h eo t h e rh a n d ，c o m p a r e dw i t h s o m eo fo t h e rt r a d i t i o n a la l g o r i t h m s ，n m fd e c o m p o s i t i o na l g o r i t h ms h o w sa n u m b e ro fa d v a n t a g e s ，s u c ha st h es i m p l i c i t yi nr e a l i z a t i o n ，e a s i l ye x p l a i n a b l e t o w a r dt h ef o r mo fa n dt h er e s u l to fd e c o m p o s i t i o n ，a sw e l la sl e s ss t o r a g e s p a c e i n 【2 】c b o u t s i d i s aa n de g a l l o p o u l o sp r o p o s e das v db a s e di n i t i a l - i z a t i o na l g o r i t h md e s i g n e dt oe n h a n c et h ei n i t i a l i z a t i o ns t a g eo fn o n n e g a t i v e m a t r i xf a c t o r i z a t i o n c o m b i n e dw i t ho t h e rn m f a l g o r i t h m s ，i tc a na c c e l e r a t e c o n v e r g e n e c er a t er a p i d l l y f o ral a r g en o n n e g a t i v em a t r i x ，al a n c z o sb i d i a g o - n a l i z a t i o np r o c e s si su t i l i z e dt oo b t a i nan o n n e g a t i v eb i d i a g o n a lm a t r i xo fl o w r a n k a n dt h e ne v e r yu n i tr a n km a t r i xp r o d u c e df r o mt h el a n c z o sp r o c e s si s a p p r o x i m a t e db yi t sn o n n e g a t i v es e c t i o ni nt h es a m ew a ya sd e v e l o p e di n t h i sr e s u l t si nau o v a li n i t i a l i z a t i o na l g o r i t h mf o rn o n n e g a t i v em a t r i xf a c t o r - i z a t i o n ( n m f ) i tc a nr e a d i l yb ec o m b i n e dw i t he x i s t i n gn m fa l g o r i t h m sa n d 基于l a 嬲o s 双对角过程的快速的非负矩阵初始化方法 m a yc o n t a i nal i t t l er a n d o m i z a t i o n s o m en u m e r i c a le x p e r i m e n t sd e m o n s t r a t e t h a tt h en e wi n i t i a l i z a t i o na l g o r i t h mi sm o r ee f f i c i e n tt h a nt h es v db a s e d i n i t i a l i z a t i o na l g o r i t h mp r e s e n t e di n 障 f i v es e c t i o n s & r ef o l d e di nt h i st h e s i s 。s e c t i o n1g i v eu st h ei n t r o d u c t i o n o fn m fa n dt h ei n i t i a l i z a i t o no fn m fa n dl o o k sb a c kt h ef o r m e rw o r k so ft h i s a r e a i ns e c t i o n 2 ，w er e v i e wt h el a n c z o sb i d i a g o n a l i z a t i o np r o c e s st og e ta l o w - r a n ka p p r o x i m a t i o n i ns e c t i n 3 ，w ep r e s e n tas t r a t e g yt og e tn o n n e g a t i v e a p p r o x i m a t i o nm a t r i c e sw a n dhf r o mt h el a n c z o sb i d i a g o n a l i z a t i o np r o c e s s i ns e c t i o n 4 ，w eg i v es o m ee x p e r i m e n t st oc o m p a r eo u rm e t h o dw i t hc b o u t s i d i s a n de g a l l o p o u l o u s m e t h o da n dd e m o n s t r a t et h ea d v a n t a g e so fo u rm e t h o d s i ns e c t i o n5 ，w eg i v eac o n c l u s i o no fo u rt h e s i s k e yw o r d s ：l a n c z o sb i d i a g o n a l i z a t i o n ；n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ； s i n g u l a rv a l u ed e c o m p o s i t i o n ；l o w - r a n ka p p r o x i a m t i o n 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体己经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：王次幺盛 砷j 年多月 f 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦f - j t 学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：王炫益 1 _ 0 0 1 年历月f 日 第一章引言 1 第一章引言 著名的科学杂志n a t u r e 于1 9 9 9 年刊登了两位科学家l e e 和s e u n g 对 数学中非负矩阵研究的突出威屎该文提出了种新的矩阵分解思想一一非负矩 阵分解( n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ，n m f ) 算祛，即n m f 是在矩阵中 所有元素均为非负数约束条件之下的矩阵分解方法由于非负矩阵分解在现实生 活如图形处理，数据挖掘，数据采集，语音处理，生物医学工程和化学工程等方面 ( 在【3 】中有着更为详细的讨论) 有着广泛的应用，该论文的发表迅速引起了些 研究领域中的科学研究人员的重视：方面，科学研究中的很多大规模数据的分 析方法需要通过矩阵形式进行有效处理，而n m f 思想则为人类处理大规模数据 提供了种新的途径；另方面，n m f 分解算法相较于传统的些算法而言， 具有实现上的简便性、分解形式和分解结果上的可解释性，以及占用存储空间少 等诸多优点 在本文中，我们定义好一为所有m n 非负矩阵的集合非负矩阵分解 ( n m f ) 的问题可以表述为：对于给定的个矩阵a 必r 和k m i n ( m ，礼) ， 我们寻找w 哗 和日乏晕n ，满足 a 日 这就是说，我们需要寻找两个非负矩阵和日，使它们的内积在某种度量( 在 本文中，这种度量为f r o b e n i u 范数f ) 限制下能够近似于给定的矩阵a p a a t e r o 【1 1 ，p a a t e r o 和t a p p e r 【1 2 】和l e e 和s e u n g 8 】都对非负矩阵的 分解( n m f ) 做了讨论在【9 】中，l e e 和s e u n g 提出了两种迭代的非负矩阵 分解算法，由于对于初始的( 彬日) 是任意给定的，所以( 彬日) 中并不蕴涵着原 始的非负矩阵a 的信息，这两种算法很多时候都需要通过大量迭代才能够渐进收 敛虽然这两种算法都是单调收敛的【9 】，但是由于它们的收敛速度比较慢，甚至 于有些时候我们需要随机的选择好几个( 彬h ) 才能够收敛得比较好，所以寻找 蕴涵原来的矩阵a 信息的( 彬日) 就变得很有必要了可是直至今日，对于初始 第一章引言 2 的( 彬) 的讨论还比较少由于非负矩阵分解( n m f ) 问题是个有界最优 化问题，所以它的收敛速度很可能就比较慢( 彤日) 在【2 】中，c b o u t s i d i s a 和 e g a l l o p o u l o s 提出了一种基于奇异值分解( s v d ) 的初始化策略，在这种策 略下，由于( 彬日) 蕴涵了原来矩阵a 的些信息，所以和原来未经过初始化的 算法相比较，收敛速度得到了很大的提高这种初始化策略我们称为n n d s v d ， 它拥有以下1 衍特征：它可以和现存的所有的非负矩阵分解( n m f ) 算法相结 合；它的初始的( wh ) 包含了原来矩阵a 的一些奇异值信息，所以不是随机的 被选择的；它可以和其它的非负矩阵分解( n m f ) 算法拥有相同的收敛结果， 但是有比较陕的收敛速度 虽然n n d s v d 和其它未经过初始化的算法相比较有着优势，但是由于它需 要进行奇异值分解( s v d ) ，而奇异值分解( s v d ) 所花费的代价是非常的大 的，所以这就大大的降低了这种初始化策略的诱惑力 在本文中，我们提出了种新的初始化策略，这种策略是基于l a n c z o s 双对 角过程去寻找矩阵的个低秩近似，因此这种力砝所得到的初始的( 彬日) 同样 蕴涵了原来矩阵a 的一些信息，所以和原来未经过初始化的算法相比较，收敛速 度也可以得到了很大的提高而且同n n d s v d 相比较，我们并不需要对矩阵进 行奇异值分解( s v d ) ，所以这就大大降低了初始化的时间，提高了我们初始化 策略的吸引力我们的策略是通过l a n c z o s 双对角化先得到矩阵的个秩k 近 似，然后同【2 】的做港 样，在l a n c z o s 过程中得到每个秩1 矩阵的非负部分的 近似，最后得到a 的非负矩阵分解的初始化矩阵数值实验显示：同n n d s v d 相比较，我们的方法更加的有效 第二章i 舳c 墨双对角过程得至i i 短降缒彳丛近似 3 第二章l a n c z os 双对角过程得到矩阵的低秩近似 许多关于非负矩降铆酥算法的文章都有提到个好的初始化方法 1 】是非常 必要的，但是事实上很少有文章对于这部分内容有做进步的讨论对于绝大多 数的文章初始的( 彬日) 都是任意给定的，或者只是对于其中个因子做了初始 化( 例如) ，而另外个因子则是被随机的选择在本文中，我们给出了一种 对于( 彬日) 都做了初始化的方法因为非负矩阵分解在本质匕其实也是种在 某种限制下的低秩近似，所以我们的初始化方法也是基于种低秩的分解 在过去，因为几乎所有的非负矩阵低秩近似都是基于奇异值分解( s v d ) ； 所以对于个低秩近似问题， e c k 缸 t - y o u n g 定理是非常重要的 定理1 ( e c k a r t y o u n g 定理，见 7 ) 矩阵a r m 一有奇异值分解 ( s v d ) a = p q r ， = d i a g ( 0 1 ，砚，o - n ) r 仇， 此处仃120 2 0 是矩阵a 的奇异值 且矩阵p 黔，m 和 q r 叩是正交矩阵当1 r n 时，矩阵 a ，= p d i a g ( a 1 i 一，“，o ，o ) q t ( 2 ) 、- - 。_ 。、，i _ 一 是问题 m i n i t a b i 瞎i b r m n ，r a n k ( b ) r )( 3 ) 的全局最优解；而且它的相应的最4 、值为：件1 砖；如果听 a r + t ，那么 4 是唯一的( 证明省略) 从定理1 我们可以看出，如果矩阵a 的奇异值分解( s v d ) 存在，矩阵的 秩r 近似就可以很容易的求出来了但是当矩阵a 是个大矩阵的时候，那么 我们就要花费很大的代价去做矩阵的奇异值分解；特别的，当我们只是对于4 ( r m i n ( m ，礼) ) 感兴趣时，那么我们花了那么大的代价对a 做奇异值分解 ( s v d ) 就很有可能只是种浪费了因此，寻找计算4 ( r m i n ( m ，n ) ) 的 g ：- 章l a n c z o s 双对角过程得到矩哇蝗堡叁近似 4 种低代价的方法就变得很有必要和很有意义了在下面，我们介绍一种基于所 谓的l a n c z o sx y x 寸角过程的低秩近似方法；通过快速的l a n c z 0 8 双对角过程， 即使不计算矩阵的奇异值分解( s 、，d ) ，我们也可以得到矩阵a 的个比绽好的 低秩近似 和 1 6 样，我们先开始介绍l a n c z o s 双对角化过程 对于给定的个初始向量b ，i = 1 ，2 ，k ，我们计算 历u 1 = b ， q 1 ”l = a t u l , ( 4 ) 风+ l 锃件1 = a 魄一瓴t i ， 啦+ 1 + 1 = a t t 正件1 一屈+ 1 此处，啦和屈应该满足限制条件1 1 2 = 1 1 2 = 1 ，所以q 和展有可 能是正数也有可能是负数但是，因为我们下节的应用，我们在i 比对和屈 的符号做了限制，我们规定和屈都是正数 ( 4 ) 的矩阵形式可以写成 u k + l ( 儡e 1 ) = b ， a v k = u k + i b k + 1 ( ：，1 ：尼) ， a r 巩= k + 1 b k t + 1 ， 此处b 七+ 1 r ( 七+ 1 ) ，( 知十1 ) 是个下双对角矩阵， b k + i = o e l 恳q 2 仇+ 1a 七+ 1 u k + 1 = 私l ，u 2 ，牡玉+ l 】，k + l = f 移l ，忱，魄+ 1 】，而召毒+ 1 ( ：，1 ：七) 是b k + i 去掉最后列所形成的矩阵 如果我们想要得到矩阵a 的少数l 个主要的奇异三元组，那么我们就需要对 矩阵鼠做奇异值分解( s v d ) 因此，我们就把反的奇异值当作矩阵a 的 第二章l a n c z o s 双对角过程得到矩阵的低秩近似 5 近似奇异值；把矩阵取的奇异向量和左右l a n c z o s 向量巩和k 相结合 当作矩阵a 的近似奇异向量 5 但是，在本文中我们感兴趣的是矩阵a 的低秩近似，所以我们并不需要对矩 阵b k 做奇异值分解( s v d ) 所以我f 彳艮自然的选择 以= 巩风昭( 6 ) 当作是矩阵a 个低秩近泡1 很显然，如果q i 0 ，i = 1 ，2 ，七，那么 r a n k ( j k ) = 七a 正如( 2 ) 定义， 1 6 表n t x 寸于任意七 歹，i i a 一以临 近似于i i a a 临特别的， 1 6 给出了兀价惯阿说明当七只是稍稍大于 j 时，i l a 一以临已经非常的接近于i l a a 幅了 通过 1 3 】的误差分析，( 5 ) 在有限的机器精度内可以写成形式 以+ ，( 岛e 。) = b ， a 哦= 巩+ 1 b k + 1 ( ：，1 ：七) + f k ， ( 7 ) 舻巩+ l = 亿+ 1 台玉1 + g 七+ l ， 此处i l 忍i | = o ( i i a i i f e m ) 和l l g 七十t l | _ o ( 1 | a 怯m ) 有机器精度e m ，面 只= 【 ，如，五】，g i = g l ，9 2 ，吼】 为了和( 5 ) 有所区分，我们增加了”1 在 1 6 中，为了保持l a n c z o s 过程和重正交过程向量的正交性，作者对 于停机准则( u k = l l a 一以怯st o l ，t o l 是个匕界) 做了进步的讨论但 是，在本文中我们对于这个并不做进步的研究 算法2 1l a n c z o s 双对角过程的m a t l a b 代码 输入：矩阵a 霹一，正向量b ，整数0 0 ；因为矩阵a 是个非负矩阵，所以我f 丁彳艮容易推出 u 1 和u 1 是非负的但是这并不能保证( 6 ) ( l a n c z o s 过程) 中的j k 也是非 负的我们目的是要的到矩阵a 的个低秩非负近似，所以我们必须对以做 些修正，同时能够对( 彬日) 做初始化；因此，我f f 了把五写成如下的形式： 以= 巩风昭= 【2 ，川七1 = 【i 1 ，仳k 】 + t 1 1 ，仳七】 口l q 2 0 尾 0 = 笔。q ；g + 旨侥+ 。d ； o t l 岛 口2 q k o 口七 仇q 七 v l u 2 ： 仇 此处g = u i 印，d i = 仳件l 谚；因为i ，u i 都是向量，所以g 和d 都是 秩1 的矩阵从以的展开式，我们可以和c b o u t s i d i s 和e g a l l o p o u l o u s 在 2 中做的样，对( 彤日) 做初始化 注意g = g + 一g 一，马= b + 一d j 一，我们定义 乃( g + ) ，叻( g + ) ，码( g + ) ) 和 肌( d j + ) ，x l ( d j + ) ，u l ( 岛+ ) ) 是g + 和岛+ 按照不增的秩序排列的奇异三 元组；相应的，我们规定i = 2 ，七；歹= 1 ，七一1 和l = 1 ，2 我们可 以得到 以 = 叁1 0 t i t 正i l t i + - k - 1 1 成+ l u i + lf = 坠1 q i g + e ，k - , 3 + 1d i = q 1c a + 冬2 q i g + 一垒2 0 f i c i 一十f k ：- 1 1 屈+ ld i + 一茸8 i + 1d i 一 = q 1 q + 冬2 口1 ( g + m 1 ( g 十) n l ( g + ) r + k ：- l i 屈+ 1 p l ( d i + ) z l ( d t + ) 1 ( d f + ) r + e 第三章初始化( 彬日) 1 0 此处e 被定义为 e 垒2 0 t i c r 2 ( g + ) m 2 ( g + ) 几2 ( g + ) t + e 譬 屈+ l p 2 ( d 件) z 2 ( d 件) v 2 ( d i + ) t 一( 叁2 啦g 一+ 旨屈+ l d i 一) 因此，我们可以初始化( 彬日) 使 日 = a 1 g + 笔2 q 盯l ( g + ) m l ( c i + ) n l ( g i + ) r 1 m u 芝 。k 一- 1 ，o + 1 p 1 ( d i + ) z 1 ( d i + ) y l ( d i + ) t = j k e ( 1 0 ) 上述的过程构成了我们算法的理论依据；基于这些，我们可以推导出我们的算 算法3 1 初始化( 彬h ) 的m a t l a b 代码 输入：矩阵a r 7 ”，正向量b ，整数0 = t e r m n l ) ( ：，i ) = ( ：，i ) + b ( i ，i 一1 ) 幸u u p n u u p ； h ( i ，：) = 日( i ，：) 4 - v v p l 7 n v v p l ； e l s e ( ：，i ) = ( ：，i ) + b ( i ，i 一1 ) , u u n n u u n ；h ( i ，：) = i - t o ，：) + v v n l 7 n v v n l e n d e n d 在上面的算法中，函数p o s 和n e g 的表示如下：【a p 】= p o s ( a ) 为a p = ( a = o ) 木a ；而【a 竹】= n e g ( a ) 为a n = ( a o ) 木( 一a ) 我们定义： e = a 一以= a 一( 日+ e ) ，a w 日= e e = r 我们可以设定u 七= i i a 一以怯 t o l ( t o l 为个匕界) ，以e 述的推理 中，我们可以对初始化的( 彬h ) 中得到个误差界；我们规定残量为r = a wh 定义：给定个矩阵a ”，由( 1 0 ) 中得到的初识化( w 日) ，r = a w 日的f r o b e n i u s 范数的个匕界可以定义为 i i e i i f i i r i i fsl i e i i f + l i e i i f t o l + i i e i i f 因为 a j 和 屈) 并不是按照不增的秩序排列的，所以我们的得到的界可 能并不是非常的好；因此，我们可以给定个e 代替e ，因此亩= a 一以= a 一( 彬膏+ 啻) ，而壳= 亩一啻所以我f 门可 以改进我们的误差界为袁： i i d i i f i i s 圣l l f i i e i i f + i l 啻l l f t o l + i l i ? l l f 虽然我们所给定的误差界是宽松的，但是它也表明了残量是有上界存在的而 且，对于我们而言，我们感兴趣的是，在实际的应用中，经过我们初始化以后， 卜 d +臃 h l 一 一g q 。御 一 = g 第三章初始化( w , u ) 得到的( 彬h ) 与现存的非负矩阵分解( n 阿) 的算法结合后，我们所需要的 迭代次数大大的减少了；如果没有经过初始化，所需的迭代次数要更多 我们策略的两个最主要的计算步骤是： ( i ) 运行k 步的l a n c z o s 双对角过程，从( 6 ) 中得到矩阵以； ( i i ) 从( 1 0 ) e e 禾4 n 近似的非负矩阵( w 日) 由引理2 可以知道，我们并不需要对矩阵做奇异值分解( s v l ) ) 就可以得 到【g 十) 和 d 件) 从 c + ) 的性质我们可以知道，和第步相比较，第二 步所需要花费的代价是很低的；而目对于个稠密的非负矩阵a ，我们所需花费 的总的代价为o ( k m n ) 1 2 第四章数值实验 1 3 第四章数值实验 从算法3 1 中，我们可以看出，同【2 】中的n n d s v d 一样，我们的算 法可以和现存的所有的非负矩阵分解( n m f ) 相结合但是，和n n d s v d 所不同的是，由于初始向量b 的选择并不唯一，所以我们的初始策略还带有一点 随机性；因此当我们在l a n c z o s 过程中选择不同的b ) 0 时，我们所得到的 初始的( wh ) 也是不一样的在接下来的实验中，诧们设定初始的向量b = ( 1 ，1 ，1 ) 7 ；我们所有的实验都是在g e n n u i n ei r t t e l ( r ) c p u l8 6 g h z ，1 5e m s 内存盼计算机上进行 我们所用的是m a t l a b7 0 版本 ( 7 f i g1d a t ao f m o o n i m a g e 倒1 我们考虑f i g 1 中的月亮图像，这是个5 3 7 3 5 8 的矩阵f i g2 ， f i g3 分别描述了l a n c z o s 初始化算法和1 n n d s v d 初始化算法的结果在 图像中，同佯的显示了参数( 秩) k 的选择对我们数值结果的影响，所以对参数 ( 秩) k 的选择在估计我们的结果时同样应该考虑进去 墨里主塾堕差壁 1 4 f 日2pr o 口r e 洲a p p r o x i m a u o a g e su $ l n 0 ：l 日n o z o s k = 1 0122 0 2 5 f i 93p r o g r o s sor a p pr o x i m s l i o n 口n m o d n l m a g 5 l “口：n n d s v d ：k = 1 口，1 22 02 5 t a b l e1 描述了两种初始化策略算法在初始阶段的运行时间从表中，我们 可以 e 清楚的看到，同n n d s v d 的初始化策略相比较，我们的l 衄c z o s 初 始化策略要陕的多 k = 1 0k = 1 2k - - 2 0k = 2 5 n n d s v d t a b l e1 初始阶段运行时问( 单位；秒) 的比较 在【9 】中，l e e 和s e u n g 提出了两种选代形式的非负矩阵分解( n m f ) 的算法，第一种我们称之为mm 我们把l a n c z c s 初始化和n n d s v d 初 始化方法同m m 算法相结合；把初始化后所得到的( w ) 应用于m m ， 并没定遮代次数为1 0 0 次 t a b l e2 比较了l a n c z o s m m 和n n d s v d m m 的目标函数值( 0 a 一+ h 怙) 第四章数值实验 k - - 1 0k - 1 2k - - 2 0 k - - - - 2 5 l a n c z o sm m 5 9 5 95 2 7 34 3 6 14 0 8 9 n n d s v dm m6 1 2 o 5 6 6 44 6 5 44 4 9 5 t a b l e2 目标函数值的比较 1 5 接下来的四幅图描述了目标函数值和迭代次数的关系，相应的参数( 秩) 七= 1 0 ，1 2 ，2 0 ，2 m h 一k 1 2 s一嚣三，joi暑 co口#2嚣万a 暑一_口c，-2五享 幕四章数值实验 1 6 从t a b l e2 和图像我们可以观察到，虽然l a n c z o s 初始化所得到的目标 函数值比n n d s v d 韧始化得到的目标函数值大，但是l a n c z o sm m 和 n n d s v dmm 相比较却有更快的收敛速度，而且在迭代1 0 0 次蚪后，l m t c - z 蹦mm 的目标函数值比n n d s v dm m 更小 倒2 在【1 0 】中，l i n 提出了一种投影梯度法( a l t e r n a t i n gn o n - a e g a t i v el e a s ts q u a r e su s i n gp r o j e c t e dg r a d i e n t s ) 现在我们把这种 方法同l a n c z o s 初始化和n n d s v d 初始化相结合，相应的，我们把得到的 这两种非负矩阵算法分别叫做l a n c z o s p g 算法和n n d s v d p g 算法我 们考虑幅花的图像( 2 2 1 4 4 0 ) ( f i g4 ) ，并将它用这两种算法来处理 这里我们取参数( 秩) = 1 0 1 5 ，2 0 ，2 5 ，并得到处理后的图像( f i g5 ，f i g6 ) 因为两种算法算法收敛时，他们的迭代次数不同，所以我们在t a b l e3 将它 们的运行时间( 单位：秒) 和目标函数值表示出来 墨堡芏墼些塞墅 1 7 k = 1 0k = 1 6 e l a p s et i m eo b j e c t i v ev a l u ee l a p s et i m eo b j e c t i v ev a l u e l a n c z o s p g1 1 5 7 0 n n d s v d p g1 4 8 47 1 0 3 1 3 0 k = 2 0k = 2 5 e l a p s et i m eo b j e c t i v ev a l u ee l a p s et i m ed b e c t i v ev a l u e l a l l c z o s p g2 4 0 6 01 2 9 8 n n d s v d p g t a b l e3 运行时间和目标函数值的比较 黜罅譬搿霹“”“”“”“”5 。” ：ig ，f i l p 5 r 0 2 9 0 r ，嚣“8 9 ”“”8 “”“”6 从t a b l e3 我们可以看出，当参数( 秩) 越小时，l a n c z o s p g 同 n n d s v d p g 相比较，虽然目标函数值稍大了一点，但是收敛的速度却大大的 加快了 例3 我们在此处所应用的算法同例2 一样，矩阵4 一d ( 1 0 0 0 ) 在 t a b l e4 中我们比较了两种算法收敛时的运行时间( 单位秒) 和目标函数值， 第四章数值实验 并取参数( 秩) 七= 1 0 ，1 5 ，2 0 ，2 5 1 8 k = 1 0k - - 1 5 e l a p s et i m eo b j e c t i v ev a l u ee l a p s et i m eo b j e c t i v ev a l u e l a l i c z o s pg9 0 7 8 02 8 4 5 8 7 4 0 2 8 2 1 n n d s v d pg1 4 5 6 4 1 02 8 3 51 0 1 7 6 6 02 8 0 9 k - - - - 2 0k - - - - 2 5 e l a p s et i m eo b j e c t i v ev a l u ee l a p s et i m eo b j e c t i v ev a l u e l a n c z o s pg7 0 9 4 02 8 0 24 2 6 5 02 8 2 3 n n d s v d p g1 1 2 7 6 6 02 7 81 0 6 7 4 1 02 7 6 t a b l e4 运行时问和目标函数值的比较 从t a b l e4 中，我们可以看出，虽然n n d s v d p g 的目标函数值比l a n c - z o s pg 精确点点，但是l a n c z o s pg 的运行速度却比n n d s v d pg 要决 得多 第五章结论 第五章结论 1 9 通过l a n c z o s 双对角过程，我们可以推导出种新的非负矩阵的初始化方 法虽然这种初始化方法带有一点点的随意性，但是这种算法可以和现存的n m f 算法相结合尽管这种算法在初始化阶段得到的目标函数值比【2 】2 中的稍大，但 是在和原来的n m f 结合后却可以收敛的更陕而实验也表明了和现存的非负 矩阵分解算法相结合，我们的方法更加的有效 参考文献 【1 】m w b e r r y , m b r o w n e ，a n l a n g v i l e ，v p p a u c a ，r j p l e m - m o i l s ，al g o r i t h m sa n da p p l i c a t i o n sf o ra p p r o z i m a t i o nn o n n e g a t i v e m a t r i xf a c t o r i z a t i o n ，c o m p u t s t a t d a t aa n a l 5 2 ( 1 ) ( 2 0 0 7 ) 1 1 5 1 7 3 【2 】c b o u t s i d i s ，e g a l l o p o u l o u s ，s v db a s e di n i t i a l i z a t i o n ：ah e a d s t a r to fn o n n e g a t i v em a t r i xf a c t o r i z a t i o n p a t t e r nr e c o g n i t i o n ， 4 1 ( 2 0 0 8 ) ，1 3 5 0 - 1 3 6 2 3 】3a c i c h o c k i ，r z d u n e k ，n m f l a bm a t l a bt o o l b o xf o r n o n - n e g a t i v em a t r i xf a c t o r i z a t i o n u r l ：w w w b s p b r a i n r i k e n j p i c a l a b n m f l a b h t m l 【4 1j c o h e n ，u r o t h b l u m ，n o n n e g a t i v er a n k s ，d e c o m p o s i t i o n ，a n d f a c t o r i z a t i o n so fn o n n e g a t i v em a t r i c e s l i n e a ra l g e r b r aa p p l 1 9 0 ( 1 9 9 3 ) 1 4 9 - 1 6 8 【5 】5j c u l l u m ，r a w i l l o u g h b y , a n dm l a k e ，al a n c z o sa l g o r