  This paper studies the problem of deterministic rank-one matrix completion.
It is known that the simplest semidefinite programming relaxation, involving
minimization of the nuclear norm, does not in general return the solution for
this problem. In this paper, we show that in every instance where the problem
has a unique solution, one can provably recover the original matrix through two
rounds of semidefinite programming relaxation with minimization of the trace
norm. We further show that the solution of the proposed semidefinite program is
Lipschitz-stable with respect to perturbations of the observed entries, unlike
more basic algorithms such as nonlinear propagation or ridge regression. Our
proof is based on recursively building a certificate of optimality
corresponding to a dual sum-of-squares (SOS) polynomial. This SOS polynomial is
built from the polynomial ideal generated by the completion constraints and the
monomials provided by the minimization of the trace. The proposed relaxation
fits in the framework of the Lasserre hierarchy, albeit with the key addition
of the trace objective function. We further show how to represent and
manipulate the moment tensor in favorable complexity by means of a hierarchical
low-rank decomposition.
