Factor graphs and the sum-product algorithm

DOI10.1109/18.910572zbMath0998.68234OpenAlexW2137813581WikidataQ56698904 ScholiaQ56698904MaRDI QIDQ4544503

Frank R. Kschischang, Hans-Andrea Loeliger, Brendan J. Frey

Publication date: 4 August 2002

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/08c370eb9ba13bfb836349e7f3ea428be4697818

zbMATH Keywords

Viterbi algorithmsum-product algorithmbelief propagationfactor graphsfast Fourier transform algorithmsturbo decoding algorithmforward/backward algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Factor metanetwork: a multilevel probabilistic meta-model based on factor graphs, Geometric Constructions of Gallager Codes, The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation, A New Inference Framework for Dependency Networks, Basics of Secrecy Coding, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Random Instances of Problems in NP – Algorithms and Statistical Physics, Unnamed Item, Marginalization in models generated by compositional expressions, Linear Response Algorithms for Approximate Inference in Graphical Models, TSFC: A Structure-Preserving Form Compiler, On the Uniqueness of Loopy Belief Propagation Fixed Points, A Binary Variable Model for Affinity Propagation, SPARSE CODE MULTIPLE ACCESS CODEBOOK DESIGN USING SINGULAR VALUE DECOMPOSITION, A local algorithm and its percolation analysis of bipartite z-matching problem, Flexibly regularized mixture models and application to image segmentation, Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu, A Message-Passing Approach to Phase Retrieval of Sparse Signals, Learning multi-agent coordination through connectivity-driven communication, Phase transitions in theq-coloring of random hypergraphs, Multi-view clustering by virtually passing mutually supervised smooth messages, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Spike-Based Probabilistic Inference in Analog Graphical Models Using Interspike-Interval Coding, Two faces of greedy leaf removal procedure on graphs, Gibbs states and the set of solutions of random constraint satisfaction problems, Adaptive Soft-Decision Iterative Decoding Using Edge Local Complementation, Statistical mechanics of the fashion game on random networks, The large deviations of the whitening process in random constraint satisfaction problems, Generalizedk-core pruning process on directed networks, Hexagonal Grid Fields Optimally Encode Transitions in Spatiotemporal Sequences, Probabilistic Graphical Models and Markov Networks, Convergence Theorems of Estimation of Distribution Algorithms, Fast Fitness Improvements in Estimation of Distribution Algorithms Using Belief Propagation, Reward-Modulated Hebbian Learning of Decision Making, Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation, Square Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing, Codes on graphs: Recent progress, Unnamed Item, Graphical models, Link-Level Aspects, A Framework for Solving Hybrid Influence Diagrams Containing Deterministic Conditional Distributions, Measure Transformer Semantics for Bayesian Machine Learning, Tropical geometry of statistical models, Parametric inference for biological sequence analysis, On the survey-propagation equations in random constraint satisfiability problems, Propagation of external regulation and asynchronous dynamics in random Boolean networks, Characterizing Marginalization and Incremental Operations on the Bayes Tree, The theoretical capacity of the Parity Source Coder, Geometrical organization of solutions to random linear Boolean equations, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Cortical Circuitry Implementing Graphical Models, Statistical and Computational Guarantees for the Baum-Welch Algorithm, The number of matchings in random graphs, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, Transducing Markov sequences, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Belief propagation: accurate marginals or accurate partition function—where is the difference?, Unnamed Item, Bayesian Inference in Cumulative Distribution Fields, IMPACT OF SUBCARRIER ALLOCATION BY ROWS ON TOTAL SUM RATE FOR SCMA SYSTEMS, Unnamed Item, ON THE CLASS OF ARRAY-BASED APM-LDPC CODES, Improving probabilistic inference in graphical models with determinism and cycles, Characterizations of pseudo-codewords of (low-density) parity-check codes, Graphical models for statistical inference and data assimilation, Positioning based on factor graphs, LDPC code design for nonuniform power-line channels, Event detection using ``variable module graphs for home care applications, Matrix fraction descriptions in convolutional coding, An explicit method to generate some QC LDPC codes with girth 8, Bayesian pedigree inference with small numbers of single nucleotide polymorphisms via a factor-graph representation, Probabilistic modelling, inference and learning using logical theories, Loop series for discrete statistical models on graphs, Optimal 2-constraint satisfaction via sum-product algorithms, Parallel finite element technique using Gaussian belief propagation, Belief Propagation in Networks of Spiking Neurons, Multicuts and perturb \& MAP for probabilistic graph clustering, Introduction: Combining probability and logic, Probabilistic reasoning in a classical logic, A probabilistic graphical model approach to stochastic multiscale partial differential equations, Rigorous inequalities between length and time scales in glassy systems, Efficient and robust associative memory from a generalized Bloom filter, The asymptotics of the clustering transition for random constraint satisfaction problems, Ensemble clustering using factor graph, Knowledge graphs completion via probabilistic reasoning, Hierarchical semi-Markov conditional random fields for deep recursive sequential data, Formalization of Error-Correcting Codes: From Hamming to Modern Coding Theory, An evolutionary model that satisfies detailed balance, Accelerated training of max-margin Markov networks with kernels, A generalized gamma mixture model for ultrasonic tissue characterization, On learning conditional random fields for stereo, Spatio-temporal random fields: compressible representation and distributed estimation, A framework for parallel second order incremental optimization algorithms for solving partially separable problems, Gamma-based clustering via ordered means with application to gene-expression analysis, Access point selection in heterogeneous wireless networks using belief propagation, A novel probabilistic clustering model for heterogeneous networks, Model-based machine learning, Fast density-weighted low-rank approximation spectral clustering, Graph-based slice-to-volume deformable registration, Markov network based ontology matching, Study of the variable growth hypernetworks influence on the scaling law, Monotonic optimization based decoding for linear codes, Tomographic reconstruction from a small number of projections by an efficient sum-product reasoning method, Graphical models for optimal power flow, An iterative algorithm and low complexity hardware architecture for fast acquisition of long PN codes in UWB systems, On the dynamics of the glass transition on Bethe lattices, A complementary construction using mutually unbiased bases, A library for formalization of linear error-correcting codes, Joint source-decoding in large scale sensor networks using Markov random field models, Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results, Unsupervised representation learning with minimax distance measures, Learning representations from dendrograms, Robustifying sum-product networks, Message-passing algorithms for inference and optimization, Non parametric distributed inference in sensor networks using box particles messages, Explorative anytime local search for distributed constraint optimization, Predecessor existence problems for finite discrete dynamical systems, Quantum graphical models and belief propagation, Joint estimation of multiple related biological networks, Random subcubes as a toy model for constraint satisfaction problems, Next nearest neighbour Ising models on random graphs, Investigation of commuting Hamiltonian in quantum Markov network, Low-temperature excitations within the Bethe approximation, Statistical mechanics of reputation systems in autonomous networks, Lowering the error floor of Gallager codes: a statistical-mechanical view, Latent binary MRF for online reconstruction of large scale systems, Transfer affinity propagation-based clustering, Data association based on optimization in graphical models with application to sensor networks, On the freezing of variables in random constraint satisfaction problems, Dynamic Bayesian networks for formal verification of structured stochastic processes, A new approach to constructing CSS codes based on factor graphs, Parallel probabilistic graphical model approach for nonparametric Bayesian inference, Implied distributions in multiple change point problems, A review of message passing algorithms in estimation of distribution algorithms, Low-complexity Gaussian detection for MIMO systems, Bounded approximate decentralised coordination via the max-sum algorithm, Convergence and correctness of belief propagation for the Chinese postman problem, On a hypergraph probabilistic graphical model, Understanding the scalability of Bayesian network inference using clique tree growth curves, Exploiting coding theory for classification: an LDPC-based strategy for multiclass-to-binary decomposition, A new distributed approximation algorithm for the maximum weight independent set problem, Cospectral bipartite graphs with the same degree sequences but with different number of large cycles, Distribution of statistics of hidden state sequences through the sum-product algorithm, A biclustering approach based on factor graphs and the max-sum algorithm, On the combinatorial structure of a class of \(\left[ \binom m 2, \binom{m-1}{2}, 3\right\) shortened Hamming codes and their dual-codes], Operator growth bounds from graph theory, Pseudocodeword-free criterion for codes with cycle-free Tanner graph, Local and global approaches of affinity propagation clustering for large scale data, Convergence of a belief propagation algorithm for biological networks, A factor graph based genetic algorithm, A branch-cut-and-price algorithm for optimal decoding in digital communication systems, Relaxed maximum a posteriori fault identification, Bit-optimal decoding of codes whose Tanner graphs are trees, \textsc{Friet}: an authenticated encryption scheme with built-in fault detection, MAP inference via \(\ell_2\)-sphere linear program reformulation, Graphs for Margins of Bayesian Networks, Detecting cycles of length 8 in the Tanner graph of a QC-LDPC code based on protograph analysis, On the convergence of kikuchi's natural iteration method, Convex combination belief propagation, Unbiasing in iterative reconstruction algorithms for discrete compressed sensing, Lifted graphical models: a survey, Minimal contagious sets in random regular graphs