Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion
arXiv:2008.04988
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.
arXiv comment6 pages, 4 figures
References in corpus (3)
- Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
- A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
- Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers