  In this paper, we study the popularly dubbed matrix completion problem, where
the task is to "fill in" the unobserved entries of a matrix from a small subset
of observed entries, under the assumption that the underlying matrix is of
low-rank. Our contributions herein, enhance our prior work on nuclear norm
regularized problems for matrix completion (Mazumder et al., 2010) by
incorporating a continuum of nonconvex penalty functions between the convex
nuclear norm and nonconvex rank functions. Inspired by SOFT-IMPUTE (Mazumder et
al., 2010; Hastie et al., 2016), we propose NC-IMPUTE- an EM-flavored
algorithmic framework for computing a family of nonconvex penalized matrix
completion problems with warm-starts. We present a systematic study of the
associated spectral thresholding operators, which play an important role in the
overall algorithm. We study convergence properties of the algorithm. Using
structured low-rank SVD computations, we demonstrate the computational
scalability of our proposal for problems up to the Netflix size (approximately,
a $500,000 \times 20, 000$ matrix with $10^8$ observed entries). We demonstrate
that on a wide range of synthetic and real data instances, our proposed
nonconvex regularization framework leads to low-rank solutions with better
predictive performance when compared to those obtained from nuclear norm
problems. Implementations of algorithms proposed herein, written in the R
programming language, are made available on github.
