检索结果-内蒙古大学图书馆

Sufficient conditions for convergence of the sum-product algorithm

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第12期53卷 4422-4437页

作者： Mooij, Joris M. Kappen, Hilbert J. Radboud Univ Nijmegen NL-6500 HB Nijmegen Netherlands

Novel conditions are derived that guarantee convergence of the sum-product algorithm (also known as Loopy Belief Propagation or simply Belief Propagation (BP)) to a unique fixed point, irrespective of the initial messages, for parallel (synchronous) updates. The computational complexity of the conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing zeros, under some additional conditions. The conditions are compared with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, sufficient conditions are derived that take into account local evidence (i.e., single-variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms existing bounds.

关键词： contraction convergence factor graphs graphical models loopy belief propagation marginalization message passing sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

FFT Based sum-product algorithm for Decoding LDPC Lattices

引用

IEEE COMMUNICATIONS LETTERS 2012年第9期16卷 1504-1507页

作者： Safarnejad, Lida Sadeghi, Mohammad-Reza Amirkabir Univ Technol Fac Math & Comp Sci Tehran Iran

LDPC lattices were introduced by Sadeghi et al. in [13] and have a good performance under generalized min-sum and sum-product algorithms. The high complexity of these algorithms is mainly due to the search for local valid codewords in each check node process. In addition, when the dimension of such lattices is increased, these decoding algorithms are very time-consuming. In this paper, we propose an FFT based sum-product algorithm to decode LDPC lattices. In the check node process, using the FFT method reduces the check node complexity from O(d(c)g(2)) to O(d(c)g log g) where d(c) is the degree of a check equation and g is the alphabet size of an LDPC lattice. As a result, with almost the same complexity cost, we have a significant improvement over the performance of the min-sum based decoding 2-level LDPC lattices with the symbol error probability smaller than 10(-5) at SNR = 1.5 dB.

关键词： LDPC lattice sum-product algorithm FFT method

来源：评论

学校读者我要写书评

暂无评论

A novel broadcast scheduling strategy using factor graphs and the sum-product algorithm

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2006年第6期5卷 1241-1249页

作者： Chen, Jung-Chieh Wang, Yeong-Cheng Chen, Jiunn-Tsair Natl Kaohsiung Normal Univ Dept Optoelect & Commun Engn Kaohsiung Taiwan VaNung Univ Dept Informat Management Chungli Taiwan Natl Tsing Hua Univ Inst Commun Engn Hsinchu Taiwan

This paper presents a novel self-organizing distributed algorithm for finding a broadcasting schedule in a packet radio network via only local collaborative interactions among neighboring network stations. Inspired by the huge success of the low density parity check (LDPC) codes in the field of error control coding, we transform the broadcast scheduling problem (BSP) into an LDPC-like problem through a factor graph. In the proposed algorithm, the constraint rules of the BSP are divided into many simple local rules, each of which is enforced by a local processing unit in the factor graph. The soft-information, describing the probability that each station will transmit a data packet, is then efficiently exchanged among the local processing units by using the sum-product algorithm to iteratively optimize the broadcasting schedule. Simulation results indicate that the proposed algorithm performs better than the other existing central-processing algorithms in terms of the channel utilization and the average packet delay. This is true especially when the network scenario is very complex. Furthermore, the proposed algorithm is both low in complexity and completely distributed, which makes it suitable for implementation in practical network applications.

关键词： BSP factor graph sum-product algorithm soft-information

来源：评论

学校读者我要写书评

暂无评论

Factor graphs and the sum-product algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2001年第2期47卷 498-519页

作者： Kschischang, FR Frey, BJ Loeliger, HA Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada Univ Waterloo Fac Comp Sci Waterloo ON N2L 3G1 Canada Univ Illinois Fac Elect & Comp Engn Urbana IL 61801 USA ETH Zentrum Signal Proc Lab ISI CH-8092 Zurich Switzerland

algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of "local" functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph. In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative "turbo" decoding algorithm, Pearl's belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.

关键词： belief propagation factor graphs fast Fourier transform forward/backward algorithm graphical models iterative decoding Kalman filtering marginalization sum-product algorithm Tanner graphs Viterbi algorithm

来源：评论

学校读者我要写书评

暂无评论

Distribution of Statistics of Hidden State Sequences Through the sum-product algorithm

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2013年第4期15卷 897-918页

作者： Martin, Donald E. K. Aston, John A. D. N Carolina State Univ Dept Stat Raleigh NC 27695 USA Univ Warwick Dept Stat CRiSM Warwick England

We compute exact distributions of statistics of hidden state sequences in general settings. Distributions are computed for undirected and directed graphical models that are represented using conditional random fields and factor graphs. The methods discussed are relevant for graphs with a sparseness of edges that allows exact computation of the normalization constant. The distributions are obtained in an efficient manner by integrating sequential updates of the statistic's value with the sum-product algorithm. Applications of this work include discrete hidden state sequences perturbed by noise and/or missing values, and state sequences that serve to classify observations. In the case of classification, the methods give a way to quantify the uncertainty in statistics associated with the classifications. The algorithm is applied to model-based false discovery distributions for protein-protein interactions and distributions related to CpG island lengths in DNA sequences.

关键词： Automata theory Classification Conditional random field Distribution of pattern statistics Factor graph sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

A novel strategy using factor graphs and the sum-product algorithm for satellite broadcast scheduling problems

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2008年第3期E91B卷 927-930页

作者： Chen, Jung-Chieh Natl Kaohsiung Inst Technol Dept Optoelect & Commun Engn Kaohsiung 802 Taiwan

This paper presents a low complexity algorithmic framework for finding a broadcasting schedule in a low-altitude satellite system, i.e., the satellite broadcast scheduling (SBS) problem, based on the recent modeling and computational methodology of factor graphs. Inspired by the huge success of the low density parity check (LDPC) codes in the field of error control coding, in this paper, we transform the SBS problem into an LDPC-like problem through a factor graph instead of using the conventional neural network approaches to solve the SBS problem. Based on a factor graph framework, the soft-information, describing the probability that each satellite will broadcast information to a terminal at a specific time slot, is exchanged among the local processing in the proposed framework via the sum-product algorithm to iteratively optimize the satellite broadcasting schedule. Numerical results show that the proposed approach not only can obtain optimal solution but also enjoys the low complexity suitable for integral-circuit implementation.

关键词： SBS problem factor graph sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Box-minus operation and application in sum-product algorithm

引用

ELECTRONICS LETTERS 2005年第4期41卷 197-198页

作者： Tong, S Wang, P Wang, D Wang, X Xidian Univ State Key Lab ISN Xian 710071 Peoples R China

A new expression for box-minus operation, i.e. the inverse of box-plus operation, is derived, with which the box-minus operation can be implemented by a small look-up table. Its application in the sum-product algorith... 详细信息

关键词： computational complexity decoding parity check codes table lookup LDPCcodes box-minus operation computational complexity decoding lookup table low density paritycheck codes sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic Belief Propagation: A Low-Complexity Alternative to the sum-product algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第4期59卷 1981-2000页

作者： Noorshams, Nima Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

The belief propagation (BP) or sum-product algorithm is a widely used message-passing method for computing marginal distributions in graphical models. At the core of the BP message updates, when applied to a graphical model involving discrete variables with pairwise interactions, lies a matrix-vector product with complexity that is quadratic in the state dimension, and requires transmission of a (d - 1)-dimensional vector of real numbers (messages) to its neighbors. Since various applications involve very large state dimensions, such computation and communication complexities can be prohibitively complex. In this paper, we propose a low-complexity variant of BP, referred to as stochastic belief propagation (SBP). As suggested by the name, it is an adaptively randomized version of the BP message updates in which each node passes randomly chosen information to each of its neighbors. The SBP message updates reduce the computational complexity (per iteration) from quadratic to linear in, without assuming any particular structure of the potentials, and also reduce the communication complexity significantly, requiring only log(2) d bits transmission per edge. Moreover, we establish a number of theoretical guarantees for the performance of SBP, showing that it converges almost surely to the BP fixed point for any tree-structured graph, and for any graph with cycles satisfying a contractivity condition. In addition, for these graphical models, we provide nonasymptotic upper bounds on the convergence rate, showing that the l(infinity) norm of the error vector decays no slower than O(1/root t) with the number of iterations on trees and the normalized mean-squared error decays as O(1/t) for general graphs. This analysis, also supported by experimental results, shows that SBP can provably yield reductions in computational and communication complexities for various classes of graphical models.

关键词： Graphical models low-complexity belief propagation (BP) randomized algorithms stochastic approximation sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Classification-Aided Multitarget Tracking Using the sum-product algorithm

引用

IEEE SIGNAL PROCESSING LETTERS 2020年 27卷 1710-1714页

作者： Gaglione, Domenico Soldi, Giovanni Braca, Paolo De Magistris, Giovanni Meyer, Florian Hlawatsch, Franz NATO Ctr Maritime Res & Expt CMRE Res Dept I-19126 La Spezia Italy Univ Calif San Diego Scripps Inst Oceanog La Jolla CA 92093 USA Univ Calif San Diego Elect & Comp Engn Dept La Jolla CA 92093 USA TUWien Inst Telecommun A-1040 Vienna Austria

Multitarget tracking (MTT) is a challenging task that aims at estimating the number of targets and their states from measurements provided by one or multiple sensors. Additional information, such as imperfect estimates of target classes provided by a classifier, can facilitate the target-measurement association and thus improve MTT performance. In this letter, we describe how a recently proposed MTT framework based on the sum-product algorithm can be extended to efficiently exploit class information. The effectiveness of the proposed approach is demonstrated by simulation results.

关键词： Sensors Probability density function Target tracking Manganese sum product algorithm Indexes Sea measurements Classification factor graph multitarget tracking probabilistic data association sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Reduced Complexity sum-product algorithm for Decoding Nonlinear Network Codes and In-Network Function Computation

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2016年第10期64卷 4070-4082页

作者： Gupta, Anindya Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

While the capacity, feasibility, and methods to obtain codes for network coding problems are well studied, the decoding procedure and complexity have not garnered much attention. In this paper, we pose the decoding problem at a sink node in a network as a marginalize product function (MPF) problem over the Boolean semiring and use the sum product (SP) algorithm on a suitably constructed factor graph to perform iterative decoding. The number of operations required to perform SP decoding is reduced using traceback. The number of operations required to perform SP decoding with and without traceback is obtained. For nonlinear network codes, we define fast decodability of a network code at sinks demanding all the messages and identify a sufficient condition for the same. Next, we consider the network function computation problem wherein the sink nodes demand a function of the messages. We present an MPF formulation for function computation at the sink nodes and use the SP algorithm to obtain the value of the demanded function. Though the proposed method can be used for decoding both linear and nonlinear network codes, it is advantageous only for the case of nonlinear network codes.

关键词： Decoding in-network function computation network coding sum-product algorithm traceback

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：