  We propose an iterative algorithm for low-rank matrix completion that can be
interpreted as an iteratively reweighted least squares (IRLS) algorithm, a
saddle-escaping smoothing Newton method or a variable metric proximal gradient
method applied to a non-convex rank surrogate. It combines the favorable
data-efficiency of previous IRLS approaches with an improved scalability by
several orders of magnitude. We establish the first local convergence guarantee
from a minimal number of samples for that class of algorithms, showing that the
method attains a local quadratic convergence rate. Furthermore, we show that
the linear systems to be solved are well-conditioned even for very
ill-conditioned ground truth matrices. We provide extensive experiments,
indicating that unlike many state-of-the-art approaches, our method is able to
complete very ill-conditioned matrices with a condition number of up to
$10^{10}$ from few samples, while being competitive in its scalability.
