  We study alternating minimization for matrix completion in the simplest
possible setting: completing a rank-one matrix from a revealed subset of the
entries. We bound the asymptotic convergence rate by the variational
characterization of eigenvalues of a reversible consensus problem. This leads
to a polynomial upper bound on the asymptotic rate in terms of number of nodes
as well as the largest degree of the graph of revealed entries.
