Linear Coordinate-Descent Message Passing for Quadratic Optimization

Massachusetts Institute of Technology Press (MIT Press)
Publication Type:
Journal Article
Neural Computation, 2012, 24 (12), pp. 3340 - 3370
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
ContentServer (58).pdfPublished Version699.12 kB
Adobe PDF
In this letter, we propose a new message-passing algorithm for quadratic optimization. The design of the new algorithm is based on linear coordinate descent between neighboring nodes. The updating messages are in a form of linear functions as compared to the min-sum algorithm of which the messages are in a form of quadratic functions. As a result, the linear coordinate-descent (LiCD) algorithm transmits only one parameter per message as opposed to the min-sum algorithm, which transmits two parameters per message. We show that when the quadratic matrix is walk-summable, the LiCD algorithm converges. By taking the LiCD algorithm as a subroutine, we also fix the convergence issue for a general quadratic matrix. The LiCD algorithm works in either a synchronous or asynchronous message-passing manner. Experimental results show that for a general graph with multiple cycles, the LiCD algorithm has comparable convergence speed to the min-sum algorithm, thereby reducing the number of parameters to be transmitted and the computational complexity.
Please use this identifier to cite or link to this item: