基于矩阵补全算法的图恢复

Question

有没有什么矩阵补全算法可以用来重建一个仅使用少量边的图？

有许多算法可以恢复和完成仅有几个采样项的未知矩阵。据我所知，许多算法适用于低秩矩阵，而图的邻接矩阵不适用于低秩矩阵。比如SVT。

Answer 1

不幸的是，许多用矩阵表示的自然图类型都是高排名的(例如树、圈和网格)。从这个意义上说，这个问题不是一个矩阵完成问题，例如，在Cai，Candes和Shen的A SINGULAR VALUE THRESHOLDING ALGORITHM FOR MATRIX COMPLETION中所述的问题。

这意味着，如果没有低秩的约束，从线性代数的角度来看，问题是不适定的，不能解决。