文章基本信息

标题：Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
本地全文：下载
作者：Wen, Zaiwen ; Yin, W. ; Zhang, Y. 等
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2012
页码：333-361
DOI：10.1007/mpc.v0i0.96
语种：English
出版社：Mathematical Programming Computation
摘要：Thematrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclearnorm minimization which requires computing singular value decompositions—a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.
关键词：65K05; 90C06; 93C41; 68Q32