给定一个实数矩阵 A 使得:
- A 是对称的
- 所有非对角线项都是已知且正的
- 所有对角线项都缺失
- 排名k
我想找到 A 的最佳可能完成,称为 Ac,这样(大约)rank(Ac)=k。
矩阵 A 可能很大(比如 n>100000),所以我需要一个最多工作为 O(n^3) 的方法。
为此,我正在考虑缺少项的 SVD 分解:
我分解 A,然后通过选择前 k 个奇异向量来恢复它。
我的问题是:当要分解的矩阵有缺失项时,SVD 是否存在可靠的结果?
最佳答案
这与最大割问题之间有着密切的联系。最大割问题的通常半定松弛涉及在 Ac 是半正定约束条件下最小化这种 Ac 的迹。我找到了 Christoph Helmberg's ConicBundle code特别适合计算这些问题的数值解。
关于algorithm - 缺少项的 SVD,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37634938/