Workshop on Information Theory and Wireless Communications (July 6, 2008)

9:00-9:30      Prakash Narayan

Title: The Poisson Fading Channel.

Abstract: A single-letter characterization of the capacity of a shot-noise limited Poisson fading channel is discussed when the receiver is provided with perfect channel state information (CSI) while the transmitter CSI can be imperfect. Properties of the optimal transmission strategies are also described. This talk is based on joint work with Kaushik Chakraborty.

Bio: Prakash Narayan received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Madras, in 1976, and the M.S. and D.Sc. degrees in Systems Science and Mathematics, and electrical engineering, respectively, from Washington University, St. Louis, MO, in 1978 and 1981.

Since 1981, he has been on the faculty of the University of Maryland, College Park, where he is Professor of Electrical Engineering with a joint appointment at the Institute for Systems Research.

His research and teaching interests are in multiuser information theory, communication theory, performance evaluation in communication networks, cryptography, and information theory and statistics.

9:30-10:00    Chao Tian

Title: Approximating the Gaussian Multiple Description Rate Distortion  Region.

Abstract: The rate-distortion characterization for the multiple description (MD) problem is a long standing open problem in information theory. In this talk, we make progress on this problem by giving an approximate characterization of the rate-distortion region for the Gaussian quadratic source. For an arbitrary number of descriptions, we focus on the symmetric-distortion-constrained problem. We show that the rate region can be sandwiched between two polytopes, between which the gap can be upper bounded by constants dependent on the number of descriptions, but independent of the exact distortion constraints. Underlying this result is an exact characterization of the lossless multi-level diversity source coding problem: a lossless counterpart of the MD problem. This connection provides a polytopic template for the inner and outer bounds of the rate region. In order to establish the outer bound, we introduce a new technique which requires a strategic expansion of the original probability space by more than one random variables.

As a consequence of this result, for the symmetric rate case with any number of descriptions, it can be shown that the gap between upper bound and lower bound for the individual description rate is no larger than 0.92 bit. We have also extended this approximation result to the asymmetric MD problem.

Joint work with Soheil Mohajer and Suhas Diggavi (EPFL).

Bio: Dr. Tian joined the Information and Software Systems Center at AT&T Labs-Research, Florham Park, New Jersey in 2007. He received the B.S. degree in Electronic Engineering from Tsinghua University, Beijing, China, in 2000 and the M.S. and Ph. D. degrees in Electrical and Computer Engineering from Cornell University, Ithaca, NY in 2003 and 2005, respectively. He was a postdoctoral researcher at Ecole Polytechnique de Lausanne (EPFL) in Switzerland from 2005 to 2007. His research interests include source coding, multiuser information theory, and image/video processing and coding.

10:00-10:30  Haim Permuter

Title: On Directed Information in Gambling, Stock Market and Data Compression.

Abstract: In the talk I will give a short overview on Massey's directed information, causal conditioning distribution, and their properties. Then we will study the problem of gambling in horse races with causal side information and will show that  directed information characterizes the increment in the maximum achievable capital growth rate due to the availability of side information. This result gives a natural interpretation of directed information $I(Y^n \to X^n)$ as the amount of information that $Y^n$ \emph{causally} provides about $X^n$. Extensions to stock market portfolio strategies and data compression with causal side information will be also discussed.

The talk is based on a joint work with Young-Han Kim and Tsachy Weissman.

Bio: Haim Permuter received his B.Sc. (summa cum laude)  in Electrical Engineering from the Ben-Gurion University. Since October 2004 he is a Ph.D. student in Electrical Engineering at Stanford University. He is a recipient of the Fulbright Fellowship and the Stanford Graduate Fellowship (SGF). Before coming to Stanford, Haim served as a scientific research officer in an R&D unit in the Israeli Defense Forces.

10:30-10:45  Coffee Break

10:45-11:15  Lei Zhao

Title: Zero-Error Capacity for Finite State Channels with Feedback and Channel State Information.

Abstract: We study the zero-error capacity for finite state channel with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of  a dynamic programming problem. Exact answers are also given for certain cases.

