Solving A Low-Rank Factorization Model for Matrix Completion by A Nonlinear Successive Over-Relaxation Algorithm

Zaiwen Wen(zw2109columbia.edu)
Wotao Yin(wotao.yinrice.edu)
Yin Zhang(yzhangrice.edu)

Abstract: 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. Convergence of this nonlinear SOR algorithm is analyzed. Numerical results 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.

Keywords: Matrix Completion, alternating minimization, nonlinear GS method, nonlinear SOR method

Category 1: Nonlinear Optimization

Category 2: Applications -- Science and Engineering

Citation: @TECHREPORT{LMaFit:report, author = {Wen, Zaiwen and Yin, Wotao and Zhang, Yin}, title = {Solving A Low-Rank Factorization Model for Matrix Completion by A Nonlinear Successive Over-Relaxation Algorithm}, institution = {Rice University}, year = {2010}, note = {CAAM Technical Report TR10-07} }

Download: [PDF]

Entry Submitted: 03/26/2010
Entry Accepted: 03/26/2010
Entry Last Modified: 03/26/2010

Modify/Update this entry