  Matrix completion aims to recover an unknown low-rank matrix from a small
subset of its entries. In many applications, the rank of the unknown target
matrix is known in advance. In this paper, first we revisit a recently proposed
rank-based heuristic for "known-rank" matrix completion and establish a
condition under which the generated sequence is quasi-Fej\'er convergent to the
solution set. Then, by including an acceleration mechanism similar to
Nesterov's acceleration, we obtain a new heuristic. Even though the convergence
of such heuristic cannot be granted in general, it turns out that it can be
very useful as a warm-start phase, providing a suitable estimate for the
regularization parameter and a good starting-point, to an accelerated
Soft-Impute algorithm. Numerical experiments with both synthetic and real data
show that the resulting two-phase rank-based algorithm can recover low-rank
matrices, with relatively high precision, faster than other well-established
matrix completion algorithms.