11:15-11:45  Tingting Liu

Title: Optimal Precoder Design for Correlated MIMO Communication Systems Using Zero-Forcing Decision Feedback Equalization.

Abstract: We consider the design of the precoder for a multi-input multi-output (MIMO) communication system equipped with a decision feedback equalizer (DFE) receiver. For such design problems, perfect knowledge of the channel state information (CSI) at both the transmitter and the receiver is usually required. However, in the environment of wireless communications, it is often difficult to provide sufficiently timely and accurate feedback of CSI from the receiver to the transmitter for such designs to be practically viable. In this paper, we consider the optimum design of a precoder for a wireless communication link having M transmitter antennas and N receiver antennas (M<N), in which the channels are assumed to be flat fading and may be correlated. We assume that full knowledge of CSI is available at the receiver. At the transmitter, however, only the first- and second-order statistics of the channels are available. Our goal here is to come up with an efficient design of the optimal precoder for such a MIMO system by minimizing the average arithmetic mean-squared error (MSE) of zero-forcing (ZF) decision feedback detection subject to a constraint on the total transmitting power. Applying some of the properties of the matrix parameters, this non-convex optimization problem can be transformed into a convex geometrical programming problem which can then be efficiently solved using an interior point method. The performance of the MIMO system equipped with this optimum precoder and a ZF-DFE has also been found to be comparable, and in some cases, superior to that of V-BLAST which necessitates optimally ordered successive interference cancellation based on the largest post-detection signal-to-noise ratio (SNR). In terms of trade-off between performance and implementation simplicity, our new system is certainly an attractive alternative.

Bio: Tingting Liu was born in Beijing, China. She attended Beijing Institute of Technology and was awarded the degree of Bachelor of Engineering (with distinction) in July 2006. She is currently pursuing the degree of Master of Applied Science in Telecommunication with the Department of Electrical and Computer Engineering, McMaster University, Canada. Her research interests include signal processing for communications, wireless communication systems, and optimization.


11:45-12:15  Tim Davidson


Title: A BICM-IDD Scheme for Non-Coherent MIMO Communication.


Abstract: This talk will describe the development of a transceiver for high-rate communication over the non-coherent multiple-input multiple-output (MIMO) channel. The transceiver architecture is that of
bit-interleaved coded modulation (BICM) with iterative demodulation and decoding (IDD), and the design exploits the underlying Grassmannian geometry of the signalling scheme that approaches the
ergodic capacity of the richly-scattered non-coherent model at high signal-to-noise ratios. In particular, this geometry guides the construction of the MIMO constellation and the mapper at the
transmitter, and gives rise to a computationally-efficient list-based soft demapping algorithm that substantially reduces the computational complexity of the receiver. Simulation results  demonstrate that at
high data rates the proposed scheme can provide significantly better performance than several training-based BICM-IDD schemes for the non-coherent MIMO channel.

This talk is based on joint work with Ramy Gohary and Mohamed El-Azizy.


Bio: Tim Davidson received the B.Eng. degree in Electronic Engineering from the University of Western Australia (UWA), Perth, in 1991 and the D.Phil. degree in Engineering Science from the University of Oxford, U.K., in 1995. He is currently an Associate Professor in the Department of Electrical and Computer Engineering at McMaster University, where he holds the (Tier II) Canada Research Chair in
Communication Systems, and is currently serving as Acting Director of the School of Computational Engineering and Science.

Dr. Davidson was awarded the 1991 J. A. Wood Memorial Prize for "the most outstanding (UWA) graduand" in the pure and applied sciences, and the 1991 Rhodes Scholarship for Western Australia. He
is currently serving as an Associate Editor of the IEEE Transactions on Signal Processing and as an Editor of the IEEE Transactions on Wireless Communications. He has also served as an Associate Editor
of the IEEE Transactions on Circuits and Systems II, and as a Guest Co-editor of issues of the IEEE Journal on Selected Areas in Communications and the IEEE Journal on Selected Topics in Signal


