DocumentCode
749937
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
Volume
55
Issue
5
fYear
2009
fDate
5/1/2009 12:00:00 AM
Firstpage
2413
Lastpage
2423
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;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.2009.2016055
Filename
4839028
Link To Document