基于SVD确定NMF初始化矩阵维数

陈剑军++刘智秉

摘要：根据奇异值分解和奇异值的属性，提出了确定非负矩阵分解中初始矩阵维数的方法：以矩阵奇异值的平方计算各自的贡献率，以贡献率之和接近给定阈值来确定所需奇异值的个数，并以之为初始矩阵的维数。避免了人为尝试维数的缺陷。给出了相应的证明并解释了方法的合理性。比较了使用奇异值确定初始矩阵维数的不同方法，证明且验证了在相同贡献率的情况下所需初始矩阵维数的大小关系。

关键词：非负矩阵分解；初始化矩阵维数；奇异值分解；贡献率

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）24-0116-03

The Dimension of NMF Initialization Matrix Based on SVD

CHEN Jian-jun 1， LIU Zhi-bing 2

（1.Guangdong University of Science and Technology， Dongguan 523083， China；2. College of Science， Jiujiang University， Jiujiang 332000， China）

Abstract： Based on the properties of singular value decomposition and singular value， the method of determining the initial matrix dimension of non negative matrix factorization is proposed. The contribution rate of the matrix singular value is calculated. To avoid the defect of the dimension of human attempt. The rationality of the method is given. A comparison is made on the different methods of determining the initial matrix dimension using the singular values， and it is proved that the size of the initial matrix dimension is required for the same contribution rate.

Key words： non negative matrix factorization； initialization matrix dimension； singular value decomposition； contribuion rate

NMF算法是Lee D D 和Seung H S 在《Nature》提出的矩阵分解新算法[1]。该算法通过简单迭代将非负矩阵分解为两个低阶非负矩阵之积，从而使矩阵分解具有可解释的实际意义。因此，NMF算法迅速引起了各科研领域的重视并将其广泛应用于图像分析、数据挖掘、语音处理、机器人控制、生物医学工程和化学工程等诸多领域[2-7]，[12-13]。

算法概要如下[1]（其收敛性在[1]中已证）：

给定非负矩阵[V∈Rm×n+]，随机产生随机矩阵[W1∈Rm×r+，H1∈Rr×n+]；[r]是根据需要选择的正整数（本文称之为初始矩阵的维数）。

[Hk+1=（Hk）.（W'kV）.（W'kWkHk）.]，[Wk+1=（Wk）.（VH'k+1）.（WkHk+1H'k+1）.]。 （注：带括号的乘、除为对应元素相乘、除。）

其中：[k=1，2，...，K]。[K]为迭代次数，据目标函数或需要来确定。目标函数之一为：[V-WH22]。

作为新方法，NMF算法虽然克服了传统的矩阵分解方法的很多缺陷，但自身也存在一些缺点，如：分解结果不唯一导致全局最小点很难找到，初始化状态不确定，等等[6-9]。NMF算法的合理初始化问题是目前国、内外研究NMF算法改进的热点问题之一[4]，[6]，[8-9]。初始化问题可分为两个方面：如何选择初始化矩阵、如何确定初始矩阵的维数，后者直接关系到存储、计算成本。然而，关注前者的研究较多[3-4]，[8]，对于后者，目前采用的方法是以不同的维数进行尝试，经过计算、比较结果之后再选择合适的维数，尚无直接确定该维数的合理方法或算法[6-7]，[9]，[14]。

本文提出NMF算法中确定初始矩阵维数的方法：用奇异值的平方计算各奇异值的平方的贡献率，当贡献率之和接近给定的阈值时，取所需要的奇异值的个数为初始矩阵的维数。采用的方法与文献[10]不同且解释了方法的合理性、证明并验证了两种方法在相同贡献率的情况下所得初始矩阵维数大小关系。

1 NMF中初始矩阵维数的确定

由文献[11]不难推导出如下的结论：

引理：给定非负矩阵[V∈Rm×n+]，记其奇异值分解如下：[V=PΣ1000QT]。式中：[Σ1=diag（σ1，σ2，...，σl）]，

