Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting

We consider the well-studied problem of completing a rank-r, µ-incoherent matrix M 2 R d⇥d from incomplete observations. We focus on this problem in the semirandom setting where each entry is independently revealed with probability at least p = poly(r,µ,log d) d . Whereas multiple nearly-linear time algorithms have been established in the more specialized fully-random setting where each entry is revealed with probablity exactly p, the only known nearly-linear time algorithm in the semi-random setting is due to [17] , 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 [42, 43] and leverages fast algorithms for flow problems on graphs to solve adaptive reweighting subproblems efficiently.