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

Publication Type:
Conference Proceeding
ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 2013, pp. 3397 - 3401
Issue Date:
Filename Description Size
06638288.pdfPublished version124.85 kB
Adobe PDF
Full metadata record
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: