论文标题
基于有效电阻的图形laplacian优化的有效算法
An efficient algorithm for graph Laplacian optimization based on effective resistances
论文作者
论文摘要
在图形信号处理中，数据样本与图上的顶点相关联，而边缘权重表示这些样本之间的相似性。我们提出了一个凸优化问题，以从数据中学习稀疏连接的图形。我们证明，解决方案中的每个边缘重量都受到相应节点数据特征之间距离的倒数的上限。我们还表明，节点之间的有效电阻距离在淋巴结数据特征之间的距离上限。因此，我们提出的方法学习了一个稀疏连接的图，该图编码了数据的几何特性。我们还提出了一种坐标最小化算法，该算法在每次迭代时，都可以使用精确的最小化更新边缘权重。该算法基于封闭形式表达式具有简单且低复杂的实现。
In graph signal processing, data samples are associated to vertices on a graph, while edge weights represent similarities between those samples. We propose a convex optimization problem to learn sparse well connected graphs from data. We prove that each edge weight in our solution is upper bounded by the inverse of the distance between data features of the corresponding nodes. We also show that the effective resistance distance between nodes is upper bounded by the distance between nodal data features. Thus, our proposed method learns a sparse well connected graph that encodes geometric properties of the data. We also propose a coordinate minimization algorithm that, at each iteration, updates an edge weight using exact minimization. The algorithm has a simple and low complexity implementation based on closed form expressions.
