Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion

Rui Liu, Alex Olshevsky

Abstract

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.
BibTeX
@inproceedings{liu2021asymptotic,
  author = {Rui Liu and Alex Olshevsky},
  title = {{Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2021},
  url = {https://openreview.net/forum?id=LDuSZJcKdR_},
}

Loading related content...

Figure