一种改进的求解矩阵补全问题的原始-对偶算法  

A Modified Primal-dual Algorithm for Matrix Completion Problems

作　　者：闫喜红[1] 张宁 YAN XIHONG;ZHANG NING(College of Mathematics and Statistics,Taiyuan Normal University,Shanci Key Laboratory for Intelligent Optimization Computing and Blockchain Technology,Jinzhong 030619,China)

机构地区：[1]太原师范学院数学与统计学院,智能优化计算与区块链技术山西省重点实验室,晋中030619

出　　处：《应用数学学报》2024年第2期175-192,共18页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(批准号:12371381);山西省科技创新人才团队专项(批准号:202204051002018);山西省回国留学人员科研教研(批准号:2022-170)资助项目。

摘　　要：低秩矩阵补全问题作为一类在机器学习和图像处理等信息科学领域中都十分重要的问题已被广泛研究.一阶原始-对偶算法是求解该问题的经典算法之一.然而实际应用中处理的数据往往是大规模的.针对大规模矩阵补全问题,本文在原始-对偶算法的框架下,应用变步长校正技术,提出了一种改进的求解矩阵补全问题的原始-对偶算法.该算法在每一步迭代过程中,首先利用原始-对偶算法对原始变量和对偶变量进行更新,然后采用变步长校正技术对这两块变量进行进一步的校正更新.在一定的假设条件下,证明了新算法的全局收敛性.最后通过求解随机低秩矩阵补全问题及图像修复的实例验证新算法的有效性.As an important problem in the field of information science such as machine learning and image processing,low rank matrix completion has been widely studied.The first-order primal-dual algorithm is one of the classical algorithms for solving this problem.However,the data processed in practical applications is often large-scale.Therefore,based on the framework of the primal-dual algorithm,this paper proposes a modified primal-dual algorithm for large-scale matrix completion problems by exploring correction strategy with the variable step size.In each iteration of the new algorithm,the primal and dual variables are firstly updated by the primal-dual algorithm,and then the correction strategy with the variable step size is used to further correct the two variables.Under certain assumptions,the global convergence of the new algorithm is proved.Finally,the new algorithm is verified to be efficient by solving some random low rank matrix completion problems and examples of image restoration.

关 键 词：一阶原始-对偶算法 低秩矩阵补全 收敛性 变步长 校正技术 

分 类 号：O221.2[理学—运筹学与控制论]