求解非负矩阵分解的有效集BB梯度算法

张 璐，魏 潇

(西安电子科技大学数学与统计学院，陕西西安 710126)

1999 年，D.D.Lee 和 H.S.Seung［1］在其发表的论文中首次提出了非负矩阵分解(NMF)的概念，并设计了算法来求解该问题。十几年来，非负矩阵分解(NMF)的研究取得了长足进展，各种NMF算法被相继提出，且其己被成功应用到图像处理与模式识别［2］、数据挖掘［3－4］、和生物医学工程［5］等多个领域。

非负矩阵分解就是在给定一个非负矩阵V∈Rm×n的前提下，寻找一个分解，使得

一般地，问题(1)可转化为如下的优化问题

其中，W，H≥0表示W和H中的元素都是非负的，表示矩阵的F—范数。

现在最常用的求解方法之一是利用交替最小二乘算法(ANLS)，将上述问题转化为下面的两个子问题进行求解，即迭代下面的过程，直到满足停止条件

由于式(3)和式(4)对称，所以主要研究问题(3)。为描述简单，文中将式(3)改写为

其中，V和W是常数矩阵。H是式(5)的稳定点，当且仅当

其中，▽f(H)=WT(WH－V)。以下主要讨论式(5)的求解问题。

1 算法步骤

设有效域Ω={H∈Rr×nH≥0}，H是子问题(5)的一个稳定点。下面构造3个互不相交的有效集

其中，I={11，12，…，1n，21，22，…，2n，…，rn}。

为了保证迭代点的可行性，可定义如下搜索方向

若令Hk+1=Hk+Dk，可发现不能保证{Hk}的收敛性，所以提出一种基于非单调线搜索的全局技术［6］，即需找到步长αk满足传统最简单的非单调技术是取其中m(k)在每次迭代时均需要计算，在文献［7］中提到这种非单调搜索技术有一些缺点:首先，由于Ck通过求解符合条件的f的最大值，这样可能会将迭代过程中产生的较好的函数值舍弃掉;其次，最后的数值结果对m(k)的依赖性比较大。为克服上述缺点，文献［9］中使用权平均函数［8］来代替的最大值函数［7］

其中，C0=f(H0)。文献［5］中已证明了 f(Hk)≤Ck，且{Ck}是一个递减序列，即Ck+1≤Ck。算法如下

