Speaker: Yongyi Mao, University of Ottawa
Time:    Monday November 10, 11:00-12:00
Place:   Room STE-5084, SITE, University of Ottawa
Title:   Duality in Factor Graphs

Abstract:
A factor graph is a bipartite graph representation of a multivariate 
function which factors as a product of a set of local functions, each 
involving only a subset of the variables. The framework of factor graphs 
has now become the foundation of a modern subject of error correction coding, 
codes on graphs. 

In this talk, I will present an extension of the factor graph framework
by introducing a new type of factor graphs, called convolutional factor 
graphs, which represent the convolutional factorization of a multivariate 
function. We show that just like conventional (multiplicative) factor 
graphs naturally arising from image representation of codes, convolutional 
factor graphs naturally arise from kernel representations of codes. A 
Fourier transform (or Pontryagin) duality can be naturally associated with 
a multiplcative factor graph and an isomorphic convolutional factor graphs, 
and we call such a pair of factor graphs a pair of dual factor graphs. We 
show that when a factor graph represents a primal code, its  dual factor 
graph represents the dual code. I will also present an interesting 
implication of this duality result in the context of probabilistic 
graphical models,  where we brought to surface an unexplored fundamental 
propery that is dual to the well-known Markov property.