Matrix Completion from General Deterministic Sampling Patterns
This work addresses a limitation in matrix completion by extending guarantees to general deterministic sampling, which is incremental but useful for applications where random sampling is impractical.
The paper tackles the problem of low-rank matrix completion under arbitrary deterministic sampling patterns, establishing theoretical guarantees for exact and approximate recovery using constrained nuclear norm minimization. The authors show that success depends on the observation graph being well-connected with similar node degrees, and their theory improves prior results for symmetric matrices.
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.