[P∈Rm×m]和[Q∈Rn×n]为正交矩阵。[σ1≥σ2≥...≥σl>0]为非零奇异值，[l=rank（V）≤min（m，n）]。记[V=（v（i，j））]，设其元素为[m]信道的、已经过零均值化处理的观测数据序列；[i=1，2，...，m；][j=1，2，...，n]。则：第[k]信道的信号功率[pk=1nσ2k]，[k=1，2，...，m]。

可见，此时奇异值的平方与能量相对应。

为直观起见，下文的非负矩阵均以图像为例。

定义1：设图像矩阵[V∈Rm×n+]，定义原始图像[V]与重构图像[Vk]的相对距离误差为[V-VkFVF]。

定义2：设图像矩阵[V∈Rm×n+]的奇异值分解如引理所记，定义[σ2i]的贡献率为：[εi=σi2/i=1lσj2]，[i=1，2，...，l]。

可见：若[j=1kεj=j=1kσj2/j=1lσj2]接近于1，则该图像的主要信息包含在矩阵[Vk=j=1kσjpjqTj]中，而矩阵[j=k+1lσjpjqTj]表示次要信息。

定理1：设图像矩阵[V∈Rm×n+]的奇异值分解如引理所记，给定重构图像与原始图像的相对误差阈值[δ（0<δ<1）]。取最小的正整数[k0]，使得[δ≥1-j=1k0εj]。取[k0]为初始矩阵的维数，构作矩阵：[Vk0=j=1k0σjpjqTj]，则：[V-Vk0FVF≤δ]。

证明：[V-Vk0FVF=j=k0+1lσ2jj=1lσ2j=1-j=1k0εj≤δ]。

根据该定理，给出确定初始矩阵维数算法如下：

1）给定重构图像与原始图像的相对误差阈值[δ（0<δ<1）]；

2）计算贡献率：[εi=σi2/i=1lσj2]，[i=1，2，...，l]；

3）计算累计贡献率：[j=1kεj，k=1，2，...，l]；

4）取[k0]，使得：[j=1k0εj≥1-δ2]且[j=1k0-1εj<1-δ2]。

因此，重构图像[Vk0=j=1k0σjpjqTj]与原图像的相对误差不超过预定的阈值[δ]。

说明：文献[10]提出：以[j=1kε′j=j=1kσjj=1lσj]来确定初始矩阵的维数（其中[ε′i=σi/i=1lσj]）。这与引理所表明的情况未能吻合。根据引理，采用奇异值平方计算贡献率更为合理。

两种方法求解初始矩阵维数的比较如下：

定理2：设图像矩阵[V∈Rm×n+]的奇异值分解如引理所记。设[1≤p≤l]为整数。

记：[σ21+...+σ2pσ21+...+σ2l=ρ1]，[σ1+...+σpσ1+...+σl=ρ2]，则：[ρ1≥ρ2]。

证明：[ρ1-ρ2=（σ21+...+σ2p）（σ1+...+σl）（σ21+...+σ2l）（σ1+...+σl）—（σ21+...+σ2l）（σ1+...+σp）（σ21+...+σ2l）（σ1+...+σl）]

[=σ1（σ21+...+σ2p）+...+σl（σ21+...+σ2p）（σ21+...+σ2l）（σ1+...+σl）-σ1（σ21+...+σ2l）+...+σp（σ21+...+σ2l）（σ21+...+σ2l）（σ1+...+σl）=σp+1（σ21+...+σ2p）+...σl（σ21+...+σ2p）（σ21+...+σ2l）（σ1+...+σl）-σ1（σ2p+1+...+σ2l）+...+σp（σ2p+1+...+σ2l）（σ21+...+σ2l）（σ1+...+σl）]

