前言

非负矩阵分解是20世纪90年代末兴起的数据降维方法，经过十几年的发展，已广泛应用于模式识别、数据挖掘和信息检索等领域。非负矩阵分解不同于经典的奇异值分解、正交三角分解和特征值分解等，其主要用于求解非负矩阵非负分解，即将非负矩阵分解成两个非负子矩阵的乘积。由于非负矩阵分解把数据表示成特征的“纯”加性叠加，这种数据表示方法天然地具有稀疏性，与人脑对信号的响应机制相一致，能够有效抑制信号噪声。同时，特征中不含任何负元素，符合真实世界的物理假设。因此，非负矩阵分解广泛应用于文本聚类、邮件监控、盲源信号分离、音频信号分析、人脸识别、图像标注、图像分割、光谱图像分析、基因微阵列数据分析等领域。近年来，非负矩阵分解引起越来越多的关注，中国的浙江大学，美国贝尔试验室、田纳西大学、维克森林大学、佐治亚理工学院，芬兰赫尔辛基大学，日本RIKEN脑科学研究所等研究机构都开展了非负矩阵分解的研究工作。他们的研究成果极大地推动了非负矩阵分解的发展，把非负矩阵分解的应用拓展到互联网、信息安全、遥感图像和数学模型求解等领域。因此，开展非负矩阵分解的研究具有重要的现实意义。

本书从模型的框架入手，建立系列非负矩阵分解模型的抽象数学框架，即非负块配准框架（Non-negative Patch Alignment Framework，NPAF），从统一的视角分析现有的非负矩阵分解模型，并用以开发新的非负矩阵分解模型。根据非负块配准框架分析，本书提出非负判别局部块配准模型（Non-negative Discriminative Locality Alignment，NDLA），弥补了经典非负矩阵分解模型的缺点，提高了非负矩阵分解模型的分类性能。为了弥补经典非负矩阵分解的优化算法收敛速度慢的缺点，本书提出在线搜索中利用牛顿法快速搜索步长，进而提出非负块配准框架的快速梯度下降（Fast Gradient Descent，FGD）算法。为了弥补经典非负最小二乘问题求解算法的缺点，本书利用最优梯度下降算法在无须线搜索的情况下以二阶收敛速度求解非负最小二乘问题，提出非负矩阵分解的高效求解算法，即NeNMF算法。在此基础上提出非负矩阵分解的高效求解算法，并开发非负块配准框架的最优梯度下降算法。为了弥补经典优化算法应用于流数据处理时计算开销过大的缺点，本书提出非负矩阵分解在线优化算法，利用健壮随机近似算法更新基矩阵，提出OR-NMF算法，提高在线优化算法的健壮性。本书的主要创新点包括以下几点。

（1）非负块配准框架。提出基于非负块配准的非负矩阵分解框架——非负块配准框架（NPAF）。自非负矩阵分解提出以后，研究人员提出多种改进模型。例如，利用局部视觉特征近似正交的特点，提出局部非负矩阵分解模型；利用流形学习技术，提出图正则非负矩阵分解模型以保持数据几何结构；利用Fisher判别技术，提出判别非负矩阵分解模型以引入标签信息。然而，这些非负矩阵分解模型是由研究人员根据各自的需求和经验而设计的，内在差异大，难以揭示和比较其模型性能，实际应用中给工程人员选择模型带来困难。本书基于块配准技术，建立非负块配准框架，从统一的角度理解已有非负矩阵分解模型，揭示其内在差异和共同特性，一方面指导工程人员选择模型，另一方面帮助研究人员开发新的非负矩阵分解模型。利用拉格朗日乘子法，提出乘法更新规则算法（Multiplicative Update Rule，MUR）优化非负块配准框架，并用辅助函数技术证明乘法更新规则算法的收敛性。该算法可用于求解非负块配准框架的大多数派生模型。

（2）非负判别局部块配准框架。根据非负块配准框架的分析，提出非负判别局部块配准框架。从非负块配准框架的角度出发，局部非负矩阵可分解为样本和基向量并分别建立由自身组成的样本块，在局部优化过程中保持数据的能量；图正则非负矩阵分解为样本建立由自身和有限最近邻组成的样本块，在局部优化过程中保持数据的几何结构，但是忽略样本判别信息；判别非负矩阵分解为样本和各类中心点建立样本块且样本块分别由所有同类样本和中心点组成，在局部优化过程中保持数据判别信息，但是由全部样本组成的样本块要求数据服从高斯分布。非负判别局部块配准模型弥补了已有非负矩阵分解模型的缺点，为每个样本建立两类样本块：类内块由同类样本中有限最近邻组成，局部优化过程中保持数据局部几何结构，放宽数据高斯分布假设；类间块由不同类样本中有限最近邻组成，局部优化过程中最大化类间边界，从而保持数据判别信息，提高非负矩阵分解的分类效果和健壮性。本书利用全局配准技术把两种局部优化过程映射到全局坐标系进行并把二者结合，套用非负块配准的乘法更新规则算法优化所提非负判别局部块配准模型。数值试验表明，非负判别局部块配准模型的分类效果优于其他非负矩阵分解算法。在有遮挡的情况下，其分类效果优于其他数据降维算法。

