algorithm - 使用矩阵完成算法恢复图形

Question

是否有任何矩阵完成算法可用于仅使用少量边来重建图？

有许多算法可以恢复和完成只有几个采样条目的未知矩阵。据我所知，这些算法中的许多都适用于低秩矩阵，这对于图邻接矩阵来说是不正确的。像 SVT。

Answer 1

不幸的是，许多表示为矩阵的自然图类型被证明是高等级的（例如树、循环和网格）。从这个意义上说，问题不是矩阵完成问题，例如Cai、Candes 和 Shen在矩阵完成的奇异值阈值算法中所述。

这意味着，如果没有低秩​​的约束，问题是从线性代数病态的角度来看的，无法解决。