Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
复制标题
通过非线性连续过松弛算法求解矩阵补全的低阶分解模型
DOI：
10.1007/s12532-012-0044-1
复制
发表时间：
2012-12-01
影响因子：
6.3
通讯作者：
Zhang, Yin
中科院分区：
文献类型：
--
作者：
Wen, Zaiwen;Yin, Wotao;Zhang, Yin
矩阵完备化问题是从一个低秩矩阵的元素子集中恢复一个低秩矩阵。这个问题的主要解决方案策略是基于核范数最小化，这需要计算奇异值分解的任务，是越来越昂贵的矩阵大小和秩的增加。为了提高求解大规模问题的能力，提出了一种低秩分解模型，并构造了一种非线性逐次超松弛（SOR）算法，每次迭代只需求解一个线性最小二乘问题.大量的数值实验表明，该算法可以可靠地解决广泛的问题，至少比许多核范数最小化算法的速度快几倍。此外，这种非线性SOR算法收敛到一个稳定点进行了分析。
The matrix 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.