收稿日期：2016年12月18日，修回日期：2017年1月25日
基金项目：国家自然科学基金项目（编号：61262006，61540050）；贵州省重大应用基础研究项目（编号：黔科合JZ 字［2014］2001）；贵州省科技厅联合基金（编号：黔科合LH 字［2014］7636）资助。
作者简介：徐梦珂，女，硕士研究生，研究方向：密码学理论与工程。许道云，男，博士，教授，研究方向：可计算性与计算复杂性、算法设计与分析。魏明俊，男，硕士研究生，研究方向：可计算性与计算复杂性。?1引言
在大数据时代，如何高效率地处理大规模数
据越来越受到人们重视。在现实生活中，巨大的
数据量往往给数据分析带来麻烦，即所谓的“维度
灾难”［1］。虽然许多数据都可以用矩阵形式表达，但是直接处理矩阵没有意义，矩阵分解就是将矩阵“分而治之”为数个矩阵的运算。非负矩阵分解是1999年由D.D.Lee 和H.S.Seung 首次提出，其基本思想是寻找一组基矩阵和线性组合参数来近似原始数据，同时约束表达基和参数都是非负的［2］。非负
矩阵分解形式描述如下：基于非负矩阵分解的低秩矩阵恢复模型
?徐梦珂1许道云2魏明俊2
（1.贵州大学数学与统计学院
贵阳550025）（2.贵州大学计算机科学与计算学院贵阳550025）摘要针对低秩矩阵恢复需要求解大规模矩阵核范数奇异值分解，计算复杂度高的缺陷，提出基于非负矩阵分解的低秩矩阵恢复模型。新模型通过对传统低秩矩阵恢复模型中的低秩矩阵进行非负因子分解，不但可以保持原始数据的局部特征，而且其低秩性可以快速求解矩阵低秩分解，从而避免了矩阵核范数求解大规模奇异值分解问题。在算法上采用多乘子交替迭代法（ADMM ），将全局问题分解为多个易求解的局部子问题，对每个子问题利用拉格朗日乘子法分别对低秩矩阵和稀疏矩阵进行迭代求解。在ORL ，AL_Gore 和Windows 三个图像数据库中Matlab 仿真实验结果表明，新模型求解算法比传统低秩矩阵恢复模型识别率高，降秩效果明显，算法的时间复杂度低，从而提高算法运行速度。
关键词非负矩阵分解；低秩矩阵恢复；多乘子交替迭代法；奇异值分解；图像识别
中图分类号
TP391.41DOI ：10.3969/j.issn.1672-9722.2017.06.002Low-rank Matrix Recovery Model Based on Non-negative Matrix Factorization
XU Mengke 1XU Daoyun 2WEI Mingjun 2
（1.College of Mathematics and Statistics ，Guizhou University ，Guiyang 550025）
（2.College of Computer Science and Technology ，Guizhou University ，Guiyang 550025）
Abstract To overcome the shortage of large-scale nuclear matrix singular value decomposition existing in low-rank matrix re?covery model ，the paper proposed low-rank matrix recovery model based on non-negative matrix factorization.Non-negative matrix factorization （NMF ）applied to the low-rank matrix ，which could quickly deal with the problem of the decomposition matrix of low-rank and avoid large-scale nuclear matrix singular value decomposition.Then the algorithm used alternarting directions method of multipliers （ADMM ）.ADMM divided the global problem into partial sub-problems.Each sub-problem used Lagrange multipliers
to solve low rank matrix and sparse matrix.Experimental results in ORL ，AL_Gore and Windows databases showed that low-rank re?covery model based NMF has higher recognition rate ，better reduction rank and lower the complexity of the algorithm than other tra?ditional low-rank recovery model.
Key Words non-negative matrix factorization （NMF ），low-rank matrix recovery ，alternating directions method of multipli?ers ，singular value decomposition （SVD ），image recognition Class Number TP391.41万方数据