On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

DOI10.1109/18.910585zbMath1002.94057OpenAlexW2098387242MaRDI QIDQ4544517

Publication date: 4 August 2002

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.910585

zbMATH Keywords

fixed points Bayesian networks Markov random fields MAP estimate min-sum algorithm max-product assignment max-product belief propagation algorithm

Mathematics Subject Classification ID

Bayesian inference (62F15) Applications of graph theory (05C90) Applications of graph theory to circuits and networks (94C15) Decoding (94B35)

Related Items (20)

Inference methods for CRFs with co-occurrence statistics ⋮ Analytical solution to the \(k\)-core pruning process ⋮ Efficient approximate linear programming for factored MDPs ⋮ Convergence and Correctness of Max-Product Belief Propagation for Linear Programming ⋮ Detecting parametric objects in large scenes by Monte Carlo sampling ⋮ Multi-view clustering by virtually passing mutually supervised smooth messages ⋮ Leveraging cluster backbones for improving MAP inference in statistical relational models ⋮ On Resolving Simultaneous Congruences Using Belief Propagation ⋮ Message-passing algorithms for inference and optimization ⋮ The cavity approach for Steiner trees packing problems ⋮ Data association based on optimization in graphical models with application to sensor networks ⋮ An efficient implementation of track-oriented multiple hypothesis tracker using graphical model approaches ⋮ A survey on learning approaches for undirected graphical models. Application to scene object recognition ⋮ Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation ⋮ A review of message passing algorithms in estimation of distribution algorithms ⋮ Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ Modelling sequences using pairwise relational features ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ A rigorous analysis of the cavity equations for the minimum spanning tree

This page was built for publication: On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs