Matrix Completion from General Deterministic Sampling Patterns

Low-rank matrix completion is to exactly or approximately recover an underlying rank-r matrix from a small number of observed entries of the matrix. It has received much attention in a wide range of applications including collaborative filtering [Goldberg et al., 1992], phase retrieval [Candes et al., 2015] and image processing [Chen and Suter, 2004]. In research on establishing provable guarantees for low-rank matrix completion methods, typical assumptions considered are as follows: first, the underlying matrix is incoherent; second, observable matrix entries are sampled according to a probabilistic (usually uniform) model. However, the latter assumption is easily violated in numerous situations; it is unlikely realistic for the sampling patterns to be uniformly at random outside experimental settings, and it may not be even reasonable to model the sampling patterns as random. With this motivation, we aim to tackle the low-rank matrix completion problem without imposing any model assumptions on the sampling patterns. Even though there have been several works on non-random sampling schemes, they have imposed additional structural assumptions on the sampling pattern which are also not applicable to many real-world scenarios. For example, Heiman et al. [2014], Bhojanapalli and Jain [2014] and Burnwal and Vidyasagar [2020] assumed that the number of observed entries is the same for each row and column of the matrix, and Bishop and Yu [2014] introduced systematic assumptions on the subsets of the observed entries.