陈红莉

(武汉大学数学与统计学院,湖北武汉 430072)

1 引言

非负矩阵分解(NMF)是1999年由Lee和Seung[1]首次提出的,有着比较广泛的应用,如图像处理[1]、文本聚类[2]和社区发现[3]等.相较于其他的矩阵分解,由于元素的非负性,所以可解释性很强.比如:在处理图像时,负的像素点是没有意义的;在文本聚类时,正值代表文档以一定概率属于某个主题,负值则没有任何实际意义.

非负矩阵分解数学描述如下:给定非负矩阵A∈Rm×n,希望找到两个非负矩阵W∈Rm×k和H∈Rk×n,使得A≈WH.可以通过以下优化问题来找到W和H,

解决非负矩阵分解的方法有很多,比较常见的是由Lee和Seung在2001年提出的基准算法(Multiplicative Update Rules)[4]、Lin在2007年提出的投影梯度法[5]以及Kim和Park在2008年提出的交替非负最小二乘法(ANLS)[6].

不同于某些迭代算法,非负矩阵分解初始值的选择对于算法效果有很大影响.由Qiao提出的SVD-NMF[7]和Boutsidis等人提出的NNDSVD[8]算法都是基于矩阵A的奇异值分解,但是当矩阵A的维数很大时,对A直接进行奇异值分解是耗时的.不同于这两种方法,本文不直接对原矩阵A进行奇异值分解.本文利用Frieze等人[9]的思想,通过抽样构造一个更小的矩阵,对这个小矩阵来做奇异值分解,从而实现对W和H的初始化,这大大节省了算法的计算时间.

2 预备知识

首先,介绍一种最为经典的非负矩阵分解算法,即由Lee和Seung在2001年提出的基准算法(Multiplicative Update Rules)[4],以下简称MU算法.在本文的数值实验部分,将会用到MU算法.MU算法步骤如下

步骤1初始化,∀i,a,b,j.

步骤 2对于k=1,2,···,

从式子(2.1)和(2.2)中可以看出,如果在第k次迭代中W和H是非负的,那么……