Deterministic Polynomial Time Algorithms for Matrix Completion Problems
Deterministic Polynomial Time Algorithms for Matrix Completion Problems
We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e., the problem of assigning values to the variables in a given symbolic matrix to maximize the resulting matrix rank. Matrix completion is one of the fundamental problems in computational complexity. …