Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
share
Given a matrix M∈ℝ^m× n, the low rank matrix completion problem asks us to find a rank-k approximation of M as UV^⊤ for U∈ℝ^m× k and V∈ℝ^n× k by only observing a few entries masked by a binary matrix P_Ω∈{0, 1 }^m× n. As a particular instance of the weighted low rank approximation problem, solving low rank matrix completion is known to be computationally hard even to find an approximate solution [RSW16]. However, due to its practical importance, many heuristics have been proposed for this problem. In the seminal work of Jain, Netrapalli, and Sanghavi [JNS13], they show that the alternating minimization framework provides provable guarantees for low rank matrix completion problem whenever M admits an incoherent low rank factorization. Unfortunately, their algorithm requires solving two exact multiple response regressions per iteration and their analysis is non-robust as they exploit the structure of the exact solution. In this paper, we take a major step towards a more efficient and robust alternating minimization framework for low rank matrix completion. Our main result is a robust alternating minimization algorithm that can tolerate moderate errors even though the regressions are solved approximately. Consequently, we also significantly improve the running time of [JNS13] from O(mnk^2 ) to O(mnk ) which is nearly linear in the problem size, as verifying the low rank approximation takes O(mnk) time. Our core algorithmic building block is a high accuracy regression solver that solves the regression in nearly linear time per iteration.
READ FULL TEXT