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

被引：595

作者：

Wen, Zaiwen ^{[1
]}

Yin, Wotao ^{[2
]}

Zhang, Yin ^{[2
]}

机构：

[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卷 / 04期

基金：

美国国家科学基金会; 中国国家自然科学基金;

关键词：

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)

← 1 2 3 4 5 →