论文标题
分解对称矩阵的计算复杂性作为阳性半限定和对角线矩阵的总和
Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices
论文作者
论文摘要
我们研究了将对称矩阵分解为低级别阳性半金属基质和对角线基质的几种变体。这种分解在因子分析中具有应用，并且已经对其进行了数十年的研究。一方面，我们证明，当分解中的阳性半芬特矩阵的等级上方通过绝对常数界定时，可以在多项式时间内解决问题。另一方面，我们证明，通常，这些问题以及它们的某些近似版本都是NP-HARD。最后，我们证明，在真实的一阶理论中，许多这些低级分解问题都是完整的。即，给定任何多项式方程系统，我们可以在多项式时间内写下一个低级别的分解问题，以便原始系统具有解决方案，如果我们相应的分解问题具有可行的某些（最低）等级的解决方案。
We study several variants of decomposing a symmetric matrix into a sum of a low-rank positive semidefinite matrix and a diagonal matrix. Such decompositions have applications in factor analysis and they have been studied for many decades. On the one hand, we prove that when the rank of the positive semidefinite matrix in the decomposition is bounded above by an absolute constant, the problem can be solved in polynomial time. On the other hand, we prove that, in general, these problems as well as their certain approximation versions are all NP-hard. Finally, we prove that many of these low-rank decomposition problems are complete in the first-order theory of the reals; i.e., given any system of polynomial equations, we can write down a low-rank decomposition problem in polynomial time so that the original system has a solution iff our corresponding decomposition problem has a feasible solution of certain (lowest) rank.
