Title | ||
---|---|---|
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. |
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. 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s12532-012-0044-1 | Math. Program. Comput. |
Keywords | Field | DocType |
Matrix completion, Alternating minimization, Nonlinear GS method, Nonlinear SOR method | Discrete mathematics,Mathematical optimization,Rank factorization,Singular value,Nonlinear system,Matrix completion,Matrix (mathematics),Algorithm,Factorization,Successive over-relaxation,Linear least squares,Mathematics | Journal |
Volume | Issue | ISSN |
4 | 4 | 18672957 |
Citations | PageRank | References |
210 | 5.13 | 21 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zaiwen Wen | 1 | 934 | 40.20 |
Wotao Yin | 2 | 5038 | 243.92 |
Yin Zhang | 3 | 1214 | 52.33 |