Is SP BP? -- R. Tu, Y. Mao and J. Zhao, Submitted to IEEE Transactions on Information Theory, 2007
The Survey Propagation (SP) algorithm for solving k-SAT problems has been shown recently as an instance of the Belief Propagation (BP) algorithm. In this paper, we show that for general constraintsatisfaction problems, SP may not be reducible from BP. We also establish the conditions under which such a reduction is possible. Along our development, we present a unification of the existing SP algorithms in terms of a probabilistically interpretable iterative procedure — weighted Probabilistic Token Passing. Link to preprint in Arxiv.

On factor graphs and the Fourier Transform -- Y. Mao and F. R. Kschishcang, IEEE Transaction on Information Theory, Vol. 51, No. 5, May 2005 We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to “syndrome realizations” of codes, just as multiplicative factor graphs with auxiliary variables give rise to “state realizations.” We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient.We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case. Download the full article.

Convolutional Factor Graphs as Probabilistic models -- Y. Mao, F. R. Kschishcang and B. J. Frey, UAI 2004, Baff, AB, CanadaBased on a recent development in the area of error control coding, we introduce the notion of convolutional factor graphs (CFGs) as a new class of probabilistic graphical models. In this context, the conventional factor graphs are referred to as multiplicative factor graphs (MFGs). This paper shows that CFGs are natural models for probability functions when summation of independent latent random variables is involved. In particular, CFGs capture a large class of linear models, where the linearity is in the sense that the observed variables are obtained as a linear transformation of the latent variables taking arbitrary distributions. We use Gaussian models and independent factor models as examples to demonstrate the use of CFGs. The requirement of a linear transformation between latent variables (with certain independence restriction) and the observed variables, to an extent, limits the modelling flexibility of CFGs. This structural restriction however provides a powerful analytic tool to the framework of CFGs; that is, upon taking the Fourier transform of the function represented by the CFG, the resulting function is represented by a MFG with identical structure. This Fourier transform duality allows inference problems on a CFG to be solved on the corresponding dual MFG. Download the full article.

A Factor Graph Approach to Link Loss Monitoring in Wireless Sensor Networks -- Y. Mao, F. R. Kschishcang, B. Li and S. Pasupathy, IEEE Journal on Selected Areas in Communications, Vol. 23, No. 4, April 2005 The highly stochastic nature of wireless environments makes it desirable to monitor link loss rates in wireless sensor networks. In a wireless sensor network, link loss monitoring is particularly supported by the data aggregation communication paradigm of network traffic: the data collecting node can infer link loss rates on all links in the network by exploiting whether packets from various sensors are received, and there is no need to actively inject probing packets for inference purposes. In this paper, we present a low complexity algorithmic framework for link loss monitoring based on the recent modeling and computational methodology of factor graphs. The proposed algorithm iteratively updates the estimates of link losses upon receiving (or detecting the loss of) recently sent packets by the sensors. The algorithm exhibits good performance and scalability, and can be easily adapted to different statistical models of networking scenarios. In particular, due to its low complexity, the algorithm is particularly suitable as a long-term monitoring facility. Download the full article.

On the Design of Raptor Codes over Gaussian Channels -- Z. Cheng, J. Castura and Y. Mao, IEEE Transactions on Communications, 2008, to appear This paper studies the problem of Raptor-code design for binary-input AWGN (BIAWGN) channels using the mean-LLR-EXIT chart approach presented in a recent work. We report that there exist situations where such a design approach may fail or fail to produce capacity-achieving codes, for certain ranges of channel SNR. Suggestions and discussions are provided pertaining the design of Raptor codes for BIAWGN channels using the mean-LLR-EXIT chart. Download the preprint.

Performance-Complexity Tradeoffs of Raptor Codes over Gaussian Channels -- K. Hu, J. Castura and Y. Mao, IEEE Communications Letters, Vol. 11, No. 4, April, 2007 We investigate the performance-complexity tradeoffs of Raptor codes over Gaussian channels. Two different implementations of the Belief-Propagation (BP) decoding algorithm are considered, which we respectively refer to as “messagereset decoding” and “incremental decoding”. We show that incremental decoding offers great advantages over message-reset decoding in terms of this tradeoff. Download the full paper.

Rateless Coding for Wireless Relay Channels -- J. Castura and Y. Mao, IEEE Transactions on Wireless Communications, Vol. 6, No. 5, May 2007 We propose a novel coding framework for wireless relay channels based on rateless codes, which allows for a natural extension to multiple antenna and multiple relay settings. The relaying protocol is half-duplex, and relays independently choose when to collaborate, if at all. With a simulated fountain code based implementation of this framework, we show that the use of rateless codes is both robust and efficient when the channel state information is not available at the transmitters. Download the full article.

Informatics Platform for Global Proteomic Profiling and Biomarker Discovery Using Liquid Chromatography-Tandem Mass Spectrometry -- D. Radulovic, S. Jelveh, S. Ryu, T. G. Hamilton, E. Foss, Y. Mao and A. Emili, Molecular and Cellular Proteomics, Vol. 3, No. 10, October 2004
We have developed an integrated suite of algorithms, statistical methods and computer applications to support large-scale liquid-chromatography-tandem mass spectrometry-based gelfree shotgun profiling of complex protein mixtures using basic experimental procedures. The programs automatically detect and quantify large numbers of peptide peaks in feature-rich ion mass chromatograms, compensate for spurious fluctuations in peptide signal intensities and retention times, and reliably match related peaks across many different datasets. Application of this toolkit markedly facilitates pattern recognition and biomarker discovery in global comparative proteomic studies, simplifying mechanistic investigation of physiological responses and the detection of proteomic signatures of disease. Download the full article.