矩阵补全算法研究进展.pdf

《矩阵补全算法研究进展.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第41卷第4期计算机科学Vo1．4lNo．42014年4月ComputerScienceApr2014矩阵补全算法研究进展史加荣郑秀云周水生。(西安建筑科技大学理学院西安710055)(西安电子科技大学数学与统计学院西安710071)摘要作为压缩感知理论的重要发展，矩阵补全与恢复已成为信号与图像处理的一种新的强有力的工具。综述了矩阵补全算法的最新研究进展。首先分析了核范数最小化模型的几种主要的矩阵补全算法，并对这些算法的迭代过程及原理进行了详细的阐述。其次讨论了矩阵补全的低秩矩阵分解模型，并列出了近年来出现的求解此模型的新算法。然后补充了上述两种模型的衍生版本，指出了相

2、应的求解方法。在数值实验中，对文中所讨论的主要矩阵补全算法的性能进行了比较。最后给出了矩阵补全算法的未来研究方向及重点。关键词矩阵补全，低秩，核范数最小化，低秩矩阵分解，压缩感知，低秩矩阵恢复中图法分类号TP391文献标识码AResearchProgressinMatrixCompletionAlgorithmsSHIJia-rongZHENGXiu—yunZHOUShui-shengz(SehoolofScience，Xi’anUniversityofArchitectureandTechnology，Xi’an710055，China)(SchoolofMathem

3、aticsandStatistics，XidianUniversity，Xi’an710071，China)AbstractAsanimportantdevelopmentofcompressedsensingtheory，matrixcompletionandrecoveryhasbeenanewandremarkabletechniqueforsignalandimageprocessing．Thispapermadeasurveyonthelatestresearchprogressinmatrixcompletionalgorithms．Firstly，itan

4、alyzedseveralmainalgorithmstonuclearnormminimizationmodel，andelabo-ratedtheiriterativeprocedureandprinciple．Secondly，itdiscussedlow-rankmatrixfactorizationmodelofmatrixcorn-pletionandlistedthecorrespondingnewalgorithmsemergedinrecentyears．Thenitcomplementedotherversionsde—rivedfromtheabo

5、vetwomodelsandpointedoutthesolvingmethods．Innumericalexperiments，performancecompari—sonsweremadeonthemainalgorithmstomatrixcompletion．Finally，itgavefutureresearchdirectionandfocusforma—trixcompletionalgorithms．KeywordsMatrixcompletion，Low-rank，Nuclearnormminimization，Low-rankmatrixfactor

6、ization，Compressedsen-sing，Low-rankmatrixrecovery矩阵补全广泛地应用在计算机视觉_6]、机器学习[10,II]、1引言推荐系统_12_和系统辨识口H]等诸多科学与工程领域中。作一般来说，不能根据信号的部分采样元素来恢复所有元为信号与图像处理技术的一个强大的新兴分支，矩阵补全已素。但信号在一组基下是稀疏的且满足一定条件时，压缩感成为继压缩感知之后的又一种重要的信号获取工具。在数学知理论(CompressedSensing／CompressedSampling，CS)证实形式上，矩阵补全可描述为一个仿射秩最小化问题，但此问题了

7、可以通过求解l最小化问题来精确地恢复所有元素[1。]。是NP难的。近年来涌现出了许多求解秩最小化问题的启发当信号用矩阵形式表示时，同样一般不能根据它的部分元素式方法，这些方法主要分为两类：一类是将秩函数凸松弛到矩来恢复所有丢失元素。Cand6s和陶哲轩等人证明了当矩阵阵核范数，建立核范数优化模型；另一类是事先给定矩阵的的奇异值具有稀疏性(即矩阵是低秩的)且采样数目满足一定秩，建立低秩分解模型。条件时，大多数矩阵可以通过求解核范数最小化问题来精确与向量的Z范数类似，矩阵的核范数也是一个连续的、地恢复所有元素¨3]。由矩阵的部分元素来恢复所有