Simplified Alternating-Direction Message Passing for Dual MAP LP-Relaxation

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
2013 IEEE International Conference on Acoustics, Speech and Signal Processing, 2013, pp. 3397 - 3401
Issue Date:
2013-10-21
Full metadata record
Files in This Item:
Filename Description Size
06638288.pdfPublished version124.85 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: