Linear Coordinate-Descent Message Passing for Quadratic Optimization

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
Proceedings fo the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing, 2012, pp. 2005 - 2008
Issue Date:
2012-03-25
Full metadata record
Files in This Item:
Filename Description Size
06288301.pdfAccepted Manuscript version182.81 kB
Adobe PDF
In this paper 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. Therefore, the linear coordinate-descent (LiCD) algorithm has simpler updating rules than the min-sum algorithm. It is shown that when the quadratic matrix is walk-summable, the LiCD algorithm converges. As an application, the LiCD algorithm is utilized in solving general linear systems. The performance of the LiCD algorithm is found empirically to be comparable to that of the min-sum algorithm, but at lower complexity in terms of computation and storage.
Please use this identifier to cite or link to this item: