In this paper, we focus on solving matrix completion problem arising from applications in the fields of information theory, statistics, engineering, etc. However, the matrix completion problem involves nonconvex rank constraints which make this type of problem difficult to handle. Traditional approaches use a nuclear norm surrogate to replace the rank constraints. The relaxed model is convex, and hence can be solved by a bunch of existing algorithms. However, these algorithms need to compute the costly singular value decomposition (SVD) which makes them impractical for handling large-scale problems. We retain the rank constraints in the optimization model, and propose an alternating minimization method for solving it. The resulting algorithm does not need SVD computation, and shows satisfactory speed performance. As a nonconvex algorithm, the new algorithm has better theoretical property than competing algorithms.
Citation
Tech report 1801, Nanjing University of Finance & Economics, 01/2018
Article
View An Alternating Minimization Method for Matrix Completion Problem