Xk?1?(MYkT??Uk??k)(YkYkT??I)?1,T?1TYk?1?(Xk?1Xk?1??I)(Xk?1M??Vk??k),Uk?1?P?(Xk?1??k/?),Vk?1?P?(Yk?1??k/?),?k?1??k???(Xk?1?Uk?1),?k?1??k???(Yk?1?Vk?1)
其中??（0,1.618），(P?(A))ij?max?aij,0?，且只涉及到q?q阶的矩阵求逆，由于q?min(m,n)，计算复杂度降低了。 4、收敛性
为了简化记法，我们把所有的变量合并成如下形式
Z:?(X,Y,U,V,?,?)
定义1：点Z是(*)式的KKT点，如果满足如下条件：
(XY?M)YT???0,XT(XY?M)???0，X?U?0,Y?v?0,
??0?U,??U?0,??0?V,??V?0.其中对相同大小的矩阵A，B定义Am?n?Bm?n?(aij?bij)m?n 命题1.设?Zk??是由交错迭代法生成的一个序列，若满足条件k?1?lim(Zk?1?Zk)?0，则?Zk??的聚点是问题(*)的KKT点。因此，??(X,Y)kkk?1k?1k??的聚点是问题(1)的KKT点。
证明：我们重新排列ADM迭代公式如下：
(Xk?1?Xk)(YkYk??I)??((XkYk?M)Yk??(Xk?Uk)??k),TT(Xk?1Xk?1??I)(Yk?1?Yk)??(Xk?1(Xk?1Yk?M)??(Yk?Vk)??k),TT(Uk?1?Uk)?P?(Xk?1??k/?)?Uk,(Vk?1?Vk)?P?(Yk?1?Πk/?)?Vk,?k?1??k???(Xk?1?Uk?1),?k?1??k???(Yk?1?Vk?1),(Zk?1?Zk)?0，则k??时，上式可化为： 若limk??
(XkYk?M)Yk??k?0,TXk?1(Xk?1Yk?M)??k?0,TP?(Xk?1??k/?)?Uk?0,P?(Yk?1?Πk/?)?Vk?0,Xk?1?Uk?1?0,Yk?1?Vk?1?0,
??(X?,Y?,U?,V?,??,??)，满足(*)式KKT条显然，对于?Zk??的任何极限点Zk?1?,V?的非负性，因此只需证件的前四条。算法的约束条件保证了U??0，???U??0,???0。 ??0，???V?现检验以下两个方程：
????/?)?U?,P?(X
????,?/?)?VP(Y???X??0，?/?)?0，?)?0；??X??0，?)?0。若U则P?(?从而(?若U则(?ijijijijijijij??0且满足???0。得证。 ??0且满足???V??U??0。同理，?即?我们已证关于(*)式的序列?Zk??该命题成立，自然地，关于与(*)k?1式等价问题(1)的序列?(Xk,Yk)??，该命题同样成立。证毕。 k?1紧接着，我们得到如下推论：
推论1.若序列?Zk??收敛，则收敛到KKT点。 k?1三、总结
本文用NNDSVD对X,Y进行初始化，再用基于ADM的NMF算
法进行迭代，通过数值试验，将使用随机初始值的方法与NNDSVD初始化的方法进行对比，从程序运行数据可得出如下结论：进行NNDSVD初始化的方法要比取随机初始值的方法速度快，图像更清晰。 四、参考文献
[1] C.Boutsides ,E.Gallopoulos . SVD based initialization: A head start for nonnegative matrix factorization . January 2007
[2] Yangyang Xu ,Wotao Yin, Zaiwen wen,Yin Zhang. An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors. Arxiv preprint arXiv:1103.1168, 2011
[3] Yin Zhang . An Alternating Direction Algorithm for Nonnegative Matrix Factorization. January 19th 2010
[4] 殷海青. 图像分析中的非负矩阵分解理论及其最优化和正则化方法研究.2011.1
[5] 徐泰燕，郝玉龙.非负矩阵分解及其应用现状分析. 武汉工业学院学报.DOI:10.3969/j.issn.1009-4881.2010.01.030
[6] 杨志君，叶东毅. 基于加权的不完备非负矩阵分解算法. 计算机应用.Vol 30 No.5 May 2010
[7] 尹星云. 非负矩阵分解的基本原理和研究现状分析. SCIENCE&TECHNOLOGY INFORMATION 2011 NO.35 [8] 沈永康. 非负矩阵分解的稀疏性模型及初始化研究. 2011.5 [9] 黄廷祝,钟守铭,李正良. 矩阵理论 高等教育出版社,2003
附件： Matlab程序：
i = imread('Fig4.20(a).jpg'); M= im2double(i); [m,n] = size(M);
s = svd(M);l =max( size(s)); k = fix(l/2);
[u,s,v] = svds(M,k);
w = zeros(m,k);h = zeros(k,n);
w(:,1) = sqrt(s(1,1))*u(:,1); h(1,:)=sqrt(s(1,1))*v(:,1)'; xp=zeros(m,1);xn=zeros(m,1);yp=zeros(n,1);yn=zeros(n,1);
a=zeros(m,1);b=zeros(n,1); for j=2:k
x = u(:,j);y = v(:,j); for i=1:m if x(i)>=0 xp(i)=x(i); xn(i)=0; else
xp(i)=0; xn(i)=x(i);
end end for p=1:n
if y(p)>=0 yp(p)=y(p); yn(p)=0; else
yp(p)=0; yn(p)=y(p); end end
xpnorm=norm(xp);ypnorm=norm(yp);mp=xpnorm*ypnorm;
xnnorm=norm(xp);ynnorm=norm(yp);mn=xnnorm*ynnorm;
if mp>mn
a=xp/xpnorm;b=yp/ypnorm;sigma=mp; else
a=xn/xnnorm;b=yn/ynnorm;sigma=mn; end