Computational Limits for Matrix Completion
Computational Limits for Matrix Completion
复制标题
矩阵补全的计算限制
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Benjamin Weitz
中科院分区：
文献类型：
--
作者：
Moritz Hardt;Raghu Meka;P. Raghavendra;Benjamin Weitz
矩阵完成是从其条目的子样本中恢复未知的实价低级数矩阵的问题。最新的最新结果表明，在未知矩阵不连贯的假设下，可以有效地解决该问题，并且子样本是随机均匀绘制的。这些假设需要吗？
众所周知，矩阵完整的完整性是NP-HARD。但是，鲜为人知的是否有其他假设，例如不一致并允许算法输出级别稍高的矩阵。在本文中，我们证明，即使未知矩阵的排名$ 4 $，矩阵的完成仍然在计算上保持棘手，但我们可以输出任何常数级别矩阵，即使我们另外我们假设未知矩阵是不相似的，并且显示了$ 90％的$ 90％$条目。此结果依赖于$ 4 $颜色问题的猜想硬度。我们还考虑了阳性的半矩阵完成问题。在这里，我们在标准假设下显示了类似的硬度结果，即$ \ mathrm {p} \ ne \ mathrm {np}。$
我们的结果大大缩小了现有可行性结果与计算下限之间的差距。特别是，我们认为我们的结果给出了第一个复杂性理论理由，即为什么除了不一致的假设以外，为了获得积极的结果，为什么还需要分布假设。从技术方面来说，我们为如何在低级别优化问题中编码硬组合问题做出了一些新想法。我们希望这些技术将有助于进一步了解矩阵完成和相关问题的计算限制。
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.