缺少条款的SVD

Question

给出一个真正的矩阵A，以便：

• A对称
• 所有的非对角项都是已知的和正的。
• 所有对角线项都不见了
• 有等级k

我想找出A的最好的完成，称为Ac，这样(大约)秩(Ac)=k。

矩阵A可以是巨大的(比如n>100000)，所以我需要一个最多是O(n^3)的方法。

要做到这一点，我在考虑SVD分解时缺少的术语：

我分解A，然后通过选择第一个k个奇异向量来恢复它。

我的问题是:当要分解的矩阵存在缺失项时，是否存在关于SVD的可靠结果？

Answer 1

这和最大的切割问题有着密切的联系。通常情况下，最大割集问题的半定松弛涉及到在Ac是正半定约束下，这样一个Ac的迹最小。我发现Christoph的ConicBundle码特别适合于计算这些问题的数值解。