12:15-1:30    Lunch


1:30-2:00      Aaron Wagner


Title: Probability Estimation in the Rare-Events Regime.


Abstract: We address the problem of estimating the probability of an observed string drawn i.i.d. from an unknown distribution. Motivated by models of natural language, we consider the regime in which the
length of the observed string and the size of the underlying alphabet are comparably large. In this regime, the maximum likelihood distribution tends to overestimate the probability of the observed letters, so
the classical Good-Turing probability estimator is typically used instead. We show that the Good-Turing sequence probability estimator not consistent in this regime. We then introduce a novel
sequence probability estimator that is consistent. It is shown that this estimator can also be used to consistently estimate other quantities of interest and to develop a consistent universal classifier.

This is joint work with Pramod Viswanath and Sanjeev Kulkarni.


Bio: Aaron Wagner is an Assistant Professor in the School of Electrical and Computer Engineering at Cornell University. He received the B.S. degree from the University of Michigan, Ann Arbor, and the M.S. and Ph.D. degrees from the University of California, Berkeley. During the 2005-2006 academic year, he was a Postdoctoral Research Associate in the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign and a Visiting Assistant Professor in the School of Electrical and Computer Engineering at Cornell. He has received the NSF CAREER award, the David J. Sakrison Memorial Prize from the U.C. Berkeley EECS Dept., and the Bernard Friedman Memorial Prize in Applied Mathematics from the U.C. Berkeley Dept. of Mathematics.


2:00-2:30      Tsachy Weissman

Title: Rate-Distortion, Noise Removal, and MCMC.

Abstract: I will start by recalling some connections between rate-distortion and denoising, explaining why optimal rate-distortion coding of noisy data, under the right distortion measure and level, results in ‘sampling from the posterior’, which in turn can be harnessed simply to achieve optimum denoising.

These observations, combined with a recently developed approach to universal lossy compression via Markov Chain Monte Carlo (MCMC), lead to a new family of universal denoisers. This family compares favorably (both theoretically and in practice) with other MCMC-based schemes, and provides an alternative to the Discrete Universal Denoiser (DUDE).

Based on joint work with Shirin Jalali (Stanford University).

Bio: Tsachy Weissman received the B.Sc. and Ph.D. degrees in electrical engineering from the Technion in 1997 and 2001, respectively. He has held postdoctoral appointments with the statistics department at Stanford University and with Hewlett-Packard Laboratories. He has joined the faculty of the electrical engineering department at Stanford University in 2003. He has been also with the department of electrical engineering at the Technion since the summer of 2007. Tsachy’s research interests span information theory and its applications, and statistical signal processing. His papers have focused mostly on data compression, prediction, denoising, communications, and learning. He is also inventor or co-inventor of several patents in these areas. In addition to his academic activities, Tsachy is a consultant to several high-tech companies. Among other prizes, Tsachy was awarded the Clore Foundation scholarship, the Rothschild Foundation scholarship for postdoctoral studies, the NSF CAREER award, and a Horev fellowship. He was a Robert N. Noyce Faculty Scholar of the School of Engineering at Stanford University, and is a recipient of the 2006 IEEE joint IT/COM societies best paper award.

2:30-3:00      Chih-Chun Wang


Title: Recent Graph-Theoretic Progress of Network Coding --- from Characterization Theorems to New Graph Algorithms.

Abstract: This talk reviews briefly the recent graph-theoretic progress of network coding. Specifically, two important open problems are discussed: the characterization theorems for {\em intersession network coding} and a new class of network-coding-based max flow algorithms for {\em intrasession network coding}. These results reveal a stronger connection between network coding and graph-theoretic research. The corresponding impacts are discussed from both the perspectives of theoretic understanding and practical implementation of network coding.

