大规模非负矩阵分解的优化模型和并行算法研究及应用

自D.D.Lee等人于1999年在《Nature》上提出非负矩阵分解（NMF）后，NMF就引起科学界的广泛关注而且已被成功应用于图像处理、生物医学、文本聚类和语音信号处理等诸多领域。但是现有分解模型不是一般模型，其目标函数和约束不能普遍表示应用问题，并且针对大规模数据集，已有算法存在很大的局限性。本课题主要研究大规模非负矩阵分解模型和并行算法及其在图像压缩和特征提取中的应用。首先，考虑分解前后数据的误差及分解后数据的长度，构造非负矩阵分解的一般矩阵优化模型；其次，基于变换后的特殊模型，针对大规模数据集，运用块坐标下降的思想，研究双层并行分解算法；提出基于有效识别函数与拟牛顿算法相结合的分解算法，从理论上证明此类算法的收敛性及终止规则；通过增加稀疏约束，将问题转变为二阶锥规划，研究并行内点分解算法；最后，结合二维NMF分解思想，运用并行分解算法进行图像压缩和特征提取。

本项目主要研究内容是大规模非负矩阵分解的优化模型和并行算法以及在指纹图像中的应用。首先，对于大规模的非负矩阵优化模型，考虑图像变换前后的集合距离相近性不变的特性引入正则项，提出了一种图正则化的普适非负矩阵分解模型，修正了原有交替方向算法的更新规则，从而证明了算法的全局收敛性；然后，研究高维数据表示中局部嵌入流形的几何表示特性，建立基于局部线性嵌入的非负矩阵分解模型，此类模型在人脸识别库上聚类效果显著；利用非负矩阵分解算法代替梯度方法求解初始指纹方向场，实验结果表明此方法是可行的，并且在标准化的指纹库上显示非负矩阵分解算法求解指纹方向场比梯度方法和修正的梯度法效果好；结合稀疏表示非负矩阵分解算法产生指纹图像的旋转不变特征，基于此稳定特征进行指纹精确分类；结合稀疏表示和非负矩阵分解模型设计新的指纹压缩算法；研究非负矩阵分解在交替方向的算法框架下，提出了求解非负矩阵优化模型的并行算法，从理论上证明了算法的全局收敛性，并且在GPU的环境下用CUDA进行编程验证并行算法是有效的。