Inferring sparse graphs from smooth signals with theoretical guarantees
Inferring sparse graphs from smooth signals with theoretical guarantees
复制标题
从具有理论保证的平滑信号推断稀疏图
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Rabbat
中科院分区：
文献类型：
--
作者：
M. Rabbat
我们考虑的问题推断出一个图的信号被假定为是光滑的图形，在设置中的图形也被假定为稀疏的。我们专注于测量是高斯向量和图形拓扑结构的协方差矩阵的逆编码的情况下。此外，假设逆协方差的权重使得模型是吸引的-所有的偏相关都是非负的。与其他方法，寻求最小化拉普拉斯二次型或涉及解决一个log-det程序，我们研究了一个简单的估计软阈值的基础上。该估计器只需要计算一个特征值分解，因此它可以很容易地扩展到具有数千个顶点的网络。我们提供的理论结果的重建误差作为一个函数的观察和问题的尺寸的情况下，假设底层图形是稀疏的。
We consider the problem of inferring a graph from signals which are assumed to be smooth over the graph, in the setting where the graph is also assumed to be sparse. We focus on the case where measurements are Gaussian vectors and the graph topology is encoded in the inverse of the covariance matrix. In addition, the weights of the inverse covariance are assumed to be such that the model is attractive—all partial correlations are non-negative. Unlike other approaches which seek to minimize the Laplacian quadratic form or involve solving a log-det program, we study a simple estimator based on soft thresholding. The estimator involves computing only a single eigenvalue decomposition, and so it can easily scale to networks with thousands of vertices. We provide theoretical results on the reconstruction error as a function of the number of observations and problem dimensions for the case where the underlying graph is assumed to be sparse.