文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 几类非负矩阵分解算法及其在图像处理中的应用_柯艺芬
侵权投诉

几类非负矩阵分解算法及其在图像处理中的应用_柯艺芬

·2·1

非负矩阵分解算法

平顶山学院学报2013年

Aij∑i,j散度.

=

Bij∑i,j

=1时,此时D(A‖B)可化简为

自从Lee和Seung提出非负矩阵分解算法的基本框架后,在实际应用中,有关研究人员还根据具体的期望特性对分解结果施加除非负外的其他限制条件,如:稀疏性、正交性、光滑性等.下面将介绍现有的一些经典的非负矩阵分解算法.1.1

Poisson-ML算法

Lee和Seung在文献[12]中用最大似然(Max-imumLikelihood,ML)估计的想法构造第一个NMF算法,其中假设矩阵V中的每个元素Vij是相互独立的且服从于以(WH)ij为参数的泊松(Poisson)分布,并以此假设下的似然函数为价值函数:

n

m

K-L散度(或相对熵),L故称上述函数为广义的K-基于上述2种价值函数将NMF问题转化为求解如下2个优化问题:

问题1:

W,H≥0

minE(V‖WH)=min∑(Vij-(WH)ij)2,

W,H≥0i,j

(2)

问题2:min

W,H≥0

minD(V‖WH)=

V

-Vij+(WH)

ij

ij

ij

Vijlog∑(W,H≥0i,(WH)j

).

(3)

虽然函数E(V‖WH)和D(V‖WH)单独地对W和H来讲是凸的,但同时对W和H来讲却不是凸函数.因此要找到解决上述2个优化问题的全局最优解是不太现实的,然而还是有不少数值优化的技巧可用来寻找局部最优解.梯度下降法也许是最简单、最易行的方法,但其收敛速度缓慢,其他方法如共轭梯度下降法,它至少在局部极小点附近有比较快的收敛速度,但其实现起来比梯度下降法更复杂.基于梯度的收敛算法对于迭代步长的选取是非常敏感的,这使得其在实际应用中很不方便.于是Lee和Seung充分利用EM(Expectation-Maximization)算法中使用的辅助函数给出了单调下降收敛到2个价值函数稳定点的“乘子更新规则”并证明了其收敛性.

“乘子更新规则”对于优化问题1即(2)式,其如下:

(VHT)ik(WTV)kj

Wik←WikHkj←Hkj

(WHHT)ik(WTWH)kj

(4)

在此迭代规则下函数E(V‖WH)是单调非增的,E(V‖WH)的值当且仅当W和H为其稳定点时,将不变.

“乘子更新规则”对于优化问题2即(3)式,其如下:

HkjVij

(WH)ij

WikVij(WH)ij

F=

[Vijlog(WH)ij∑∑i=1j=1

-(WH)ij].

其迭代规则如下:

W←W

ik∑ ikj

Wik

W, ik←W∑pk p

Vij

HHW.← kjkj∑ik

(WH)iji

Vij

H,

(WH)ijkj

在上述迭代规则下,该算法收敛到价值函数的ML算一个局部极小值,且称这个算法为Poisson-法(本节之后将以算法的主要思路、目标函数、优被认为是NMF算法化方法或模型对算法命名),中的先驱算法.1.2

SED-EM算法和GKLD-EM算法

Lee和Seung在文献[13]中分别提出用矩阵A和B间的欧几里得距离的平方(SquareofSED)和广义的K-L散度EuclidianDistance,

(GeneralizedKullback-LeiblerDivergence,GKLD)作为价值函数:

1)矩阵A和B间的欧几里得距离的平方:E(A‖B)=‖A-B‖2=

(Aij∑i,j

-Bij)

2

E(A‖B)有最小值0.当且仅当A=B,2)广义的K-L散度:D(A‖B)=

Wik←Wik

∑j

∑(i,j

Aij

Aijlog-Aij+Bij,

Bij

)

Hkq∑q

,Hkj←Hkj

∑i

Wpk∑p

.(5)

D(A‖B)有最小值0.且当当且仅当A=B,在此迭代规则下函数D(V‖WH)是单调非增的,

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email