Linear coordinate-descent message-passing for quadratic optimization

Publication Type:
Conference Proceeding
ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 2012, pp. 2005 - 2008
Issue Date:
Filename Description Size
06288301.pdfAccepted Manuscript version182.81 kB
Adobe PDF
Full metadata record
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. © 2012 IEEE.
Please use this identifier to cite or link to this item: