An SOR Algorithm for Matrix Completion
主 题: An SOR Algorithm for Matrix Completion
报告人: Prof. Yin Zhang (Rice University)
时 间: 2014-06-04 14:00-15:00
地 点: 镜春园82号院甲乙丙楼82J12教室（主持人：文再文）
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 nuclear-norm 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.
