Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization

Abstract

We study low-rank matrix completion in the semi-random model, where each entry (i, j) is observed independently with an unknown probability p_i,j≥ p, in contrast to the standard model with a uniform probability p. While prior work has shown that nonconvex approach succeeds in the semi-random model for exact observations [CG18], it remains unclear whether similar guarantees extend to more general observation model, such as noisy or one-bit measurements. In this paper, we give a unified framework for semi-random matrix recovery applicable to a broad family of observation models. Our approach builds on the preprocessing step of [CG18] to restore regularity conditions that are violated under adversarial sampling, and leverages the primal-dual framework of [ZWYG18] to obtain near-optimal recovery guarantees. As concrete corollaries, we show that for both noisy and one-bit matrix completion in the semi-random model, after the preprocessing step, every local minimum of the non-convex objective yields an approximate recovery of the ground-truth matrix.