1994 年，Paatero 和Tapper［136］提出正矩阵分解的概念，因为该算法较为复杂，该文并未引起学者们的广泛关注。1999 年，Lee 和Seung［137］提出了非负矩阵分解（Non⁃negative Matrix Factorization，NMF）算法的基本概念，通过对非负矩阵进行非负因子分解得到数据的潜在特征，分别以欧氏距离的平方和和最小化广义Kullback⁃Leibler 散度为目标函数，并给出了基于不同目标函数的两种算法的收敛性证明。2001 年，Seung 和Lee［138］给出了NMF 的研究成果，乘性迭代算法有可能收敛到稳定点［139］。

给定一个数据矩阵X∈Rm×n，NMF 算法的目的是把它分解为基因子矩阵U∈Rm×r与低维表示因子矩阵V∈Rn×r乘积的形式

其中，U∈Rm×r和V∈Rn×r是非负因子。

如果假设Xj和vj是矩阵X 和V 所对应的列向量，则式（3.1）又可写为Xj＝Uvj。其中，每一个Xj可看作非负矩阵U 的列向量的线性组合，U可看作为对数据矩阵X 进行线性逼近的一组基，V 是样本集X 在基U 上的非负投影系数。

一般情况下，r 的选取要满足（m＋n）r≪nm，从而因子矩阵U 和V 的秩将会远小于原始矩阵X 的秩。

Seung 和Lee［138］提出基于欧式距离平方的目标函数和基于广义Kullback⁃Leibler 散度的目标函数来度量上式（3.1）逼近的程度。（1）基于欧式距离平方的目标函数

其中，‖·‖F为Frobenius 范式。

（2）基于广义Kullback⁃Leibler 散度的目标函数(www.daowen.com)

虽然目标函数（3.2）是关于任何其中一个变量U 或V 的凸函数，但同时对变量U 和V 来说却是非凸函数。因此，求解上述两个问题的全局最优解是不现实的。文献［137］给出的迭代规则在适当的条件下收敛到两个目标函数的稳定点。根据Karush⁃Kuhn⁃Tuchker（KKT）最优性条件，（U，V）是问题（3.2）的稳定点当且仅当（U，V）满足条件

其中，☉表示Hadamard 乘积。

针对目标函数（3.2），Seung 和Lee 给出了迭代规则

上述迭代算法式（3.5）、式（3.6）可看作步长自学习的梯度下降算法，文献［138］证明了该更新规则每次迭代后目标函数值为非增的。这意味着在实际应用中只要根据规则重复迭代，算法一定会保证收敛到某个局部最优解。然而，上述迭代算法式（3.5）和式（3.6）的收敛速度不尽如人意，投影梯度法［140］及分层交替非最小二乘法等更快速的算法被相继提出。

基于NMF 的聚类算法结合了非负约束的矩阵分解思路［100，141］，可获得基于部分的数据表示和潜在特征，分解形式与分解结果的可解释性以及存储空间小等特点，是一种有效的矩阵低秩逼近的方法。由于该分解方法可解释性强，且符合人们对客观世界的认知规律等优点，吸引了研究者们的广泛关注［101，137⁃138，142］。

注：本书主要关注基于欧式距离平方的目标函数的表达形式，有关Kullback⁃Leibler 散度目标函数的约束优化问题可通过Frobenius 范式使用时的简单类比得到，文中将不再赘述。