  


Solving A LowRank Factorization Model for Matrix Completion by A Nonlinear Successive OverRelaxation Algorithm
Zaiwen Wen(zw2109columbia.edu) Abstract: The matrix completion problem is to recover a lowrank 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 largescale problems, we propose a lowrank factorization model and construct a nonlinear successive overrelaxation (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 nuclearnorm 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 LowRank Factorization Model for Matrix Completion by A Nonlinear Successive OverRelaxation Algorithm}, institution = {Rice University}, year = {2010}, note = {CAAM Technical Report TR1007} } Download: [PDF] Entry Submitted: 03/26/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  