Title :
Convergence of Min-Sum Message Passing for Quadratic Optimization
Author :
Moallemi, Ciamac C. ; Van Roy, Benjamin
Author_Institution :
Grad. Sch. of Bus., Columbia Univ., New York, NY
fDate :
5/1/2009 12:00:00 AM
Abstract :
We establish the convergence of the min-sum message passing algorithm for minimization of a quadratic objective function given a convex decomposition. Our results also apply to the equivalent problem of the convergence of Gaussian belief propagation.
Keywords :
convergence; message passing; minimisation; quadratic programming; Gaussian belief propagation; convex decomposition; min-sum message passing; min-sum message passing algorithm; minimization; quadratic optimization; Belief propagation; Convergence; Decoding; Graphical models; Heuristic algorithms; Linear programming; Message passing; Minimization methods; Parity check codes; Sum product algorithm; Decentralized optimization; message-passing algorithms;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2009.2016055
