Matrix Completion from General Deterministic Sampling Patterns
Hanbyul Lee Rahul Mazumder Qifan Song Jean Honorio
Most of the existing works on provable guarantees for low-rank matrix
completion algorithms rely on some unrealistic assumptions such that matrix
entries are sampled randomly or the sampling pattern has a specific structure.
In this work, we establish theoretical guarantee for the exact and approximate
low-rank matrix completion problems which can be applied to any deterministic
sampling schemes. For this, we introduce a graph having observed entries as its
edge set, and investigate its graph properties involving the performance of the
standard constrained nuclear norm minimization algorithm. We theoretically and
experimentally show that the algorithm can be successful as the observation
graph is well-connected and has similar node degrees. Our result can be viewed
as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and
Vidyasagar [2020], in which the node degrees of the observation graph were
assumed to be the same. In particular, our theory significantly improves their
results when the underlying matrix is symmetric.