Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting - Li, Jerry (2024)
We consider the well-studied problem of completing a rank-r, μ-incoherent matrix [M] [R]^[d × d] from incomplete observations. We focus on this problem in the semi-random setting where each entry is independently revealed with probability at least p = [[poly](r, μ, d)][d]. Whereas multiple nearly-linear time algorithms have been established in the more specialized fully-random setting where each entry is revealed with probability exactly p, the only known nearly-linear time algorithm in the semi-random setting is due to [CG18], whose sample complexity has a polynomial dependence on the inverse accuracy and condition number and thus cannot achieve high-accuracy recovery. Our main result is the first high-accuracy nearly-linear time algorithm for solving semi-random matrix completion, and an extension to the noisy observation setting. Our result builds upon the recent short-flat decomposition framework of [KLLST23a, KLLST23b] and leverages fast algorithms for flow problems on graphs to solve adaptive reweighting subproblems efficiently.