| Paper ID | SPTM-15.5 |
| Paper Title |
AN EFFICIENT ALTERNATING DIRECTION METHOD FOR GRAPH LEARNING FROM SMOOTH SIGNALS |
| Authors |
Xiaolu Wang, Chaorui Yao, Haoyu Lei, Anthony Man-Cho So, The Chinese University of Hong Kong, Hong Kong SAR China |
| Session | SPTM-15: Graph Topology Inference and Clustering |
| Location | Gather.Town |
| Session Time: | Thursday, 10 June, 14:00 - 14:45 |
| Presentation Time: | Thursday, 10 June, 14:00 - 14:45 |
| Presentation |
Poster
|
| Topic |
Signal Processing Theory and Methods: [OPT] Optimization Methods for Signal Processing |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
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. |
