  We consider the problem of reconstructing a low rank matrix from a subset of
its entries and analyze two variants of the so-called Alternating Minimization
algorithm, which has been proposed in the past. We establish that when the
underlying matrix has rank $r=1$, has positive bounded entries, and the graph
$\mathcal{G}$ underlying the revealed entries has bounded degree and diameter
which is at most logarithmic in the size of the matrix, both algorithms succeed
in reconstructing the matrix approximately in polynomial time starting from an
arbitrary initialization. We further provide simulation results which suggest
that the second algorithm which is based on the message passing type updates,
performs significantly better.
