An Efficient Alternating Direction Method for Graph Learning from Smooth Signals
An Efficient Alternating Direction Method for Graph Learning from Smooth Signals
复制标题
一种从平滑信号进行图学习的高效交替方向方法
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. M. So
中科院分区：
文献类型：
--
作者：
Xiaolu Wang;Chao Yao;Haoyu Lei;A. M. So
我们考虑从一组平滑图信号中识别图拓扑的问题。解决这个问题的一个众所周知的方法是最小化狄利克雷能量并伴随一些弗罗贝尼乌斯范数正则化。最近的工作在节点度上结合了对数障碍，以在不影响图稀疏性的情况下提高整体图的连通性，这对于提高学习图的质量非常有效。尽管文献中已经提出了原对偶算法来解决此类图学习公式，但它缺乏严格的收敛分析，并且似乎具有缓慢的经验性能。在本文中，我们将图学习公式视为非光滑、严格凸优化问题，并开发了一种有效的乘子交替方向方法来解决它。我们证明了我们的算法通过任意初始化收敛到全局最小值。我们对各种合成图和真实世界图进行了广泛的实验，结果表明我们的方法表现出尖锐的线性收敛，并且比常用的原始对偶方法快得多。
We consider the problem of identifying the graph topology from a set of smooth graph signals. A well-known approach to this problem is minimizing the Dirichlet energy accompanied with some Frobenius norm regularization. Recent works have incorporated the logarithmic barrier on the node degrees to improve the overall graph connectivity without compromising graph sparsity, which is shown to be quite effective in enhancing the quality of the learned graphs. Although a primal-dual algorithm has been proposed in the literature to solve this type of graph learning formulations, it lacks a rigorous convergence analysis and appears to have a slow empirical performance. In this paper, we cast the graph learning formulation as a nonsmooth, strictly convex optimization problem and develop an efficient alternating direction method of multipliers to solve it. We show that our algorithm converges to the global minimum with arbitrary initialization. We conduct extensive experiments on various synthetic and real-world graphs, the results of which show that our method exhibits sharp linear convergence and is substantially faster than the commonly adopted primal-dual method.
影响因子：
14.9
作者：
Mateos, Gonzalo;Segarra, Santiago;Ribeiro, Alejandro
通讯作者：
Ribeiro, Alejandro