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

被引：578
作者：
Zaiwen Wen
Wotao Yin
Yin Zhang
机构：
[1] Department of Mathematics and Institute of Natural Sciences, Shanghai Jiaotong University, Shanghai
[2] Department of Computational and Applied Mathematics, Rice University, Houston, TX
来源：
Mathematical Programming Computation | 2012年 / 4卷 / 4期
基金：
美国国家科学基金会; 中国国家自然科学基金;
关键词：
Alternating minimization; Matrix completion; Nonlinear GS method; Nonlinear SOR method;
D O I：
10.1007/s12532-012-0044-1
中图分类号：
学科分类号：
摘要：
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. © 2012 Springer and Mathematical Optimization Society.
引用
收藏
页码：333 / 361
页数：28
相关论文
共 42 条
  • [1] Beck A., Teboulle M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, pp. 183-202, (2009)
  • [2] Candes E., Plan Y., Matrix completion with noise, Proc. IEEE, 98, pp. 925-936, (2010)
  • [3] Candes E.J., Recht B., Exact matrix completion via convex optimization, Found. Comput. Math., (2009)
  • [4] Candes E.J., Tao T., The power of convex relaxation near-optimal matrix completion, IEEE Trans. Inf. Theory, 56, pp. 2053-2080, (2010)
  • [5] Chan T.F., Rank revealing QR factorizations, Linear Algebra Appl., 88, 89, pp. 67-82, (1987)
  • [6] Chan T.F., Hansen P.C., Low-rank revealing QR factorizations, Numer. Linear Algebra Appl., 1, pp. 33-44, (1994)
  • [7] Dai W., Milenkovic O., Set an algorithm for consistent matrix completion CoRR, (2009)
  • [8] Elden L., Matrix Methods in Data Mining and Pattern Recognition (Fundamentals of Algorithms), (2007)
  • [9] Goldberg K., Roeder T., Gupta D., Perkins C., Eigentaste A constant time collaborative filtering algorithm, Inf. Retr., 4, pp. 133-151, (2001)
  • [10] Goldfarb D., Ma S., Wen Z., Solving low-rank matrix completion problems efficiently, Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, pp. 1013-1020, (2009)
12345