Optimization Online


An Alternating Minimization Method for Matrix Completion Problem

Yuan Shen(ocsiban***at***126.com)
Xin Liu(liuxin***at***lsec.cc.ac.cn)

Abstract: 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.

Keywords: matrix completion, alternating minimization, SVD, local optimality, symmetric low-rank product

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Tech report 1801, Nanjing University of Finance & Economics, 01/2018

Download: [PDF]

Entry Submitted: 01/30/2018
Entry Accepted: 01/30/2018
Entry Last Modified: 01/30/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society