title: Linear coordinate-descent message passing for quadratic optimization.
abstract: 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.
authors.affiliation: Department of Intelligent Systems, Delft University of Technology, Delft, the Netherlands. g.zhang-1@tudelft.nl
authors.forename: Guoqiang
authors.initials: G
authors.lastname: Zhang
authors.forename: Richard
authors.initials: R
authors.lastname: Heusdens