Linear coordinate-descent message passing for quadratic optimization

Zhang, G; Heusdens, R

Linear coordinate-descent message passing for quadratic optimization

Zhang, G

Heusdens, R

Permalink

Publication Type:: Journal Article
Citation:: Neural Computation, 2012, 24 (12), pp. 3340 - 3370
Issue Date:: 2012-12-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (699.12 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, G https://orcid.org/0000-0003-4521-542X	en_US
dc.contributor.author	Heusdens, R	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	Neural Computation, 2012, 24 (12), pp. 3340 - 3370	en_US
dc.identifier.issn	0899-7667	en_US
dc.identifier.uri	http://hdl.handle.net/10453/115369
dc.description.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. © 2012 Massachusetts Institute of Technology.	en_US
dc.relation.ispartof	Neural Computation	en_US
dc.relation.isbasedon	10.1162/NECO_a_00368	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Linear coordinate-descent message passing for quadratic optimization	en_US
dc.type	Journal Article
utslib.citation.volume	12	en_US
utslib.citation.volume	24	en_US
utslib.for	080108 Neural, Evolutionary and Fuzzy Computation	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	open_access
pubs.issue	12	en_US
pubs.publication-status	Published	en_US
pubs.volume	24	en_US

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. © 2012 Massachusetts Institute of Technology.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/115369