Convergence of Min-Sum Message Passing for Quadratic Optimization

2006/03/14 by Ciamac C. Moallemi, Moallemi, Ciamac C., Benjamin Van Roy +1
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Artificial Intelligence (cs.AI) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques

paper · pdf · doi:10.48550/arxiv.cs/0603058

openalex publication_date 2006/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We establish the convergence of the min-sum message passing algorithm for minimization of a broad class of quadratic objective functions: those that admit a convex decomposition. Our results also apply to the equivalent problem of the convergence of Gaussian belief propagation.

Related

• Convergence of the Min-Sum Algorithm for Convex Optimization
• Convergence of Message-Passing for Distributed Convex Optimisation with Scaled Diagonal Dominance
• A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification
• Approximate message-passing for convex optimization with non-separable penalties
• Convergence Rate of a Message-passing Algorithm for Solving Linear Systems