Back to Search
Start Over
Log-Determinant Relaxation for Approximate Inference in Discrete Markov Random Fields.
- Source :
- IEEE Transactions on Signal Processing; Jun2006 Part 1, Vol. 54 Issue 6, p2099-2109, 11p, 2 Black and White Photographs, 6 Diagrams, 6 Graphs
- Publication Year :
- 2006
-
Abstract
- Graphical models are well suited to capture the complex and non-Gaussian statistical dependencies that arise in many real-world signals. A fundamental problem common to any signal processing application of a graphical model is that of computing approximate marginal probabilities over subsets of nodes. This paper proposes a novel method, applicable to discrete-valued Markov random fields (MRFs) on arbitrary graphs, for approximately solving this marginalization problem. The foundation of our method is a reformulation of the marginalization problem as the solution of a low-dimensional convex optimization problem over the marginal polytope. Exactly solving this problem for general graphs is intractable; for binary Markov random fields, we describe how to relax it by using a Gaussian bound on the discrete entropy and a semidefinite outer bound on the marginal polytope. This combination leads to a log-determinant maximization problem that can be solved efficiently by interior point methods, thereby providing approximations to the exact marginals. We show how a slightly weakened log-determinant relaxation can be solved even more efficiently by a dual reformulation. When applied to denoising problems in a coupled mixture-of-Gaussian model defined on a binary MRF with cycles, we find that the performance of this log-determinant relaxation is comparable or superior to the widely used sum-product algorithm over a range of experimental conditions. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 1053587X
- Volume :
- 54
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Signal Processing
- Publication Type :
- Academic Journal
- Accession number :
- 21209304
- Full Text :
- https://doi.org/10.1109/TSP.2006.874409