  We study deterministic matrix completion problem, i.e., recovering a low-rank
matrix from a few observed entries where the sampling set is chosen as the edge
set of a Ramanujan graph. We first investigate projected gradient descent (PGD)
applied to a Burer-Monteiro least-squares problem and show that it converges
linearly to the incoherent ground-truth with respect to the condition number
\k{appa} of ground-truth under a benign initialization and large samples. We
next apply the scaled variant of PGD to deal with the ill-conditioned case when
\k{appa} is large, and we show the algorithm converges at a linear rate
independent of the condition number \k{appa} under similar conditions. Finally,
we provide numerical experiments to corroborate our results.
