Biography

Pascal O. Vontobel received the Diploma degree in electrical engineering in 1997, the Post-Diploma degree in information techniques in 2002, and the Ph.D. degree in electrical engineering in 2003, all from ETH Zurich, Zurich, Switzerland.

From 1997 to 2002, he was a Research and Teaching Assistant at the Signal and Information Processing Laboratory at ETH Zurich. After being a Postdoctoral Research Associate at the University of Illinois at Urbana-Champaign, at 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 Laboratories in Palo Alto, CA, in the summer of 2006 as a research scientist. His research interests lie in information theory, communications, and signal processing.

He has been on the technical program committees of several international conferences, he has recently co-organized a BIRS workshop in Banff, and he has also been twice a plenary speaker at international information and coding theory conferences. Dr. Vontobel was awarded the ETH medal for his Ph.D. dissertation.

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.

The aim of this tutorial is to review the basics of the above mentioned topics, to present some new results, and, most importantly, to shed new light on older results by suitably reformulating them and by giving more intuitive (yet mathematically precise) explanations for them.

Audience background: for this presentation it is of advantage to be familiar with the rudimentary basics of channel coding, and to possibly have encountered a subset of concepts like factor graphs, message-passing iterative decoding, and linear programming decoding. However, a deep understanding of these concepts is not a requisite.

Biography

Dr. Chee Wei Tan is an Assistant Professor at the City University of Hong Kong. Prior to that, he was a Postdoctoral Scholar at the California Institute of Technology (Caltech). He received his Ph.D. degree in Electrical Engineering from Princeton University. He was a Research Associate at Fraser Research Laboratory in 2005 and a Visiting Scholar at the Coordinated Science Laboratory of UIUC in 2007. Dr. Tan received the 2008 Princeton Wu Prize for Excellence and the 2001 Siemens International Scholarship. His research interests are in wireless and broadband communications, networking and distributed systems, Green IT, signal processing, information theory and nonlinear optimization.

Objectives:

1. The students will acquire a state-of-the-art functional knowledge of convex optimization theory, which allows them to appreciate real-world applications.
2. Show how nonlinear problems in communication networks can be formulated and solved as various forms of convex optimization.
3. Introduce the tools of convex optimization and Lagrange duality. Study its theoretical properties and computational algorithms as applied to the analysis and design of communication systems.
4. The course follows a case-study approach by considering recent successful applications published within the last ten years in prestigious scientific journals and in industry.

Logistics:

1. Prerequisite: basic matrix algebra and probability, and a strong desire to learn. No need to have previous exposure to optimization.
2. Textbooks:
   1. Convex Optimization (S. Boyd and L. Vandenberghe) and Nonlinear Programming (D. P. Bertsekas)
   2. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (A. Ben-Tal and A. Nemirovski) and Introductory Lectures on Convex Optimization: A Basic Course (Y. Nesterov)

Curriculum:

1. Overview of convex optimization
   1. Theoretical structures
   2. Lagrange duality approach
   3. Computational algorithms
2. Basic theory: Convex functions and convex sets
3. Basic theory: Linear programming
4. Convex optimization theory: quadratic programming and geometric programming
5. Convex optimization theory: conic programming and semidefinite programming
6. Convex optimization theory: Pareto optimization and optimal tradeoff
7. Detection, equalization and antenna beamforming problems
8. Lagrange duality of convex optimization: dual problems
9. Lagrange duality of convex optimization: Karush-Kuhn-Tucker optimality conditions
10. Theory of decomposition approaches: Primal and dual decomposition
11. Application: Linear transceiver design in MIMO channels
12. Application: Internet congestion control and network utility maximization
13. Application: Power control problems in wireless network
14. Algorithms for smooth and unsmooth unconstrained optimization
15. Nonconvex Optimization: Compressed sensing and single-path routing
16. Industry case studies: Conclusions on using convex optimization to understand and solve nonlinear problems in communication networks