Message-passing algorithms for quadratic minimization
From MaRDI portal
Abstract: Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite quadratic function. As was observed in previous work, the GaBP algorithm fails to converge if the computation trees produced by the algorithm are not positive definite. In this work, we will show that the failure modes of the GaBP algorithm can be understood via graph covers, and we prove that a parameterized generalization of the min-sum algorithm can be used to ensure that the computation trees remain positive definite whenever the input matrix is positive definite. We demonstrate that the resulting algorithm is closely related to other iterative schemes for quadratic minimization such as the Gauss-Seidel and Jacobi algorithms. Finally, we observe, empirically, that there always exists a choice of parameters such that the above generalization of the GaBP algorithm converges.
Recommendations
- On the convergence of Gaussian belief propagation with nodes of arbitrary size
- Regularized Gaussian belief propagation
- Correctness of belief propagation in Gaussian graphical models of arbitrary topology
- Convex combination belief propagation
- Convergence analysis of distributed inference with vector-valued Gaussian belief propagation
Cited in
(11)- Approximate message passing algorithms for rotationally invariant matrices
- Linear coordinate-descent message passing for quadratic optimization
- Cycle-based cluster variational method for direct and inverse inference
- scientific article; zbMATH DE number 7255132 (Why is no real title available?)
- Convergence of Min-Sum Message Passing for Quadratic Optimization
- Gaussian belief propagation solvers for nonsymmetric systems of linear equations
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Convergence of Gaussian belief propagation under general pairwise factorization: connecting Gaussian MRF with pairwise linear Gaussian model
- On the convergence of Gaussian belief propagation with nodes of arbitrary size
- scientific article; zbMATH DE number 6253910 (Why is no real title available?)
- Message-passing algorithms for inference and optimization
This page was built for publication: Message-passing algorithms for quadratic minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933883)