（3）非负块配准框架快速梯度下降算法。从梯度下降的角度改进非负块配准乘法更新规则算法，利用牛顿法实现快速线搜索，提出非负块配准快速梯度下降（FGD）算法。快速线搜索沿着调整负梯度方向搜索最优步长，在不超出第一象限边界的情况下更新矩阵因子，大大提高了乘法更新规则的收敛速度。本书证明了快速梯度法的收敛性。为了解决矩阵因子整体的最优步长可能蜕化为1的问题，本书为矩阵因子的列（或行）设置步长，用多变量牛顿法搜索步长向量，提出多步长快速梯度下降（Multi-variables FGD，MFGD）算法，并证明其收敛性。为了解决多变量牛顿法Hessian矩阵求逆开销大的问题，本书提出用伪牛顿法L-BFGS直接近似Hessian矩阵的逆与梯度的乘积，提出有限记忆快速梯度下降（Limited-memory FGD，L-FGD）算法。数值试验表明，FGD算法的收敛速度比乘法更新规则快近5倍，MFGD算法可以解决FGD步长蜕化的问题，L-FGD算法可处理较大规模数据。

（4）非负矩阵分解最优梯度下降算法。通过分析非负矩阵分解优化子问题的性质，利用最优梯度下降算法交替更新矩阵因子，提出非负矩阵分解最优梯度下降算法。非负矩阵分解优化问题是NP-难问题，继乘法更新规则之后出现了非负最小二乘法、投影梯度法、伪牛顿法和Active Set方法等一系列方法。然而，乘法更新规则收敛速度慢且存在零元素问题；非负最小二乘法无法从理论上保证收敛性；投影梯度法的线搜索过程计算开销过高；伪牛顿法在求解过程中计算Hessian矩阵的逆，计算开销大且存在数值不稳定问题；Active Set方法在矩阵不满秩时会出现数值问题。因此，非负矩阵分解的高效优化问题仍然是个开放性问题。本书将非负矩阵分解优化问题看成两个子问题，从数学上证明了每个子问题都是凸问题且其梯度是Lipschitz连续的，从而利用最优梯度下降算法以的收敛速度求解每个子问题，提出非负矩阵分解高效优化算法，即NeNMF算法，弥补了经典非负矩阵分解优化算法的缺点。通过分析非负块配准框架优化问题的子问题的性质，本书成功地将NeNMF算法用于优化非负块配准框架，提出非负块配准框架的最优梯度下降算法。数值试验表明，NeNMF算法的收敛速度快于其他非负矩阵分解优化算法；基于NeNMF的非负块配准框架优化算法也快于常用的乘法更新规则算法等非负块配准框架优化算法。

（5）非负矩阵分解在线优化算法。提出非负矩阵分解在线优化（OR-NMF）算法，利用健壮随机近似算法以在线的方式更新基矩阵。非负矩阵分解在线优化算法的空间复杂度与样本维数和样本规模成正比，由于计算机内存容量的限制，难以满足流数据处理的需求。此外，新样本到达时，经典非负矩阵分解算法需要“重新启动”以更新分解结果，导致时间开销不断增加。因此，研究人员提出在线非负矩阵分解算法，利用新到达的样本更新分解结果，弥补经典非负矩阵分解算法时间复杂度高和空间复杂度高两方面的缺限。然而，已有的在线非负矩阵分解算法的收敛速度受噪声、矩阵不满秩等因素影响，存在数值不稳定的问题。本书提出在新样本到达时利用健壮随机近似算法以的收敛速度更新基矩阵，提高在线非负矩阵分解的健壮性。利用准鞅理论，本书证明了所介绍算法的收敛性。为了弥补空间复杂度过高的缺点，本书提出用缓冲池技术存储有限的历史样本，用新样本替换缓冲池中的旧样本以保证基矩阵引入最新的样本统计信息。图像标注试验表明，OR-NMF算法可以更好地提取图像语义空间信息。