[=（σ21σp+1-σ1σ2p+1）+...+（σ2pσp+1-σpσ2p+1）（σ21+...+σ2l）（σ1+...+σl）+（σ21σp+2-σ1σ2p+2）+...+（σ2pσp+2-σpσ2p+2）（σ21+...+σ2l）（σ1+...+σl）+]

[+...+（σ21σl-σ1σ2l）+...+（σ2pσl-σpσ2l）（σ21+...+σ2l）（σ1+...+σl）≥0]。

可见：在初始矩阵的维数相同的情况下[ρ1≥ρ2]，因此，若在相同累计贡献率的情况下求初始矩阵的维数，则：采用奇异值的平方得到的维数不超过采用奇异值计算得到的维数。

2 图像实验

实验条件：Windows7、Matlab7.0，CPU：1.8G，内存4.0G。图像分辨率为：[512×512]。

贡献率相同情况下，计算初始矩阵维数的结果如表1。

按照表1中维数[k0]，采用前段[k0]个奇异值重构图像[Vk0=j=1k0σjpjqTj]。图1对应于奇异值平方计算贡献率，图2对应于奇异值计算贡献率，均按照表1中的累计贡献率由低到高的顺序排列。

可以看出：用不同的方法计算贡献率，即使贡献率相同，对应的图像有较大的差异：这是因为贡献率的计算方法不同。本文的方法一般取累计贡献率在0.995乃至以上方可取得较好重构效果。

3 结束语

NMF中初始矩阵维数的选取关系到矩阵的计算、存储成本。提出以奇异值平方来计算累计贡献率以确定NMF中初始矩阵的维数。弥补了目前反复尝试以确定初始矩阵维数的缺陷。引理及定理1保证了方法的合理性，定理2及表格1比较了两种不同计算方法的效果。

NMF中初始矩阵维数与初始矩阵、迭代次数的关系有待进一步探索。

参考文献：

[1] Lee D D，Seung H S. Learning the parts of objects by non-negative matrix factorization[J].Nature，1999，401（6755）：788- 791.

[2] 程明松，刘勺连.一种实用快速非负矩阵分解算法[J].大连理工大学学报，2013，53（1）：151-156.

[3] 高洪涛.非负矩阵因子分解算法理论和应用研究[D].上海：同济大学，2005：8-18.

[4] 王炫盛，陈震，卢琳璋.Lanczos双对角化：一种快速的非负矩阵初始化方法[J].厦门大学学报：自然科学版，2012，51（2）：149-152.

[5] 徐森，卢志茂.结合K均值和非负矩阵分解集成文本聚类算法[J].吉林大学学报：工学版，2011， 41（4）： 149-152.

[6] 李乐，章毓晋.非负矩阵分解算法综述[J].电子学报，2008，36（4）：738-743.

[7] 徐泰燕，郝玉龙.非负矩阵分解及其应用现状分析[J].武汉工业学院学报，2010，29（1）：109-114.

[8] Wild S， Curry J，Dougherty A.Improving non-negative matrix factorization through structured initialization [J].Pattern Recognition， 2004，37（11）： 2217-2232.

[9] Boutsidis C， Gallopoulos E.SVD based initialization：A head start for non-negative matrix factorization[J].Pattern Recognition， 2008，41（4）：1350-1362.

[10] Qiao H. New SVD based initialization strategy for Non-negative Matrix Factorization. arXiv：1410.2786v1，[cs.LG]10 Oct.2014.

[11] 张贤达.矩阵分析与应用[M].北京：清华大学出版社，2004：344-354，510-512.

[12] 林庆，李佳，雍建平，等.一种改进的基于NMF的人脸识别方法[J].计算机科学，2012，39（5）：243-245.

[13] 刘如京，王玲.一种NMF和SVD相结合的鲁棒水印算法[J].计算机科学，2011，38（2）：271-273.

[14] Amy N. Langville， Carl D. Meyer， Russell Albright，et al. Algorithms，Initializations，and Convergence for the Non-negative Matrix Factorization. arXiv：1407.7299v1 [cs.NA] 28 Jul 2014.