New Hardness Results for Low-Rank Matrix Completion

Dror Chawin, Ishay Haviv

The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank mat…