SHORT COURSE on CODING and OPTIMIZATION

SPEAKER: Dr. Pascal Vontobel (HP Labs)ABSTRACT: Whenever information is transmitted across a channel, we have to ensure its integrity against errors. The ground-breaking work of Shannon showed (at least theoretically) how such integrity can be achieved, namely by using an appropriately chosen encoder at the sender side and an appropriately chosen decoder at the receiver side.From a practical point of view, so-called low-density parity-check (LDPC) and turbo codes together with message-passing iterative decoders have become increasingly popular in the last decade. It is fair to say that these codes and decoding algorithms (and ideas related to them) have thoroughly changed much of modern communications. Before this backdrop, a good understanding of these types of communication techniques is obviously highly desirable, especially the understanding of iterative decoding of finite-length codes.Another interesting development in coding theory is the linear programming decoder that was recently proposed by Feldman, Karger, and Wainwright. Simulation results indicate that this decoding algorithm seems to have a similar decoding behavior as iterative decoding.Ideas from optimization theory have arguably played a key role in the two above-mentioned developments. This stems from the fact that decoding can be formulated as an optimization problem. Given that this optimization problem cannot be solved efficiently for good codes, one has to look for suboptimal, yet efficient, algorithms that approximately solve the optimization problem. Both message-passing iterative decoding and linear programming decoding can be seen as successful attempts to formulate such algorithms.Starting from the optimization setup, the first part of this tutorial will introduce message-passing iterative decoding and linear programming decoding and show how they are tightly connected. (This part of the tutorial is planned to be accessible to an broad audience with a general background in communication theory / decision theory.) The second part will go more into the details of certain topics as listed below.First Part: a) Motivation for coding theory, b) Factor graphs and message-passing iterative decoding, c) Linear programming decoding, d) Graph-cover decoding as a way to connect message-passing iterative decoding and linear programming decodingSecond Part: a) Geometry and properties of the fundamental cone, b) Pseudo-weights; lower bounds on the minimum pseudo-weight, c) Low-complexity algorithms for linear programming decoding, d) Bounds on the threshold of linear programming decoding(Based on joint work with Ralf Koetter, UIUC.)BIO: Pascal O. Vontobel received a diploma in electrical engineering in 1997, a post-diploma in information techniques in 2002, and a PhD degree in electrical engineering in 2003, all from ETH Zurich, Switzerland. After being a postdoctoral research associate at the University of Illinois at Urbana-Champaign, the University of Wisconsin-Madison (visiting assistant professor), and at the Massachusetts Institute of Technology, he joined the Information Theory Research Group at Hewlett-Packard Labs in Palo Alto, CA, in the summer of 2006 as a research scientist. For his PhD thesis he was awarded the ETH medal.He is interested in information theory and signal processing in general. More specifically, for his diploma thesis he worked on source coding. Since then, he has mainly looked at the construction of LDPC and turbo codes based on algebraic principles, the calculation and bounding of capacities and information rates of finite-state machine channels, and connections between factor graphs, the summary-product algorithm, and electrical networks. Most recently, he has worked towards an understanding and characterization of the summary-product algorithm on factor graphs with cycles and its connections to linear programming (LP) decoding.Host: Dr. Giuseppe Caire, caire@usc.edu

Location: James H. Zumberge Hall Of Science (ZHS) - 360

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher