Simplified alternating-direction message passing for dual MAP LP-relaxation

Zhang, G; Heusdens, R

Simplified alternating-direction message passing for dual MAP LP-relaxation

Zhang, G

Heusdens, R

Permalink

Publication Type:: Conference Proceeding
Citation:: ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 2013, pp. 3397 - 3401
Issue Date:: 2013-10-18

Closed Access

	Filename	Description	Size
	06638288.pdf	Published version	124.85 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

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	2013-10-18	en_US
dc.identifier.citation	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 2013, pp. 3397 - 3401	en_US
dc.identifier.isbn	9781479903566	en_US
dc.identifier.issn	1520-6149	en_US
dc.identifier.uri	http://hdl.handle.net/10453/120327
dc.description.abstract	The approximate MAP inference over (factor) graphic models is of great importance in many applications. Due to its simplicity, linear-programming (LP) relaxation has become one of the most popular approaches to approximate MAP. In this paper, we propose a new message passing algorithm for the MAP LP-relaxation problem by using the alternating-direction method of multipliers (ADMM). At each iteration, the new algorithm performs two layers of optimization sequentially, that is node-oriented optimization and factor-oriented optimization. On the other hand, the recently proposed augmented dual LP (ADLP) algorithm, also based on the ADMM, has to perform three layers of optimization. We refer to our new algorithm as the simplified ADLP (SiADLP) algorithm. The design of the SiADLP algorithm stems from a new formulation for the dual LP problem. Experimental results show that the SiADLP algorithm outperforms the ADLP method. © 2013 IEEE.	en_US
dc.relation.ispartof	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings	en_US
dc.relation.isbasedon	10.1109/ICASSP.2013.6638288	en_US
dc.title	Simplified alternating-direction message passing for dual MAP LP-relaxation	en_US
dc.type	Conference Proceeding
utslib.for	080199 Artificial Intelligence and Image Processing not elsewhere classified	en_US
utslib.for	080599 Distributed Computing not elsewhere classified	en_US
utslib.for	090609 Signal Processing	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	closed_access
pubs.publication-status	Published	en_US

Abstract:

The approximate MAP inference over (factor) graphic models is of great importance in many applications. Due to its simplicity, linear-programming (LP) relaxation has become one of the most popular approaches to approximate MAP. In this paper, we propose a new message passing algorithm for the MAP LP-relaxation problem by using the alternating-direction method of multipliers (ADMM). At each iteration, the new algorithm performs two layers of optimization sequentially, that is node-oriented optimization and factor-oriented optimization. On the other hand, the recently proposed augmented dual LP (ADLP) algorithm, also based on the ADMM, has to perform three layers of optimization. We refer to our new algorithm as the simplified ADLP (SiADLP) algorithm. The design of the SiADLP algorithm stems from a new formulation for the dual LP problem. Experimental results show that the SiADLP algorithm outperforms the ADLP method. © 2013 IEEE.

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

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