## Message-Passing Algorithms for Quadratic Minimization

*Nicholas Ruozzi, Sekhar Tatikonda*; 14(Aug):2287−2314, 2013.

### Abstract

Gaussian belief propagation (GaBP) is an iterative algorithm for
computing the mean (and variances) 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
covariance matrix. As was observed by Malioutov et al. (2006),
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.

[abs][pdf][bib]