Matrix Completion is the problem of recovering an unknown real-valued
low-rank matrix from a subsample of its entries. Important recent results show
that the problem can be solved efficiently under the assumption that the
unknown matrix is incoherent and the subsample is drawn uniformly at random.
Are these assumptions necessary?
It is well known that Matrix Completion in its full generality is NP-hard.
However, little is known if make additional assumptions such as incoherence and
permit the algorithm to output a matrix of slightly higher rank. In this paper
we prove that Matrix Completion remains computationally intractable even if the
unknown matrix has rank $4$ but we are allowed to output any constant rank
matrix, and even if additionally we assume that the unknown matrix is
incoherent and are shown $90%$ of the entries. This result relies on the
conjectured hardness of the $4$-Coloring problem. We also consider the positive
semidefinite Matrix Completion problem. Here we show a similar hardness result
under the standard assumption that $\mathrm{P}\ne \mathrm{NP}.$
Our results greatly narrow the gap between existing feasibility results and
computational lower bounds. In particular, we believe that our results give the
first complexity-theoretic justification for why distributional assumptions are
needed beyond the incoherence assumption in order to obtain positive results.
On the technical side, we contribute several new ideas on how to encode hard
combinatorial problems in low-rank optimization problems. We hope that these
techniques will be helpful in further understanding the computational limits of
Matrix Completion and related problems.

本文证明了矩阵完成问题即使假设未知矩阵的秩为 4 并且允许输出任意常数秩的矩阵，以及假设未知矩阵不相干并展示 90% 的条目，在 4 着色问题的推测难度性的基础上，矩阵完成问题仍然是计算上难解的；而在标准假设 P≠NP 下，对于正半定矩阵完成问题，我们也展示了类似的难度结果。

矩阵补全的计算限制

Computational Limits for Matrix Completion

Alternating Minimization is a widely used and empirically successful
heuristic for matrix completion and related low-rank optimization problems.
Theoretical guarantees for Alternating Minimization have been hard to come by
and are still poorly understood. This is in part because the heuristic is
iterative and non-convex in nature. We give a new algorithm based on
Alternating Minimization that provably recovers an unknown low-rank matrix from
a random subsample of its entries under a standard incoherence assumption. Our
results reduce the sample size requirements of the Alternating Minimization
approach by at least a quartic factor in the rank and the condition number of
the unknown matrix. These improvements apply even if the matrix is only close
to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in
the dimension of the matrix and, in a broad range of parameters, gives the
strongest sample bounds among all subquadratic time algorithms that we are
aware of.
Underlying our work is a new robust convergence analysis of the well-known
Power Method for computing the dominant singular vectors of a matrix. This
viewpoint leads to a conceptually simple understanding of Alternating
Minimization. In addition, we contribute a new technique for controlling the
coherence of intermediate solutions arising in iterative algorithms based on a
smoothed analysis of the QR factorization. These techniques may be of interest
beyond their application here.

使用一种基于交替最小化的新算法，在标准不连贯性假设下，可从一个未知的低秩矩阵中恢复随机子样本的条目，并减少至少一次方之秩和相似矩阵的条件数的交替最小化方法的样本大小要求。