  In this paper, we develop a relative error bound for nuclear norm regularized
matrix completion, with the focus on the completion of full-rank matrices.
Under the assumption that the top eigenspaces of the target matrix are
incoherent, we derive a relative upper bound for recovering the best low-rank
approximation of the unknown matrix. Although multiple works have been devoted
to analyzing the recovery error of full-rank matrix completion, their error
bounds are usually additive, making it impossible to obtain the perfect
recovery case and more generally difficult to leverage the skewed distribution
of eigenvalues. Our analysis is built upon the optimality condition of the
regularized formulation and existing guarantees for low-rank matrix completion.
To the best of our knowledge, this is the first relative bound that has been
proved for the regularized formulation of matrix completion.
