Matrix Completion via Nonconvex Regularization: Convergence of the
  Proximal Gradient Algorithm
  Matrix completion has attracted much interest in the past decade in machine
learning and computer vision. For low-rank promotion in matrix completion, the
nuclear norm penalty is convenient due to its convexity but has a bias problem.
Recently, various algorithms using nonconvex penalties have been proposed,
among which the proximal gradient descent (PGD) algorithm is one of the most
efficient and effective. For the nonconvex PGD algorithm, whether it converges
to a local minimizer and its convergence rate are still unclear. This work
provides a nontrivial analysis on the PGD algorithm in the nonconvex case.
Besides the convergence to a stationary point for a generalized nonconvex
penalty, we provide more deep analysis on a popular and important class of
nonconvex penalties which have discontinuous thresholding functions. For such
penalties, we establish the finite rank convergence, convergence to restricted
strictly local minimizer and eventually linear convergence rate of the PGD
algorithm. Meanwhile, convergence to a local minimizer has been proved for the
hard-thresholding penalty. Our result is the first shows that, nonconvex
regularized matrix completion only has restricted strictly local minimizers,
and the PGD algorithm can converge to such minimizers with eventually linear
rate under certain conditions. Illustration of the PGD algorithm via
experiments has also been provided. Code is available at
https://github.com/FWen/nmc.
