Department of Intelligent Systems, Delft University of Technology, Delft, the Netherlands.
Neural Comput. 2012 Dec;24(12):3340-70. doi: 10.1162/NECO_a_00368. Epub 2012 Sep 12.
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.
在这封信中，我们提出了一种用于二次优化的新消息传递算法。该新算法的设计基于相邻节点之间的线性坐标下降。与消息形式为二次函数的 min-sum 算法相比，更新消息的形式为线性函数。因此，线性坐标下降（LiCD）算法每条消息只传输一个参数，而 min-sum 算法每条消息传输两个参数。我们表明，当二次矩阵是可遍历的时，LiCD 算法收敛。通过将 LiCD 算法作为子程序，我们还解决了一般二次矩阵的收敛问题。LiCD 算法以同步或异步的消息传递方式工作。实验结果表明，对于具有多个循环的一般图，LiCD 算法的收敛速度与 min-sum 算法相当，从而减少了要传输的参数数量和计算复杂度。
