Bi-Alternating Direction Method of Multipliers over Graphs

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2015, pp. 3571 - 3575
Issue Date:
2015-08-06
Full metadata record
Files in This Item:
Filename Description Size
07178636.pdfPublished version169.75 kB
Adobe PDF
In this paper, we extend the bi-alternating direction method of multipliers (BiADMM) designed on a graph of two nodes to a graph of multiple nodes. In particular, we optimize a sum of convex functions defined over a general graph, where every edge carries a linear equality constraint. In designing the new algorithm, an augmented primal-dual Lagrangian function is carefully constructed which naturally captures the associated graph topology. We show that under both the synchronous and asynchronous updating schemes, the extended BiADMM has the convergence rate of O(1/K) (where K denotes the iteration index) for general closed, proper and convex functions. As an example, we apply the new algorithm for distributed averaging. Experimental results show that the new algorithm remarkably outperforms the state-of-the-art methods.
Please use this identifier to cite or link to this item: