Abstract: Matrix completion is a modern missing-data problem in which both the missing structure and the underlying parameter are high dimensional. Despite the missing structure being a key component of any missing-data problem, existing matrix-completion methods often assume a simple uniform missing mechanism. In this work, we study matrix completion from corrupted data under a novel low-rank missing mechanism. The observation probability matrix is estimated using a high-dimensional, low-rank matrix-estimation procedure, and then used to complete the target matrix via inverse probability weighting. Owing to the high-dimensional and extreme (i.e., very small) nature of the true probability matrix, the effect of inverse probability weighting requires careful study. Lastly, we derive optimal asymptotic convergence rates of the proposed estimators for both the observation probabilities and the target matrix.

Key words and phrases: Low-rank, missing, nuclear-norm, regularization.