Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion

2020/08/11 by Liu, Rui, Olshevsky, Alex
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA)

paper · doi:10.48550/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.

Related

• Understanding Alternating Minimization for Matrix Completion
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
• Low-rank Matrix Completion using Alternating Minimization
• A deterministic theory of low rank matrix completion
• Fast matrix completion without the condition number