2012/12/16 by Nima Noorshams, Martin J. Wainwright, Noorshams, Nima +1 · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Artificial intelligence #Basis (linear algebra) #Belief propagation #Computer science #Control Systems and Identification #Distributed Sensor Networks and Detection Algorithms #Distributed computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Factor graph #Fixed point #Graphical model #Information Theory (cs.IT) #Iterated function #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematical optimization #Mathematics #Message passing #Series (stratigraphy) #Smoothness #State (computer science) #Stochastic approximation #Target Tracking and Data Fusion in Sensor Networks #Theoretical computer science #Tree (set theory) #Wireless Communication Security Techniques #cs.IT #cs.LG #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.1212.3850
published in arXiv (Cornell University) 14(1), 2799-2835 (Cornell University) · Portions of the results were presented at the International Symposium on Information Theory 2012. The results were also submitted to the Journal of Machine Learning Research on December 16th 2012
arxiv created 2012/12/16 · openalex publication_date 2012/12/16 · arxiv updated 2012/12/18 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The sum-product or belief propagation (BP) algorithm is a widely used\nmessage-passing technique for computing approximate marginals in graphical\nmodels. We introduce a new technique, called stochastic orthogonal series\nmessage-passing (SOSMP), for computing the BP fixed point in models with\ncontinuous random variables. It is based on a deterministic approximation of\nthe messages via orthogonal series expansion, and a stochastic approximation\nvia Monte Carlo estimates of the integral updates of the basis coefficients. We\nprove that the SOSMP iterates converge to a \δ-neighborhood of the unique\nBP fixed point for any tree-structured graph, and for any graphs with cycles in\nwhich the BP updates satisfy a contractivity condition. In addition, we\ndemonstrate how to choose the number of basis coefficients as a function of the\ndesired approximation accuracy \δ and smoothness of the compatibility\nfunctions. We illustrate our theory with both simulated examples and in\napplication to optical flow estimation.\n