Matrix Completion in Almost-Verification Time

We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank-r matrix M ∈ ℝm × n (where m ≥ n) from random observations. First, we provide an algorithm which completes M on 99% of rows and columns under no further assumptions on M from ≈ mr samples and using ≈ mr2 time. Then, assuming the row and column spans of M satisfy additional regularity properties, we show how to boost this partial completion guarantee to a full matrix completion algorithm by aggregating solutions to regression problems involving the observations. In the well-studied setting where M has incoherent row and column spans, our algorithms complete M to high precision from mr2+o(1) observations in mr3 + o(1) time (omitting logarithmic factors in problem parameters), improving upon the prior state-of-the-art [JN15] which used ≈ mr5 samples and ≈ mr7 time. Under an assumption on the row and column spans of M we introduce (which is satisfied by random subspaces with high probability), our sample complexity improves to an almost information-theoretically optimal mr1 + o(1), and our runtime improves to mr2 + o(1). Our runtimes have the appealing property of matching the best known runtime to verify that a rank-r decomposition UV^top agrees with the sampled observations. We also provide robust variants of our algorithms that, given random observations from M + N with |N|F ≤ Delta, complete M to Frobenius norm distance ≈ r1.5Delta in the same runtimes as the noiseless setting. Prior noisy matrix completion algorithms [CP10] only guaranteed a distance of ≈ √nDelta.