Bio: Chih-Chun Wang joined the School of Electrical and Computer Engineering in January 2006 as an Assistant Professor. He received the B.E. degree in E.E. from National Taiwan University, Taipei, Taiwan in 1999, the M.S. degree in E.E., the Ph.D. degree in E.E. from Princeton University in 2002 and 2005, respectively. He worked in Comtrend Corporation, Taipei, Taiwan, as a design engineer during in 2000 and spent the summer of 2004 with Flarion Technologies, New Jersey. In 2005, he held a post-doc position in the Electrical Engineering Department of Princeton University. His current research interests are in the graph-theoretic and algorithmic analysis of iterative decoding and of network coding. Other research interests of his fall in the general areas of optimal control, information theory, detection theory, coding theory, iterative decoding algorithms, and network coding.


3:00-3:15      Coffee Break


3:15-3:45      Mohamed D. A. Mohamed and Ahmed Farid


Title: Wireless Optical Intensity Channels: Ideas on Modulation and Capacity.


Abstract: The talk considers modulation design and capacity bounds for dispersive and non-dispersive wireless optical channels.

For non-dispersive line-of-sight channels, upper and lower bounds for optical channel capacity under nonnegativity and average optical power constraints are derived. Intensity modulated direct detection (IM/DD) channels and pulse amplitude modulation (PAM) are considered.  Utilizing signal space geometry and a sphere packing argument, an upper bound is derived, while a lower bound is derived based on source entropy maximization over discrete distributions. The proposed distribution provides tighter lower bound compared to the bound obtained from a continuous distribution. The derived bounds asymptotically describe the optical capacity at both low and high SNR.

For the dispersive indoor wireless optical channel, a power efficient modulation scheme, called Optical impulse modulation (OIM), is introduced. OIM, with a simple lowpass receiver, provides a significant gain in optical average power over conventional rectangular modulation schemes that use the relatively complex whitened matched filter receiver. The information rates of OIM on typical ISI channels are demonstrated to be significantly greater than conventional approaches.

Bio: Mohamed Darwish A. Mohamed received the B.Sc. degree (with honors) in electronics and communication engineering, and the M.Sc. degree in engineering mathematics from Cairo University, Giza, Egypt, in 2001 and 2004, respectively. In 2005, he joined the Department of Electrical and Computer Engineering at McMaster University, Hamilton, Ontario, Canada, and is currently working toward the Ph.D. degree in electrical engineering. He worked as a Teaching Assistant with the Department of Engineering Mathematics and Physics, Faculty of Engineering, Cairo University, from 2001 to 2004, and with the Department of Electrical and Computer Engineering, McMaster University, from 2005 to present. His field of interest includes digital communications, signal processing, and coding and modulation for wireless optical communication links.

Ahmed Farid received the B.Sc. and M.Sc. in Electrical Engineering from Alexandria University, Egypt and M.A.Sc in Electrical Engineering from McMaster University, Canada where he is currently pursuing the Ph.D. degree. His current research interests are wireless optical communications, information theory, coding and modulation, and channel modeling for free-space optical links.

3:45-4:15      Young-Han Kim


Title: The Value of One-Bit Feedback.

Abstract: It is well known that feedback can improve the quality of communication in several important ways -- feedback can increase the capacity, reduce the probability of error, decrease communication delay, and even simplify the system design. Nonetheless, in order to understand the value of feedback in two-way communication as a whole, we should take into account the cost of feedback itself. For example, it is easy to see that the capacity of forward channel never increases by more than the entropy H(Y) of the channel output Y, the minimum data rate required for sending the received output over the backward channel. Thus in terms of capacity, perfect output feedback apparently does not break even.

What will happen if we feed back a summary of Y instead? What would make the most efficient description of Y that is relevant to the forward communication? Is one-bit feedback really worth one bit?

This talk addresses partial answers to these questions by going through a few classical and new examples in multiple user channels. A special attention will be paid to the analogy between the value of channel state information and the value of feedback.

