Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

Zaiwen Wen Wotao Yin Yin Zhang

Numerical Analysis and Scientific Computing mathscidoc:1912.43771

Mathematical Programming Computation, 4, (4), 333-361, 2012
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 decompositionsa 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.
No keywords uploaded!
[ Download ] [ 2019-12-24 20:57:03 uploaded by Wotao_Yin ] [ 505 downloads ] [ 0 comments ]
@inproceedings{zaiwen2012solving,
  title={Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm},
  author={Zaiwen Wen, Wotao Yin, and Yin Zhang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191224205703763762335},
  booktitle={Mathematical Programming Computation},
  volume={4},
  number={4},
  pages={333-361},
  year={2012},
}
Zaiwen Wen, Wotao Yin, and Yin Zhang. Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. 2012. Vol. 4. In Mathematical Programming Computation. pp.333-361. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191224205703763762335.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved