New Hardness Results for Low-Rank Matrix Completion

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 matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new mathsfNP -hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number varepsilon ∈ [ 2-O(d),frac17], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is mathsfNP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most varepsilon, even when the rank is allowed to exceed d by a multiplicative factor of O (frac1varepsilon 2 · log(1/varepsilon) ). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to varepsilon that decays polynomially in d. We establish similar mathsfNP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.