Bio: Young-Han Kim is an assistant professor in the Department of Electrical and Computer Engineering at the University of California, San Diego. He received his B.S. degree with honors in Electrical Engineering from Seoul National University, Korea, in 1996, where he was a recipient of the General Electric Foundation Scholarship. After a three-and-half-year stint as a software architect at Tong Yang Systems, Seoul, Korea, working on several industry projects such as developing the communication infrastructure for then newly opening Incheon International Airport of Korea, he resumed his graduate studies at Stanford University, Stanford, CA, and received his Ph.D. degree in Electrical Engineering (M.S. degrees in Statistics and Electrical Engineering) in 2006. Prof. Kim's research primarily focuses on network information theory and the role of feedback in communication networks. More broadly, he is interested in statistical signal processing and information theory, with applications in  communication, control, computation, networking, data compression, and learning. He is a recipient of the 2008 National Science Foundation Faculty Early Career Development Award.

4:15-4:45      Yossef Steinberg


Title: A Framework for Successive Information Embedding.


Abstract: Successive coding has traditionally been investigated in the context of source coding. To some extent, the degraded broadcast channel can be viewed as its counterpart in the realm of channel coding. In this work a general framework for successive information embedding will be presented. Its implications to various watermarking problems, including private and public watermarking, reversible information embedding (RIE), and information embedding with distortion constraints at the output, will be discussed. The general idea is that of a sequence of (possibly correlated) messages embedded in a sequence of correlated host signals, which can present, for example, a sequence of images in a video stream. I will present preliminary results on a few of these models, and discuss future research directions.


Bio: Yossef Steinberg received the Ph.D. degree in electrical engineering from Tel-Aviv University, Tel Aviv, Israel. He was a Lady Davis Fellow in the Department of Electrical Engineering, Technion – Israel Institute of Technology, Haifa, Israel, and held visiting appointments in the Department of Electrical Engineering at Princeton University, Princeton, NJ, and at the C I Center, George Mason University, Fairfax, VA. From 1995 to 1999, he was with the Department of Electrical Engineering, Ben Gurion University, Beer-Sheva, Israel. In 1999, he joined the Department of Electrical Engineering at the Technion. His research areas are information theory, statistical communications, and statistical signal processing. Yossi Steinberg served as Asociate Editor for Shannon Theory in the IEEE Transactions on Information Theory, and won the 2007 IEEE IT best paper award, jointly with Hanan Weingarten and Shlomo Shamai.


4:45-5:15      Michael Botros Shenouda


Title: A Unified Deign Framework for Non-Linear MIMO Transceivers  with Perfect or Limited Channel State Information.


Abstract: Non-linear MIMO transceivers have the potential for considerable gains over linear transceivers, while maintaining a comparable complexity. These gains are achieved by implementing interference (pre) subtraction at either the transmitter, such as Tomlinson-Harashima Precoding (THP) systems, or at the receiver, such as Decision Feedback Equalization (DFE) systems.  However, for many of the design criteria for which (jointly) optimal linear transceivers are known, the optimal non-linear transceiver has remained an open problem. Furthermore, the development of a unifying design framework for non-linear transceivers, that complements an existing framework of their linear counterparts,  has appeared to be a challenging problem.


In this talk, we present unified design framework for the two dual non-linear MIMO systems: MIMO transceivers with Tomlinson-Harashima precoding and those with Decision Feedback Equalization. It uses concepts from majorization theory and convex optimization theory to develop optimal closed-form designs for a broad range of unsolved design objectives. It also characterizes the scenarios under which the designed non-linear transceivers are (strictly) superior to their linear counterparts. Furthermore, the framework extends to communication schemes that employ non-linear transceivers with limited channel state information (finite-rate feedback) using concepts from Grassmannian packings.


Bio: Michael Botros Shenouda received the B.Sc. (Hons. 1) degree in 2001 and the M.Sc. degree in 2003, both in electrical engineering. He is currently working toward the Ph.D. degree at the Department of Electrical and Computer Engineering, McMaster University, Canada.  His main areas of interest include wireless and MIMO communication, convex and robust optimization, and signal processing algorithms. He is also interested in majorization theory, and its use in the development of design frameworks for non-linear MIMO transceivers. Mr. Botros Shenouda was awarded an IEEE Student Paper Award at ICASSP 2006, and was a finalist in the IEEE Student Paper Award competition at ICASSP 2007.