矩阵弹性网

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2017,28(6):15471564[doi:10.
13328/j.
cnki.
jos.
005260]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563矩阵补全模型及其算法研究综述陈蕾1,2,3,陈松灿11(南京航空航天大学计算机科学与技术学院,江苏南京210016)2(江苏省无线传感网高技术研究重点实验室(南京邮电大学),江苏南京210003)3(南京邮电大学计算机学院,江苏南京210003)通讯作者:陈蕾,E-mail:chenlei@njupt.
edu.
cn摘要:近年来,随着压缩感知技术在信号处理领域的巨大成功,由其衍生而来的矩阵补全技术也日益成为机器学习领域的研究热点,诸多研究者针对矩阵补全问题展开了大量卓有成效的研究.
为了更好地把握矩阵补全技术的发展规律,促进矩阵补全理论与工程应用相结合,针对矩阵补全模型及其算法进行了综述.
首先,对矩阵补全技术进行溯源,介绍了从压缩感知到矩阵补全的自然演化历程,指出压缩感知理论的发展为矩阵补全理论的形成奠定了基础;其次,从非凸非光滑秩函数松弛的角度将现有矩阵补全模型进行分类,旨在为面向具体应用的矩阵补全问题建模提供思路;然后综述了适用于矩阵补全模型求解的代表性优化算法,其目的在于从本质上理解各种矩阵补全模型优化技巧,从而有利于面向应用问题的矩阵补全新模型求解;最后分析了矩阵补全模型及其算法目前存在的问题,提出了可能的解决思路,并对未来的研究方向进行了展望.
关键词:稀疏学习;矩阵补全;压缩感知;矩阵分解;随机优化中图法分类号:TP181中文引用格式:陈蕾,陈松灿.
矩阵补全模型及其算法研究综述.
软件学报,2017,28(6):15471564.
http://www.
jos.
org.
cn/1000-9825/5260.
htm英文引用格式:ChenL,ChenSC.
Surveyonmatrixcompletionmodelsandalgorithms.
RuanJianXueBao/JournalofSoftware,2017,28(6):15471564(inChinese).
http://www.
jos.
org.
cn/1000-9825/5260.
htmSurveyonMatrixCompletionModelsandAlgorithmsCHENLei1,2,3,CHENSong-Can11(CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,China)2(JiangsuHighTechnologyResearchKeyLaboratoryforWirelessSensorNetworks(NanjingUniversityofPostsandTelecommunications),Nanjing210003,China)3(SchoolofComputerScience,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China)Abstract:Inrecentyears,withthegreatsuccessofcompressedsensing(CS)inthefieldofsignalprocessing,matrixcompletion(MC),derivedfromCS,hasincreasinglybecomeahotresearchtopicinthefieldofmachinelearning.
Manyresearchershavedonealotoffruitfulstudiesonmatrixcompletionproblemmodelingandtheiroptimization,andconstructedrelativelycompletematrixcompletion基金项目:国家自然科学基金(61472186,61572263,61403208);江苏省自然科学基金(BK20161516,BK20151511);中国博士后科学基金(2015M581794);江苏省高校自然科学研究面上项目(15KJB520027);江苏省博士后科研资助计划(1501023C);南京邮电大学校级科研基金(NY214127,NY215097)Foundationitem:NationalNaturalScienceFoundationofChina(61472186,61572263,61403208);NationalScienceFoundationofJiangsuProvince(BK20161516,BK20151511);PostdoctoralScienceFoundationofChina(2015M581794);ProjectofNaturalScienceResearchofJiangsuUniversity(15KJB520027);PostdoctoralScienceFoundationofJiangsuProvince(1501023C);NUPTSF(NY214127,NY215097)收稿时间:2016-05-26;修改时间:2016-11-03;采用时间:2017-01-19;jos在线出版时间:2017-02-20CNKI网络优先出版:2017-02-2014:05:55,http://www.
cnki.
net/kcms/detail/11.
2560.
TP.
20170220.
1405.
018.
html1548JournalofSoftware软件学报Vol.
28,No.
6,June2017theory.
Inordertobettergraspthedevelopmentprocessofmatrixcompletion,andfacilitatethecombinationofmatrixcompletiontheoryandengineeringapplications,thisarticlereviewstheexistingmatrixcompletionmodelsandtheiralgorithms.
First,itintroducesthenaturalevolutionprocessfromCStoMC,andillustratesthatthedevelopmentofCStheoryhaslaidthefoundationfortheformationofMCtheory.
Second,thearticlesummarizestheexistingmatrixcompletionmodelsintothefourclassesfromtheperspectiveoftherelaxationofnon-convexandnon-smoothrankfunction,aimingtoprovidereasonablesolutionsforspecificmatrixcompletionapplications;Third,inordertounderstandtheinherentoptimizationtechniquesandfacilitatesolvingnewproblem-dependentmatrixcompletionmodel,thearticlestudiestherepresentativeoptimizationalgorithmssuitableforvariousmatrixcompletionmodels.
Finally,articleanalyzestheexistingproblemsincurrentmatrixcompletiontechnology,proposespossiblesolutionsfortheseproblems,anddiscussesthefuturework.
Keywords:sparselearning;matrixcompletion;compressedsensing;matrixdecomposition;stochasticoptimization近年来,随着压缩感知[1,2]理论的流行,矩阵补全技术(matrixcompletion)[3]也越来越受到研究者的广泛关注.
众所周知,压缩感知研究的是如何根据低维的测量值向量恢复出高维稀疏的原始信号向量.
而在很多实际问题中,例如图像和视频处理、推荐系统、文本分析等等,待恢复的数据通常是用矩阵表示的,这使得对问题的理解、建模、处理和分析更为方便.
然而,这些数据经常面临缺失、损毁和噪声污染等问题,如何在这些情形下得到准确的数据,就是研究者们所要解决的问题.
因此,压缩感知理论便自然地从向量空间被拓展至矩阵空间,从而利用矩阵的二阶稀疏性(即矩阵的低秩性),通过采样矩阵的部分元素来恢复目标矩阵.
在机器学习领域,这类问题通常被刻画为矩阵补全问题.
迄今为止,矩阵补全理论已在图像修复[4]、多标记图像分类[5]、网络异常流量监测[6]、无线传感器网络数据收集[7]、核磁共振图像分割[8]、声源定位与阵列校准[9]、社交网络链接关系预测[10]、运动侦测与估计[11]、半监督聚类[12]、推荐系统[13]、相位检索[14]、地震数据重构[15]、问答社区专家发现[16]、无线传感器网络节点定位[17]、Web服务QoS属性预测[18]以及Web服务标签修正[19]等领域得到了重要应用,已逐渐成为机器学习、模式识别以及计算机视觉领域中的主要研究热点之一.
就矩阵补全理论的学术影响而言,在著名的学术论文数字图书馆ACM,IEEE,Elsevier,Springer以及GoogleScholar中用"MatrixCompletion"作为关键字进行检索发现:与矩阵补全有关的学术论文发表数量,近年来一直呈增长趋势.
国内外众多研究机构如卡内基梅隆大学[20]、斯坦福大学[21]、加州理工学院[22]、明尼斯达大学[23]、亚利桑那州立大学[24]、哥伦比亚大学[25]、莱斯大学[26]、华盛顿大学[27]、加州大学伯克利分校[28]、加州大学洛杉矶分校[29]、IBM[30]、德克萨斯州大学奥斯汀分校[31]、新加坡国立大学[32]、密歇根州立大学[33]、鲁汶大学[34]、伊朗沙力夫理工大学[35]、滑铁卢大学[36]、香港中文大学[37]、北京大学[38]、清华大学[39]、南京大学[40]、上海交通大学[41]、西安电子科技大学[42]、浙江大学[43]、南京邮电大学[44]等研究机构都开展了矩阵补全研究工作.
他们的研究成果不仅推动了矩阵补全理论的发展,而且展现了矩阵补全理论诱人的应用前景.
本文首先对标准的矩阵补全模型进行溯源,探讨压缩感知和矩阵补全的关系,指出压缩感知的相关理论和技术可以自然地推广到矩阵补全;然后综述近年来涌现的各种矩阵补全模型,从非凸非光滑秩函数松弛的角度将其分为基于核范数松弛的矩阵补全模型、基于矩阵分解的矩阵补全模型、基于非凸函数松弛的矩阵补全模型和其他类型的矩阵补全模型;接着,从独立于问题模型的角度综述适用于矩阵补全模型求解的代表性优化方法,其目的在于从本质上理解矩阵补全模型优化技巧,从而有利于问题依赖的新模型求解;最后,本文分析了现有矩阵补全研究存在的问题,指出现有矩阵补全模型及其算法仍然存在噪声容错性差、归纳推广性不足和先验信息融合性不强等问题,同时,所设计的算法大多受制于单机内存和计算效率的约束,难以适用于大规模问题求解;针对这些问题,作者提出了可能的解决思路,并对未来研究方向进行了展望.
本文第1节对矩阵补全技术进行溯源,指出压缩感知理论的发展为矩阵补全理论的形成奠定了基础.
第2节综述现有矩阵补全模型.
第3节综述适用于矩阵补全模型求解的代表性优化算法.
第4节对矩阵补全模型及其算法研究目前存在的问题进行分析,指出可能的解决方案,并对未来研究工作进行展望.
最后是本文的总结.
1矩阵补全溯源由Donoho[1]提出的压缩感知技术是信号处理领域的研究热点,其核心思想是:基于信号的可压缩性或稀疏陈蕾等:矩阵补全模型及其算法研究综述1549性,通过低分辨率、欠Nyquist采样数据的非相关观测来实现高维信号的感知.
压缩感知理论突破了香农定理对信号采样频率的限制,能够以较少的采样资源、较高的采样速度和较低的软硬件复杂度获得原始型号的测量值,已被广泛应用于数字相机、医学成像、遥感成像、地震勘探、多媒体混合编码、通讯等领域,在理论和应用方面均取得了极大成功[39].
从数学上来看,压缩感知主要研究对于以向量x∈n表示的稀疏信号,如何在mr,有如下等式成立:1222*,1||||mins.
t.
}2nknkTFFLQXLQXLQ**∈∈=+=(16)基于此,标准矩阵补全问题也可以直接建模为12222,1min22nkknFFFLQPMLQLQΩλ**∈∈++(17)从而,采用分块坐标下降算法即可容易求解.
然而,由于问题(15)非凸,该问题可能存在非全局最优的驻点解.
幸运的是,Mardani等人在文献[53]中已经证明,只要满足如下较为宽松的条件:||PΩ(MLQ)||F≤λ(18)则问题(16)的解XLQ=即为全局最优解.
2.
3基于非凸函数松弛的矩阵补全模型基于非凸函数松弛的建模方法是基于核范数松弛建模方法的另一种可替代方法.
研究者认为:虽然核范数是秩函数在单位球内的最佳凸逼近,但二者之间仍存在较大差异.
因此,他们提出可以引入一些更加紧致的非凸函数来松弛秩函数.
例如,Nie等人在文献[31]中将矩阵Schattenp-范数引入模型中代替秩函数,将矩阵补全问题建模为12minpnnPPsPXXPMXΩλ*∈+(19)其中,1212min{,}111pnnnnppppSipijiijXXXXσ=====∑∑∑,0=;endforifstoppingcriterionissatisfiedthenreturn1kkmXXendifendfor分块坐标下降算法具有以下3个特点:(i)如果函数F(X1,…,Xm)连续可微且每个子问题均可解,那么算法能够保证收敛;(ii)如果函数F(X1,…,Xm)非光滑,那么算法不一定收敛;(iii)如果非光滑部分是可分离的,那么算法也能保证收敛.
3.
3矩阵空间Bregman迭代算法Bregman迭代算法起源于凸分析中一种寻求等式约束下目标函数极值的优化方法[64],Osher等人[65]于2005年首先将该方法应用于全变分图像复原,随之被拓展应用到压缩感知[66]、图像去噪[67]等领域,已成为求解低秩矩阵恢复问题的有效方法之一.
对于任一凸函数J(X)在点X处的Bregman距离定义为PJDXXJXJXPXX34)其中,()PJX∈为J在点X处的一个次梯度.
假设J(X)和H(X)为m*n上两个凸函数,其中,函数H(X)可微,J(X)不可微,考虑无约束优化一般框架:min()()mnXJXHX*∈+(35)可以对不可微函数J(X)引入Bregman距离,转化为迭代求解下述子问题序列:1argminargmin**+∈∈kmnmnkPkkJXXXDXXHXJXPXHX(36)进一步地,由于Xk+1是上述子问题的最优解,因此,0矩阵属于目标函数在Xk+1处的次微分,即:0∈J(Xk+1)Pk+H(Xk+1)(37)由于Pk+1∈J(Xk+1),化简后可得:Pk+1=PkH(Xk+1)(38)求解上述无约束优化问题(35)的Bregman迭代公式如下:111argmin()mnkkXkkkXJXPXHXPPHX*+∈++=(39)算法4详细描述了求解无约束优化一般框架的矩阵空间Bregman迭代算法实现步骤.
算法4.
矩阵空间Bregman迭代算法.
Input:maximumiterationtimeN;Output:Xopt.
Initialization:chooseX0=P0=0;fork=0,1,…,Ndo1556JournalofSoftware软件学报Vol.
28,No.
6,June2017121argminnnkkXXJXPXHX*+∈Pk+1=PkH(Xk+1)ifstoppingcriterionissatisfiedthenreturnXk+1endifendfor需要指出的是,矩阵空间Bregman迭代算法通常假定子问题121argminnnkkXXJXPXHX*+∈有解析解.
当该子问题没有解析解的时候,可以采用第3.
1节所述的近邻梯度下降算法或者加速近邻梯度算法迭代求解.
考虑到实际上不需要求出子问题的精确解就足以使算法最终收敛到原问题的最优解,因此只需更新Xk+1一次得到子问题的一个近似解即可,据此可以得到一个更为简洁且实际收敛速度较快的矩阵空间线性Bregman迭代算法.
此外,与传统的求解约束优化问题的惩罚函数与连续策略相比,Bregman迭代算法主要有两个优点:(i)Bregman迭代收敛速度快,特别是当目标函数中包含L1范数正则化项时,只需少许几次迭代求解无约束问题即可获得很好的结果;(ii)连续策略需要在迭代过程中不断减小步长的取值,而步长的取值在Bregman迭代过程中可保持不变,因此可以选择一个合适的步长值最小化子问题的条件数,同时可避免参数调整程中连续策略的数值不稳定性.
3.
4交替方向乘子法交替方向乘子法[68](alternatingdirectionmethodofmultipliers,简称ADMM)是一种求解凸优化问题的算法框架,通常也称为Douglas-Rachford分裂算法[69],适用于求解分布式凸优化问题.
ADMM算法最早由Gabay和Mercier[70]于1976年提出,并被Boyd等人于2011年重新综述并证明其适用于大规模分布式优化问题.
ADMM算法融合了对偶分解和增广Lagrangian的优点,在解决大规模分布式计算系统和面向大规模问题的优化求解中起着非常重要的作用,近年来受到了广泛关注,尤其在机器学习领域得到了很好的应用.
标准ADMM算法旨在求解约束优化一般框架(F1)的特例,即,如下带线性约束的可分离目标函数优化问题:12min()()s.
t.
mnXFXFZAXBZC*∈++=(40)该算法先构造相应的增广拉格朗日函数:()2122||||TFLXZYFXFZtraceYAXBZCAXBZCρβ41)然后,通过交替最小化增广拉格朗日函数来更新变量X,Y,Z.
算法5描述了标准ADMM算法的详细步骤.
算法5.
交替方向乘子法(alternatingdirectionmethodofmultipliers,简称ADMM).
Input:maximumiterationtimeN,parameterβ;Output:Xopt,Zopt.
InitializeY0=Z0=0;fork=0,…,Ndo111111argmin(,,)argmin(,,)()kkkxkkkzkkkkXLXZYZLXZYYYAXBZCρρρ++++++===++;ifstoppingcriterionissatisfiedthenreturnXk+1,Zk+1;endifendfor为了更好地适应大规模问题求解,众多学者对标准ADMM算法进行了改进,分别提出了同步分布式陈蕾等:矩阵补全模型及其算法研究综述1557ADMM[68]、异步分布式ADMM[71]及快速随机ADMM[72]等.
特别地,对于只涉及两个变量的标准ADMM算法,南京大学何炳生等人在文献[73]中已经证明,其收敛率为O(N1).
然而,对于3个或3个以上变量的凸约束优化问题,如果沿用上述标准的ADMM求解步骤,则其收敛性难以保证.
为此,何炳生教授等人提出了一种有收敛性保证的基于高斯回代方法的多变量ADMM算法[74],北京大学林宙辰教授等人则提出了一种更为简单的有收敛性保证的基于自适应惩罚的并行分裂线性ADMM算法[75].
3.
5随机优化算法随着信息技术和计算技术的迅猛发展,行业应用和科学研究中的数据正以惊人的速度增长,产生了大规模海量数据,机器学习也正面临着数据规模日益扩大的严峻挑战,传统的机器学习优化方法受制于单机计算效率和内存空间的限制,每次迭代都要遍历所有样本,已经不能满足实际应用中大规模问题快速求解的需求.
由于随机优化算法通常假设样本是独立同分布的,从而随机抽取单个样本的梯度是目标函数梯度的无偏估计[76],进而可以通过每次迭代时仅随机选用单个或部分样本的方法来代替批处理方法.
因此,随机优化算法可视为求解大规模机器学习问题的高效方法之一.
常用的随机优化算法包括随机梯度下降算法[77]、随机坐标下降算法[78]、随机交替方向乘子算法[79]和随机近邻梯度下降算法[80]等.
鉴于随机梯度下降算法、随机坐标下降算法和随机交替方向乘子算法分别是其各自确定性算法版本的自然推广,本节将主要介绍随机近邻梯度下降算法.
如第2.
1节所述,基于核范数松弛的矩阵补全模型在求解过程中均不可避免地需要求解如下子问题:2*1min2mnFXFXJXXJXXWλ*∈=+=其中(42)该子问题固然可以采用奇异值阈值算子求得闭式解,但由于涉及到复杂的奇异值分解,其时间复杂度和空间复杂度分别达到了O(mnmin(m,n))和O(mn),即使采用改进的部分奇异值分解[81]或者随机奇异值分解[81]算法,依然无法适用于大规模问题.
众所周知,随机梯度下降算法通过采用目标函数随机样本梯度的无偏估计代替目标函数所有样本的实际梯度,从而使得每次迭代的计算量非常小,计算复杂度因而不会随着样本量的增加而急剧增加.
受此启发,南京大学张利军等人针对现有的近邻梯度下降算法,提出了求解上述子问题的随机近邻梯度下降算法[80],该算法通过计算函数J(X)在Xt处的低秩随机无偏梯度TttttGGYY=并引入增量奇异值分解[81],使得算法的时间和空间复杂度分别减少到O((m+n)r2)和O((m+n)r),其中,r为目标矩阵的秩.
算法6给出了随机近邻梯度下降算法的详细步骤.
算法6.
随机近邻梯度下降算法(stochasticproximalgradientdescent,简称SPGD).
Input:maximumiterationtimeN,theregularizationparameterλ;Output:Xopt.
InitializeX1=0;fort=1,2,…,Ndo/YZk=,whereeachcolumnsofZisdrawnuniformlyatrandomandindependentlyofeachotherfrom1nnene;TttttGGYY=,whereGtisasubgradientofJ()atXt;21*1argmin2mnttttFtXXXXGXηηλ*+∈ifstoppingcriterionissatisfiedthenreturnXt+1;endifendfor3.
6各类优化算法优缺点分析上述5类优化算法是求解矩阵补全模型的代表性算法.
表2分析了这些算法各自的收敛率及其求解优势、1558JournalofSoftware软件学报Vol.
28,No.
6,June2017存在缺点,其中:随机优化算法涉及到多种具体算法,限于篇幅,表2仅给出了随机近邻梯度下降算法的收敛率;其他随机优化算法的收敛率可查阅相应的参考文献.
Table2Convergencerate,advantagesanddisadvantagesanalysisofdifferentrepresentativeoptimizingalgorithms表2各类代表性优化算法收敛率及其优缺点分析优化算法优点缺点收敛率近邻梯度下降算法面向小规模问题求解时补全性能好,收敛速度快求解矩阵补全模型时涉及到复杂的矩阵奇异值分解,因此无法求解中大规模问题近邻梯度下降算法的收敛率为O(N1);加速近邻梯度下降算法的收敛率为O(N2)分块坐标下降算法应用范围广,简单易实现,是矩阵补全模型求解的基本算法当目标函数非光滑时算法无收敛性保证目标函数凸光滑或者非光滑部分可分离时算法有收敛性保证,其收敛率为O(N1)矩阵空间Bregman迭代算法实际应用中无需求解子问题的精确解,算法实际收敛速度快不可分布式并行实现,无法求解大规模问题O(N1)交替方向乘子法融合了对偶分解和增广Lagrangian方法的优点,可分布式并行实现,适用于大规模问题求解在高精度要求下算法收敛很慢;但在中等精度要求下,ADMM的收敛速度可以接受(一般迭代数十次即可)O(N1)随机优化算法可分布式并行实现,适用于大规模问题求解仅适用于样本独立同分布情形,实际应用中该假设并不总是成立随机近邻梯度下降算法的收敛率为(log/)ONN4存在的问题及未来研究方向4.
1存在的问题然而,尽管现有矩阵补全研究在模型及算法方面取得了众多进展,但仍然存在如下几点不足.
(1)噪声容错性差早期的矩阵补全模型大多只是简单地假设采样矩阵受到单一的高斯噪声污染,并不能解决实际问题中遇到的野值(outlier)噪声和结构化噪声污染问题.
为此,针对野值噪声情形下的矩阵补全问题,南京大学陶敏和何炳生等人在文献[82]中采用Laplacian分布拟合野值噪声,提出了一种基于核范数松弛的L1范数正则化矩阵补全模型,并设计了相应的交替分裂增广拉格朗日求解算法.
Yan等人则在文献[83]中提出一种基于矩阵分解的L1范数正则化矩阵补全模型,在求解该模型时,他们采用了自适应匹配追踪算法.
更进一步,Chen等人在文献[84]中对何等人的核范数松弛模型进行了严格的理论分析,从理论上证实了基于核范数松弛的L1范数正则化矩阵补全模型的有效性.
另一方面,针对结构化噪声污染问题,Chen等人在文献[85]中率先提出一种基于增广拉格朗日乘子法的核范数松弛矩阵补全模型.
类似地,我们也在文献[44]中提出了一类基于线性Bregman迭代算法的结构化噪声矩阵补全模型.
与已有矩阵补全模型相比,我们的模型不仅能够更好地恢复结构化噪声矩阵的缺失元素,还能精确地辨识出采样矩阵中被污染元素所在行的位置信息.
此外,我们也对复合噪声情形下的矩阵补全应用展开了一些探索,在文献[17]中提出了一类适用于高斯、野值复合噪声情形的矩阵补全算法,并将其成功应用于无线传感网节点定位.
然而实际问题中,采样矩阵遇到的噪声类型常常是不可预知的,并且通常表现为多种噪声类型的复合.
因此在构建矩阵补全问题模型时,如何自适应地拟合不可预知的复杂噪声信息从而提高矩阵补全模型的噪声容错性能,仍然有待进一步的深入研究.
(2)归纳推广性不足现有的矩阵补全模型仅能处理观测样本的数据补全问题,而对于未见样本则无法处理,在实际应用中表现出了明显的归纳推广性缺陷.
例如:Gogn等人在文献[13]中将矩阵补全技术应用到推荐系统时,无法克服冷启动问题;Yi等人在文献[12]中将矩阵补全应用到半监督聚类时,所设计的成对相似性矩阵补全算法不能进行联机半监督聚类,对新加入样本无法进行类别预测;南京大学Xu等人在文献[86]中提出了一种融合辅助信息的加速矩阵补全算法应用于多标记学习,然而他们同样未能解决未见样本的分类问题.
陈蕾等:矩阵补全模型及其算法研究综述1559(3)先验信息融合性不强现有的矩阵补全理论往往忽略了数据固有的先验信息,这类先验信息通常包括目标矩阵的先验稀疏信息、应用问题的先验特征信息和结构信息等.
例如:Cabral等人在文献[5]中利用矩阵补全的方法解决多标记图像分类问题时,忽略了图像与图像、标记与标记之间的先验相似性关联信息;Mardani等人在文献[6]利用矩阵补全方法监测网络异常流量时,忽略了网络流量的先验特征和结构信息;Natarajan等人在文献[87]中将矩阵补全算法应用于基因-疾病预测时,忽略了基因-疾病关联矩阵的先验稀疏信息.
(4)算法扩放性及计算效率低下现有矩阵补全算法的可扩放性和计算效率也已成为其大规模应用的瓶颈.
针对这个问题,研究者已经进行过一些探索.
针对核范数松弛类矩阵补全算法所涉及的奇异值分解问题,普遍采用的方法是调用PROPACK软件包进行部分奇异值分解,从而有效降低奇异值分解的时间复杂度,一定程度上加速了算法收敛速度,但仍然无法适用于大规模矩阵补全问题.
为此,Teflioudi等人在文献[88]中基于MapReduce并行编程模型设计了一类适用于集群平台的并行交替最小均方算法,Recht等人在文献[75]中基于随机投影增量梯度方法设计了一类矩阵补全并行算法,Mosabbeb等人在文献[89]中基于交替方向乘子法设计了一类分布式矩阵补全并行算法并实际应用于大规模多标记分类,而Makari等人则在文献[30]中基于随机梯度下降方法设计了一类既能运行在共享存储又能运行在分布式存储平台上的并行算法.
然而,所有这些算法一方面局限于解决直传型矩阵补全问题,缺乏归纳推广性能;另一方面,基本都是基于MapReduce并行编程模型设计,仅适合运行于Hadoop平台,而且由于矩阵补全算法需要大量的迭代计算,使用MapReduce编程模型效率显得极为低下,仍然难以满足很多复杂的大数据处理需求.
4.
2未来研究方向矩阵补全技术研究方兴未艾,在模型、算法及其应用方面仍需要做很多工作.
下面分别从这几个方面对其未来研究方向进行探讨.
(1)模型方面现有的矩阵补全模型往往局限于数据表示信息的重建,重建的目的是获得最佳描述特征,未能有效利用数据的判别信息.
例如:在多标记学习任务中经常遇到基于不完全样本特征信息的多标记分类问题,对于此类问题,我们实际上并不关心补全后的样本数据和真实的样本数据是否在数据表示上完全一致,我们真正关心的是这些补全后的样本数据能否被正确分类,因此,如果在对这些样本特征信息进行预测和补全时能够融入监督或半监督的类别信息,那么将有可能提高后续分类任务的分类性能.
因此,研究如何在问题建模时融入问题的判别信息将具有很好的理论与现实意义,极有可能成为矩阵补全技术研究的新热点.
此外,矩阵补全是压缩感知从一维向量空间向二维矩阵空间的拓展,而张量补全[93]则是矩阵补全从二维矩阵空间向多维张量空间的拓展.
与压缩感知和矩阵补全技术相比,张量补全技术研究起步较晚,张量补全模型多样性的缺乏阻碍了其在实际应用中的推广,因此可以预见,张量补全技术的研究将是一个值得持续关注的热点.
(2)算法方面现有的矩阵补全算法大多属于集中式串行处理算法,受制于单机计算效率和内存空间限制,算法的扩放性和计算效率低下,难以应用于大规模问题.
对现有算法进行分布式并行扩展,应该是一种可行的解决思路.
典型的分布式并行编程模型诸如MPI,Hadoop和Spark各有其优缺点,其中,源于加州伯克利大学的Spark是近年来大数据处理平台的新锐代表.
Spark已经在批处理、流计算、机器学习、图计算、SQL查询等一系列领域得到广泛应用,并随着愈发活跃的开发者社区以及Twitter,Adobe,Intel,Amazon,Redhat等公司的加入而渐成气候.
相比于Hadoop,Spark是内存计算框架,拥有HadoopMapReduce所具有的优点;但不同于Hadoop,Job中间输出和结果可以保存在内存中,从而不再需要读写HDFS,因此尤其适用于需要多次迭代计算的矩阵补全模型求解.
而且从数值优化上看,SparkMLlib已成功实现了梯度下降、牛顿法、ADMM等经典优化算法.
因此,Spark有望成为矩阵补全分布式并行扩展的首选编程模型.
1560JournalofSoftware软件学报Vol.
28,No.
6,June2017(3)应用方面现有的矩阵补全技术虽然在诸多领域得到了广泛应用,但是大多基于一些严格的假设,实际上这些假设并不一定符合实际,因此,如何放宽矩阵补全应用中的理想假设使其更加契合问题的本源,将是值得关注的研究方向.
例如在多标记图像分类中,往往假设图像标记和图像特征之间满足线性映射关系,而实际情况是更可能满足非线性映射关系.
再如,在推荐系统的用户-评分预测中,通常假设用户偏好在某一个时间段内是一成不变的,只在跨时间段间发生变化,这种假设显然也是过于严苛的.
针对这两种理想假设的不足,最近已有学者分别提出了非线性矩阵补全[91]和动态矩阵补全模型[92],模型性能有了显著提高.
此外,矩阵补全模型的噪声容错性能也是一个影响矩阵补全应用推广的普适性问题,现有的矩阵补全模型在噪声类型先验假设的前提下取得了较好的研究成果,但是不可预知的复杂噪声背景下的矩阵补全技术研究才刚刚起步.
其中,西安交通大学徐宗本院士和孟德宇博士团队在低维子空间学习模型噪声容错性领域的研究成果为此提供了一个很好的思路,他们在ICCV2015会议上撰文指出[93]:如果采用混合指数幂分布(mixtureofexponentialpower)函数来拟合不可预知的复合噪声类型,将取得令人鼓舞的效果.
其理论依据是,混合指数幂分布函数理论上能逼近任意分布.
虽然该方法目前尚存在算法扩放性和初值敏感性问题,但其无疑为机器学习领域众多学习模型的噪声容错性问题提供了一种很好的解决思路.
5本文总结作为稀疏学习理论的重要组成部分,衍生于压缩感知的矩阵补全技术近年来在机器学习领域获得了广泛关注,短短几年,从模型、算法到应用方面均得到了快速发展,取得了诸多研究成果.
本文首先从秩函数松弛的角度综述了4类不同的矩阵补全模型,旨在为相关应用领域的矩阵补全问题建模提供参考;然后从独立于问题模型的角度综述了适用于矩阵补全模型统一框架的的常用优化算法,其目的在于从本质上加深对矩阵补全模型优化技巧的理解,从而有利于面向应用问题的矩阵补全新模型的优化求解;最后指出了现有矩阵补全模型在噪声容错性、归纳推广性和先验信息融合性方面存在的不足;同时,本文也关注到现有的矩阵补全算法大多受制于单机计算效率和内存空间限制,导致算法扩放性和计算效率低下,难以应用于大规模问题求解的问题.
可以想见,如果上述这些问题能够得到较好的解决,矩阵补全技术必将迎来更加广阔的应用前景.
References:[1]DonohoDL.
Compressedsensing.
IEEETrans.
onInformationTheory,2006,52(4):12891306.
[doi:10.
1109/TIT.
2006.
871582][2]CandesEJ,RombergJ,TaoT.
Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation.
IEEETrans.
onInformationTheory,2006,52(2):489509.
[doi:10.
1109/TIT.
2005.
862083][3]CandesEJ,RechtB.
Exactmatrixcompletionviaconvexoptimization.
FoundationsofComputationalMathematics,2009,9(6):717772.
[doi:10.
1007/s10208-009-9045-5][4]LiW,ZhaoL,LinZJ,XuDQ,LuDM.
Non-Localimageinpaintingusinglow-rankmatrixcompletion.
ComputerGraphicsForum,2015,34(6):111122.
[doi:10.
1111/cgf.
12521][5]CabralR,DelaTorreF,CosteiraJP,BernardinoA.
Matrixcompletionforweakly-supervisedmulti-labelimageclassification.
IEEETrans.
onPatternAnalysisandMachineIntelligence,2015,37(1):121135.
[doi:10.
1109/TPAMI.
2014.
2343234][6]MardaniM,GiannakisGB.
Estimatingtrafficandanomalymapsvianetworktomography.
IEEE/ACMTrans.
onNetworking,2016,24(5):15331547.
[doi:10.
1109/TNET.
2015.
2417809][7]YiKF,WanJW,YaoL,BaoTY.
Partialmatrixcompletionalgorithmforefficientdatagatheringinwirelesssensornetworks.
IEEECommunicationsLetters,2015,19(1):5457.
[doi:10.
1109/LCOMM.
2014.
2371998][8]OtazoR,CandèsE,SodicksonDK.
Low-RankplussparsematrixdecompositionforaccelerateddynamicMRIwithseparationofbackgroundanddynamiccomponents.
MagneticResonanceinMedicine,2015,73(3):11251136.
[doi:10.
1002/mrm.
25240][9]TaghizadehMJ,ParhizkarR,GarnerPN,BourlardH,AsaeiA.
Adhocmicrophonearraycalibration:Euclideandistancematrixcompletionalgorithmandtheoreticalguarantees.
SignalProcessing,2015,107:123140.
[doi:10.
1016/j.
sigpro.
2014.
07.
016][10]HsiehCJ,NatarajanN,DhilonIS.
PUlearningformatrixcompletion.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2015.
陈蕾等:矩阵补全模型及其算法研究综述1561[11]Adeli-MosabbebE,FathyM.
Non-Negativematrixcompletionforactiondetection.
ImageandVisionComputing,2015,39(1):3851.
[doi:10.
1016/j.
imavis.
2015.
04.
006][12]YiJ,ZhangL,JinR,QianQ,JainAK.
Semi-Supervisedclusteringbyinputpatternassistedpairwisesimilaritymatrixcompletion.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2013.
[13]GognA,MajumdarA.
Matrixcompletionincorporatingauxiliaryinformationforrecommendersystemdesign.
ExpertSystemwithApplications,2015,42(12):57895799.
[doi:10.
1016/j.
eswa.
2015.
04.
012][14]CandesEJ,EldarYC,StrohmerT,VladislavH.
Phaseretrievalviamatrixcompletion.
SIAMReview,2015,57(2):225251.
[doi:10.
1137/151005099][15]KumarR,SilvaCD,AkalinO,AravkinAY,MansourH;RechtB;HerrmannFJ.
Efficientmatrixcompletionforseismicdatareconstruction.
Geophysics,2015,80(5):97114.
[doi:10.
1190/geo2014-0369.
1][16]ZhaoZ,ZhangLJ,HeXF,NgW.
Expertfindingforquestionansweringviagraphregularizedmatrixcompletion,IEEETrans.
onKnowledgeandDataEngineering,2015,27(4):9931004.
[doi:10.
1109/TKDE.
2014.
2356461][17]XiaoF,ShaCH,ChenL,SunLJ,WangRC.
Noise-Tolerantlocalizationfromincompleterangemeasurementsforwirelesssensornetworks.
In:Proc.
oftheIEEEInt'lConf.
onComputerCommunications.
2015.
27942802.
[doi:10.
1109/INFOCOM.
2015.
7218672][18]ChenL,YangG,ChenZY,XiaoF,XuJ.
WebservicesQoSpredictionviamatrixcompletionwithstructuralnoise.
JournalonCommunications,2015,36(6):4959(inChinesewithEnglishabstract).
[19]ChenL,YangG,ChenZY,XiaoF,ShiJY.
CorrelationconsistencyconstrainedmatrixcompletionforWebservicetagrefinement.
NeuralComputingandApplications,2015,26(1):101110.
[doi:10.
1007/s00521-014-1704-z][20]BishopWE,YuBM.
Deterministicsymmetricpositivesemidefinitematrixcompletion.
In:Proc.
oftheAdvancesinNeuralInformationProcessingSystems.
2014.
[21]LiXD.
Compressedsensingandmatrixcompletionwithconstantproportionofcorruptions.
ConstructiveApproximation,2013,37:7399.
[doi:10.
1007/s00365-012-9176-9][22]CandesEJ,PlanY.
Matrixcompletionwithnoise.
Proc.
oftheIEEE,2010,98(6):925936.
[doi:10.
1109/JPROC.
2009.
2035722][23]MardaniM,MateosG,GiannakisGB.
Subspacelearningandimputationforstreamingbigdatamatricesandtensors.
IEEETrans.
onSignalProcessing,2015,63(10):26632677.
[doi:10.
1109/TSP.
2015.
2417491][24]WangZ,LaiJ,LuZS,YeJP.
Orthogonalrank-onematrixpursuitforlowrankmatrixcompletionSIAMJournalonScientificComputing,2015,37(1):488514.
[doi:10.
1137/130934271][25]MaS,GoldfarbD,ChenL.
FixedpointandBregmaniterativemethodsformatrixrankminimization.
MathematicsProgramming,2011,128(1):321353.
[doi:10.
1007/s10107-009-0306-5][26]XuYY,YinWT,WenZW,ZhangY.
Analternatingdirectionalgorithmformatrixcompletionwithnonnegativefactors.
FrontiersofMathematicsinChina,2012,7(2):365384.
[doi:10.
1007/s11464-012-0194-5][27]MohanK,FazelM.
Iterativereweightedalgorithmsformatrixrankminimization.
JournalofMachineLearningResearch,2013,13:32533285.
[28]MackeyL,TalwalkarA,JordanM.
Distributedmatrixcompletionandrobustfactorization.
JournalofMachineLearningResearch,2015,16(1):913960.
[29]CandesEJ,TaoT.
Thepowerofconvexrelaxation:Near-optimalmatrixcompletion.
IEEETrans.
onInformationTheory,2009,56(5):20532080.
[doi:10.
1109/TIT.
2010.
2044061][30]MakariF,TeflioudiC,GemullaR,HaasP,SismanisY.
Shared-Memoryandshared-nothingstochasticgradientdescentalgorithmsformatrixcompletion.
KnowledgeandInformationSystems,2015,42(3):493523.
[doi:10.
1007/s10115-013-0718-7][31]NieFP,WangH,HuangH,DingC.
Jointschattenp-normandLp-normroubstmatrixcompletionformissingvaluerecovery.
KnowledgeandInformationSystems,2015,42(3):525544.
[doi:10.
1007/s10115-013-0713-z][32]LuCY,TangJH,YanSC,LinZ.
Generalizednonconvexnon-smoothlow-rankminimization.
In:Proc.
oftheIEEEConf.
onComputerVisionandPatternRecognition.
2014.
41304137.
[doi:10.
1109/CVPR.
2014.
526][33]ZhangLJ,YangT,JinR,ZhouZH.
Stochasticproximalgradientdescentfornuclearnormregularization.
2015.
http://arxiv.
org/abs/1511.
01664CoRRabs/1511.
016641562JournalofSoftware软件学报Vol.
28,No.
6,June2017[34]BoumalN,AbsilP.
RTRMC:Ariemanniantrustregionmethodformatrixcompletion.
In:Proc.
oftheAnnualConf.
onNeuralInformationProcessingSystems.
2011.
[35]GhasemiH,Malek-MohammadiM,Babaie-ZadehM.
SRF:Matrixcompletionbasedonsmoothedrankfunction.
In:Proc.
oftheIEEEInt'lConf.
onAcoustics,SpeechandSignalProcessing.
2011.
36723675.
[doi:10.
1109/ICASSP.
2011.
5947147][36]WinlawM,HynesM,CateriniA,SterckH.
AlgorithmicaccelerationofparallelALSforcollaborativefiltering;speedingupdistributedbigdatarecommendationinSpark.
In:Proc.
oftheIEEEInt'lConf.
onParallelandDistributedSystems.
2015.
682691.
[doi:10.
1109/ICPADS.
2015.
91][37]SunRY,LuoZQ.
Guaranteedmatrixcompletionvianon-convexfactorization.
In:Proc.
oftheAnnualSymp.
onFoundationsofComputerScience.
2015.
[doi:10.
1109/FOCS.
2015.
25][38]LinZC.
Rankminimization:Theory,algorithmsandapplications.
In:ZhangCS,ZhouZH,eds.
Proc.
oftheMachineLearningandTheirApplications.
Beijing:TsinghuaUniversityPress,2013.
143164(inChinesewithEnglishabstract).
[39]PengYG,SuoJL,DaiQH,XuLW.
Fromcompressedsensingtolow-rankmatrixrecovery:Theoryandaplications.
ActaActomaticaSinica,2013,39(7):981994(inChinesewithEnglishabstract).
[doi:10.
1016/S1874-1029(13)60063-4][40]ChenCH,HeBS,YuanXM.
Matrixcompletionviaanalternatingdirectionmethod.
IMAJournalofNumericalAnalysis,2012,32(1):227245.
[doi:10.
1093/imanum/drq039][41]WenSW,XuFF,WenZW,ChenL.
Robustlinearoptimizationundermatrixcompletion.
ScienceinChina:Mathematics,2014,57:699710.
[doi:10.
1007/s11425-013-4697-7][42]JiaoLC,ZhaoJ,YangSY,LiuF,XieW.
Researchadvancesonsparsecognitivelearning,computingandrecognition.
ChineseJournalofComputers,2016,39(4):835852(inChinesewithEnglishabstract).
[43]HuY,ZhangDB,YeJP,LiX,HeXF.
Fastandaccuratematrixcompletionviatruncatednuclearnormregularization.
IEEETrans.
onPatternAnalysisandMachineIntelligence,2013,35(9):21172130.
[doi:10.
1109/TPAMI.
2012.
271][44]ChenL,YangG,ChenZY,XiaoF,ChenSC.
Linearizedbregmaniterationalgorithmformatrixcompletionwithstructuralnoise.
ChineseJournalofComputers,2015,38(7):13571371(inChinesewithEnglishabstract).
[45]TibshiraniR.
Regressionshrinkageandselectionviathelasso.
JournaloftheRoyalStatisticalSociety,1996,58(1):267288.
[46]FazelM.
Matrixrankminimizationwithapplications[Ph.
D.
Thesis].
StandfordUniversity,2002.
[47]TohKC,YunSW.
Anacceleratedproximalgradientalgorithmfornuclearnormregularizedleastsquaresproblems.
PacificJournalofOptimization,2010,6(3):615640.
[48]CaiJF,CandesEJ,ShenZ.
Asingularvaluethresholdingalgorithmformatrixcompletion,SIAMJournalofOptimization,2010,20(4):19561982.
[doi:10.
1137/080738970][49]LinZC,ChenMM,WuLQ,MaY.
TheaugmentedLagrangemultipliermethodforexactrecoveryofcorruptedlow-rankmatrices.
TechnicalReport,UILU-ENG-09-2214,UIUCUniversity,2010.
[50]WenZW,YinWT,ZhangY.
Solvingalowrankfactorizationmodelformatrixcompletionbyanonlinearsuccessiveover-relaxationalgorithm.
MathematicProgrammingComputation.
2012,4:333361.
[doi:10.
1007/s12532-012-0044-1][51]LiuYY,JiaoLC,ShangFH.
Afasttri-factorizationmethodforlow-rankmatrixrecoveryandcompletion.
PatternRecognition,2013,46(1):163173.
[doi:10.
1016/j.
patcog.
2012.
07.
003][52]SrebroN,ShraibmanA.
Rank,trace-normandmax-norm.
In:Proc.
oftheAnnualConf.
onLearningTheory.
2005.
545560.
[doi:10.
1007/11503415_37][53]MardaniM,MateosG,GiannakisGB.
Rankminimizationforsubspacetrackingfromincompletedata.
In:Proc.
oftheIEEEInt'lConf.
onAcoustics,SpeechandSignalProcessing.
2013.
56815685.
[doi:10.
1109/ICASSP.
2013.
6638752][54]GengJ,WangLS,WangYF.
Anon-convexalgorithmframeworkbasedonDCprogrammingandDCAformatrixcompletion.
NumericalAlgorithms,2015,68:903921.
[doi:10.
1007/s11075-014-9876-2][55]KangZ,PengC,ChengJ,ChengQ.
LogDetrankminimizationwithapplicationtosubspaceclustering.
ComputationalIntelligenceandNeuroscience,2015,ArticleID824289.
[doi:10.
1155/2015/824289][56]HonerkampJ,WeeseJ.
Tikhonovsregularizationmethodforill-posedproblems.
ContinuumMechanicsandThermodynamics,1990,2(1):1730.
[doi:10.
1007/BF01170953]陈蕾等:矩阵补全模型及其算法研究综述1563[57]ChenZ,HaykinS.
Ondifferentfacetsofregularizationtheory.
NeuralComputation,2002,14(12):27912846.
[doi:10.
1162/089976602760805296][58]CombettesPL,WajsVR.
Signalrecoverybyproximalforward-backwardsplitting.
MultiscaleModelingandSimulation,2005,4(4):11681200.
[doi:10.
1137/050626090][59]NemirovskiA.
Efficientmethodsinconvexprogramming.
LectureNotes,1995,23(3):2439.
[60]BeckA,TeboulleM.
Afastiterativeshrinkage-thresholdingalgorithmforlinearinverseproblems.
SIAMJournalonImagingSciences,2009,2(1):183202.
[doi:10.
1137/080716542][61]NesterovY.
AmethodofsolvingaconvexprogrammingproblemwithconvergencerateO(k2).
SovietMathematicsDoklady,1983,27(2):372376.
[62]NesterovY.
Efficiencyofcoordinatedescentmethodsonhuge-scaleoptimizationproblems.
SIAMJournalonOptimization,2012,22:341362.
[doi:10.
1137/100802001][63]BeckA,TetruashviliL.
Ontheconvergenceofblockcoordinatedescentmethods.
SIAMJournalonOptimization,2013,23(4):20372060.
[doi:10.
1137/120887679][64]BregmanL.
Therelaxationmethodoffindingthecommonpointsofconvexsetsanditsapplicationtothesolutionofproblemsinconvexprogramming.
ComputationalMathematicsandMathematicalPhysics,1967,7(3):200217.
[doi:10.
1016/0041-5553(67)90040-7][65]OsherS,BurgerM,GoldfarbM.
Aniterativeregularizationmethodfortotalvariation-basedimagerestoration.
MultiscaleModelingandSimulation,2005,4(2):460489.
[doi:10.
1137/040605412][66]YinWT,OsherS,GoldfarbD.
BregmaniterativealgorithmsforL1-minimizationwithapplicationstocompressedsensing.
SIAMJournalonImagingSciences,2008,1(1):143168.
[doi:10.
1137/070703983][67]CaiJF,OsherS,ShenZ.
LinearizedBregmaniterationforframe-basedimagedeblurring.
SIAMJournalonImagingSciences,2009,2(2):226252.
[doi:10.
1137/080733371][68]BoydS,ParikhN,ChuE.
Distributedoptimizationandstatisticallearningviathealternatingdirectionmethodofmultipliers.
FoundationsandTrendsinMachineLearning,2011,3(1):1122.
[doi:10.
1561/2200000016][69]DouglasJ,RachfordHH.
Onthenumericalsolutionofheatconductionproblemsintwoandthreespacevariables.
Trans.
oftheAmericanMathematicalSociety,1956,82:421439.
[doi:10.
1090/S0002-9947-1956-0084194-4][70]GabayD,MercierB.
Adualalgorithmforthesolutionofnonlinearvariationalproblemsviafiniteelementapproximations.
ComputersandMathematicswithApplications,1976,2:1740.
[doi:10.
1016/0898-1221(76)90003-1][71]ZhangRL,KwokJ.
AsynchronousdistributedADMMforconsensusoptimization.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2014.
[72]ZhangWL,KwokJ.
Faststochasticalternatingdirectionmethodofmultipliers.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2014.
[73]HeBS,YuanXM.
OntheO(1/n)convergencerateoftheDouglas-Rachfordalternatingdirectionmethod.
SIAMJournalofNumericalAnalysis.
2012,50(2):700709.
[doi:10.
1137/110836936][74]HeBS,TaoM,YuanXM.
AlternatingdirectionmethodwithGaussianbacksubstitutionforseparableconvexprogramming.
SIAMJournalonOptimization,2012,22(2):313340.
[doi:10.
1137/110822347][75]LinZC,LiuRS,LiH.
Linearizedalternatingdirectionmethodwithparallelsplittingandadaptivepenaltyforseparableconvexprogramsinmachinelearning.
MachineLearning,2015,99(2):287325.
[doi:10.
1007/s10994-014-5469-5][76]NemirovskiA,JuditskyA,LanG,ShapiroA.
Robuststochasticapproximationapproachtostochasticprogramming.
SIAMJournalonOptimization,2009,19(4):15741609.
[doi:10.
1137/070704277][77]RechtB,ReC.
Parallelstochasticgradientalgorithmsforlarge-scalematrixcompletion.
MathematicalProgrammingComputation,2013,5(2):201226.
[doi:10.
1007/s12532-013-0053-8][78]LiuJ,WrightSJ,ReC,BittorfV,SridharS.
Anasynchronousparallelstochasticcoordinatedescentalgorithm.
JournalofMachineLearningResearch,2015,16(1):285322.
[79]AzadiS,SraS.
Towardsanoptimalstochasticalternatingdirectionmethodofmultipliers.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2014.
1564JournalofSoftware软件学报Vol.
28,No.
6,June2017[80]ZhangLJ,YangT,YiJ,JinR,ZhouZH.
StochasticoptimizationforkernelPCA.
In:Proc.
oftheAAAIConf.
onArtificialIntelligence.
2016.
23162322.
[81]ZhangZH.
Thesingularvaluedecomposition,applicationsandbeyond.
arXiv:1510.
08532v1,http://arxiv.
org/abs/1510.
08532[82]TaoM,HeBS,YuanXM.
Recoveringlow-rankandsparsecomponentsofmatricesfromincompleteandnoisyobservations.
SIAMJournalonOptimization,2011,21(1):5781.
[doi:10.
1137/100781894][83]YanM,YangY,OsherS.
Exactlow-rankmatrixcompletionfromsparselycorruptedentriesviaadaptiveoutlierpursuit.
JournalofScientificComputing,2013,56(3):433449.
[doi:10.
1007/s10915-013-9682-3][84]ChenYD,JalaliA,SanghaviS,CaramanisC.
Low-Rankmatrixrecoveryfromerrorsanderasures.
IEEETrans.
onInformationTheory,2013,59(7):43244337.
[doi:10.
1109/TIT.
2013.
2249572][85]ChenYD,XuH,CaramanisC,SanghaviS.
Robustmatrixcompletionandcorruptedcolumns.
In:Proc.
oftheInt'lConf.
onMachineLearning.
2011.
[86]XuM,JinR,ZhouZH.
Speedupmatrixcompletionwithsideinformation:Applicationtomulti-labellearning.
In:Proc.
oftheAdvancesinNeuralInformationProcessingSystems.
2013.
[87]NatarajanN,DhillonIS.
Matrixcompletionforpredictinggene-diseaseassociations.
Bioinformatics,2014,30(12):6068.
[doi:10.
1093/bioinformatics/btu269][88]TeflioudiC,MakariF,GemullaR.
Distributedmatrixcompletion.
In:Proc.
oftheIEEEInt'lConf.
onDataMining.
2012.
655664.
[doi:10.
1109/ICDM.
2012.
120][89]MosabbebEA,FathyM.
Distributedmatrixcompletionforlarge-scalemulti-labelclassification.
IntelligentDataAnalysis,2014,18:11371151.
[90]LiuJ,MusialskiP,WonkaP,YeJP.
Tensorcompletionforestimatingmissingvaluesinvisualdata.
IEEETrans.
onPatternAnalysisandMachineIntelligence,2013,35(1):208220.
[doi:10.
1109/TPAMI.
2012.
39][91]Alameda-PinedaX,YanY,RicciE,SebeN.
Recognizingemotionsfromabstractpaintingsusingnon-linearmatrixcompletion.
In:Proc.
oftheIEEEConf.
onComputerVisionandPatternRecognition.
2016.
52405248.
[doi:10.
1109/CVPR.
2016.
566][92]XuLB,DavenportMA.
Dynamicmatrixrecoveryfromincompleteobservationsunderanexactlow-rankconstraint.
In:Proc.
oftheAdvancesinNeuralInformationProcessingSystems.
2016.
[93]CaoXR,ChenY,ZhaoQ,MengDY,WangY,WangD,XuZB.
Low-Rankmatrixfactorizationundergeneralmixturenoisedistributions.
In:Proc.
oftheInt'lConf.
onComputerVision.
2015.
[doi:10.
1109/ICCV.
2015.
175]附中文参考文献:[18]陈蕾,杨庚,陈正宇,肖甫,许建.
基于结构化噪声矩阵补全的Web服务QoS预测.
通信学报,2015,36(6):4959.
[38]林宙辰.
秩极小化:理论、算法与应用.
见:张长水,周志华,编.
机器学习及其应用会议论文集.
北京:清华大学出版社,2013.
143164.
[39]彭义刚,索津莉,戴琼海,徐文立.
从压缩传感到低秩矩阵恢复:理论与应用.
自动化学报,2013,39(7):981994.
[doi:10.
1016/S1874-1029(13)60063-4][42]焦李成,赵进,杨淑媛,刘芳,谢雯.
稀疏认知学习、计算与识别的研究进展.
计算机学报,2016,39(4):835852.
[44]陈蕾,杨庚,陈正宇,肖甫,陈松灿.
基于线性Bregman迭代的结构化噪声矩阵补全算法.
计算机学报,2015,38(7):13571371.
陈蕾(1975-),男,江西宜春人,博士,副教授,CCF专业会员,主要研究领域为大规模机器学习,计算机视觉,基于医学影像的脑疾病诊断.
陈松灿(1962-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为模式识别,机器学习.