算法1 (s.0)给定初始点H0≥0，整数M≥1，容许参数ε＞0，参数λmax＞λmin＞0，常数满足γ∈(0，1)，τ∈(0，1］，C0=f(H0)，m(0)=0，给定初始参数 λ0∈［λmin，λmax］，令 k=0。

步骤3 由式(10)计算搜索方向Dk。

步骤4 非单调搜索技术确定步长αk。

其中

令 Hk+1=Hk+ αkDk。5

令 λk－1=min{λmax，max{λmin，λ'A}}。

步骤7 令k=k+1，转步骤1

2 收敛性分析

在这一部分中，将分析上面所得到算法1的全局收敛性。

引理1［9］设上述算法产生的迭代序列为{Hk}，则{Hk}是有界的。

引理2 设上述算法生成Hk和Dk，则Dk=0当且仅当Hk是问题(5)的一个稳定点。

引理3 设Hk∈Ω，Dk是由上述算法产生的，则＜▽f(Hk)，Dk＞ ＜0。

当 ij∈Fk时，Dkij= － λk▽f(Hk)，则有〈▽f(Hk)，Dk〉=〈▽f(Hk)，－λk▽f(Hk)〉= －▽f(Hk)＜0

综上所述，该引理成立。

引理 4［9］如果 Hk→ 且 Dk→0，则是问题(5)的一个稳定点。

由以上的引理，结合文献［6］类似的证明，我们可以得到以下定理。

定理1［10］设算法产生序列{Hk}，则{Hk}的每个极限点都是问题(5)的极限点。

3 仿真实验

研究算法的实际效果，所使用的算法是在Matlab 7.10环境下运行。为测试上述算法的实际效果，使其与投影梯度算法(Projected Gradient Method，PG)［11］进行比较，初始点{W0，H0}由代码 W0=abs(randn(m，r));H0=abs(randn(r，n))产生。其中，m和n分别表示矩阵V的行数和列数。首先讨论在本算法中每个子问题的终止条件。根据文献［12］的思想，使用如下终止条件。用于解决子问题的迭代过程中所产生的返回矩阵Hk+1和Wk+1应该分别满足条件和，这里，ε是容许参数。如果对于问题(3)，该算法没有任何迭代，通过=0.1来降低停止参数。对于子问题(4)，运用同样的方法来降低的值。

实验中，该算法的常数的值是M=5，τ=0.3，λ0=1，γ =0.1，λmin=10－6，λmax=1，ε =10－6。误差值计算为。为说明该算法的有效性，对于每个问题，列出了在算法终止时，算法的迭代次数，运行时间，函数值和误差。具体数值结果如表1所示。

表1 数值结果

从ORL人脸数据库里选取5幅像素为112×92的人脸图像，分别记为A，B，C，D和E，将每一幅图像的数据矩阵记为V，两个算法采用相同的初始点，其中r分别取为 5，10，15，20 和 40。初始点(W0'，H0')由代码W0'=10×abs(randn(m，r));H0'=10×abs(randn(r，n))产生。运用上述的两种算法，分别得到对应的重构图像。

图1的5幅图分别表示 A，B，C，D和E图像的迭代过程中迭代次数和相对误差值的关系，图中PSG表示新算法。可看到，两种算法在相对误差大致相同的情况下，本文提出的新算法比PG算法的迭代次数少。通过控制精度值，来对比两种算法在人脸识别中的实际效果得到图2所示。图3中的5幅图分别表示在5组人脸识别的图像中选取精度与运行时间的关系，由图像容易看出:随着精度的降低，运行时间是增加的。当精度选取为10－6时，得到的效果比较明显;当R取10时，该算法有些失效，这为以后的继续研究提供了方向，但总体情况下，当精度一样时，该算法还是比PG算法有效。如图1分别对应上述5种情况。

图1 NMF算法的效果图

图2 人脸识别的效果

图3 人脸识别中精度与运行时间的关系

［1］Facchinei F，Fischer A，Kanzow C.On the accurate identification of active constraints［J］.SIAM Journal on Optimization，1998，9(1):14 －32.

［2］Ziehe A，Laskov P，Pawelzik K，et al.Non － negative sparse coding for general blind source separation［C］.Vancourver:Advances in Neural Information Processing Systems，2003.

［3］Xu Wei，Liu Xin，Gong Yihong.Document clustering based on non － negativematrix factorization［C］.New York:Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2003.

［4］Shahnaz F，Berry M，Pauca V，et al.Document clustering using nonnegativematrix factorization ［J］.Information Processing ＆ Management，2006，42(2):373 －386.

［5］Brunet J，Tamayo P，Golub T，et al.Metagenes and molecular pattern discovery using matrix factorization［J］.Proceedings of the National Academy of Sciences of the United States of America，2004，101(12):4164 －4169.

［6］Philippe L T.An assessment of nonmonotone linesearch techniques for unconstrained optimization［J］.SIAM Journal on Scientific Computing，1996，17(3):725 －739.

［7］Zhang Hongchao，William W Hager.A nonmonotone line search technique and its application to unconstrained optimization［J］.SIAM Journal on Optimization，2004，14(4):1043－1056.

［8］Irene K，Stefanos Z，Ioannis P.A novel discriminant non －negative matrix factorization algorithm with applications to facial imagecharacterization problems［J］.IEEE Transactions on Information Forensics and Security，2007，2(3):588－595.

［9］Liu Hongwei，Li Xiangli.Modified subspace barzilai－ borwein gradient method for non－negative matrix factorization［J］.Computational Optimization and Applications，2012，55(1):173－196.

［10］Xiao Yunhai，Hu Qingjie.Subspace Barzilai－ Borwein gradient method for large－scale bound constrained optimization［J］.Applied Mathematics and Optimization，2008，58(2):275－290.

［11］肖霄.基于非负矩阵分解的人脸识别研究［D］.大连:大连理工大学，2008.

［12］Liu Chihjen.Projected gradient methods for nonnegative matrix factorization ［J］.Neural Computation，2007，19(10):2756－2779.