Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion
This provides theoretical guarantees for a fundamental matrix completion problem, though it is incremental as it focuses on the simplest rank-one case.
The authors analyzed the asymptotic convergence rate of alternating minimization for rank-one matrix completion, establishing a polynomial upper bound in terms of the number of nodes and the largest degree in the graph of revealed entries.
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.