基于NNDSVD初始化及交错迭代的非负矩阵快速分解
宋艳枝 徐敏
摘要：本文是基于凸规划的经典交错迭代法来解决非凸非负矩阵分解
问题（NMF），其精髓在于把有约束优化问题转化为无约束极小化问题，结合交错迭代法将非凸问题转化为凸规划。与传统方法用随机值初始化不同，我们利用SVD分解数据集，将分解矩阵中的负元素改为零以后作为NMF的初始化矩阵，即非负双重奇异值分解初始化（NNDSVD）。实验表明，在有限的迭代步数内，这样选取的初始值比随机初始值收敛的更快。
关键词：非负矩阵分解，交错迭代法，NNDSVD，KKT点。
引言：非负矩阵分解（Nonnegative Matrix Factorization,NMF）是机器
学习领域中的一种高效的数据降维方法，也是一种特征提取的新方法，相较于一些传统算法（主成分分析（PCA）、独立成分分析（ICA）、矢量量化（VQ）、奇异值分解（SVD）等），它的分解过程和结果都是非负的，具有可解释性，这在心理学上符合人对整体的感知是由对组成整体的部分的感知构成的。近年来非负矩阵分解算法在图像处理和模式识别、文本聚类和数据挖掘、语音处理、生物医学工程和化学工程领域取得了很好的应用。
NMF可看做非线性约束优化问题，可将其转化为无约束极小化问题进行求解，我们引入了增广拉格朗日函数。目标函数对单独的X
或Y来讲均是凸函数，但同时对X,Y来讲却不是凸函数。因此要找一个全局最优解是不大现实的。最有效的求解非负矩阵分解的方法是交替最小化求解X,Y，这样就把一个非凸问题转化为两个简单的凸规划 。
由于在缺少实际问题的更多附加信息时，不能确定X,Y的初始值，通常取随机值初始化。如果用随机值初始化X,Y算法执行后得到的分解矩阵只是局部最小，而不是全局最优。因此需要用若干对随机取值的X,Y，多次执行算法，然后从得到的结果中选择一对最优的X,Y作为分解结果。NMF也具有约束优化问题收敛速度慢的不足，执行一次算法需要成百上千次迭代才能达到收敛，而多次执行算法，从中选择最优的分解作为结果使得时间开销非常大，不能满足实时系统的应用需求。为此我们考虑NMF初始化问题，这里我们采用非负双重奇异值分解初始化（NNDSVD），实验表明，在有限的迭代步数内，这样选取的初始值比随机初始值收敛的更快。
正文
一、问题描述
本文介绍了如下问题的一种算法：
给定一个非负矩阵M?Rm?n，找低秩非负矩阵X?Rm?q和Y?Rq?n，使得M?XYF最小。 该问题的模型如下
minf(X,Y)?X,Y1XY?M22Fs.t.X?0,Y?0,(1)
其中，q?min(m,n)，（工程应用中通常q??min(m,n)），
AF?nm2????a???ij?，A??aij?m?n
?j?1i?1?12二、算法
1、交错迭代法背景（ADM）
在有限维空间，经典交错迭代法（alternating direction method, ADM），解决了以下形式的凸规划问题：
x??y??minf(x)?g(y),s.t.Ax?By?c,（2）
其中f和g是定义在有限维空间上的闭集X和Y上的凸函数，A和B是系数矩阵，c是列向量。式(2)的增广拉格朗日函数为：
LA(x,y,?)?f(x)?g(y)??T(Ax?By?c)??2(Ax?By?c2)2
?是拉格朗日乘数向量，?是正的罚参数。
经典的交错迭代法是增广拉格朗日乘数法的拓展。该方法得到的是x，y交错迭代的最小值，紧随其后的是?的不断更新；也就是说，第k次迭代为：
xk?1?argminLA(x,yk,?k),x??(3a)(3b) (3c)yk?1?argminLA(xk,y,?k),y?Y?k?1??k???(Axk?1?Byk?1?c)（0,0.618）其中??是一个步长。（3a）的目标函数中仅包含f(x)，（3b）
仅包含g(y)，经典增广拉格朗日法要求同时涉及到x和y的函数（3b） LA(x,y,?k)的最小值，也就是说，用下式代替（3a）
（xk?1,yk?1）?argminLA(x,y,?k)
x?X,y?Y与（3a）（3b）相比，要困难的多。
2、NNDSVD
首先我们引出奇异值分解 定义 设A?Cm?n,AHA的特征值为
r ?1??2????r??r?1????n?0，
则称?i??i(i?1,2,?,r)为矩阵A的奇异值。
定理 设A?Cm?n,?1,?2,??r是A的r个正奇异值，则存在m阶酉矩阵
rU，n阶酉矩阵V，使得
A?U??DO??V， ?OO?其中D=diag(?1,?2,??r),而?i是满足?i??i(i?1,2,?r)的复数。 NNDSVD法：
?n任意给定一个矩阵A??m，根据如上定理将矩阵分解为??DO?A?U??V。
OO???nInputs:Matrix A??m?,integer k
3、主要算法
为了促进交替最小化的效用，我们先引进两个辅助变量U和V，考虑与(1)的等价模型：
X,Y,U,Vmin1XY?M22Fs.t.X?U?0,Y?V?0,U?0,V?0,(?)
其中U?Rm?q,V?Rq?n。它的增广拉格朗日函数为：
LA(X,Y,U,V,?,?)??1XY?M22F2F????X?U?????Y?V??2X?U2F??2Y?V
其中??Rm?q,??Rq?n是拉格朗日乘数，??0,??0分别是约束
X?U?0,Y?V?0的罚参数。对相同大小的矩阵A和B，定义A?B??i,jaijbij。
基于LA最小化得到(*)式的交错迭代公式如下
Xk?1?argminLA(X,Yk,M,Uk,Vk,?k,?k),Yk?1?argminLA(Xk?1,Y,M,Uk,Vk,?k,?k),U?0Uk?1?argminLA(Xk?1,Yk?1,M,Uk,Vk,?k,?k),
V?0Vk?1?argminLA(Xk?1,Yk?1,M,Uk?1,Vk,?k,?k),得到如下具体的迭代形式：