A Semester of Seminars on Information Theory, Networks and Signal Processing at Cornell

---

Speaker:

Sergio Servetto.

Title:

A Modular Architecture for Data Archiving Applications in Sensor Networks.

Abstract:

We consider the problem of data archiving in sensor networks: this is the problem of periodically gathering snapshots of the state of the data field observed by the network, and storing them in a central repository for later data analysis. Moving high-fidelity encodings of raw sensor readings out of the network (as opposed to functions of these readings), especially at this early stage in the deployment of such networks, is a critical task: it is often the case that the characteristics of the signals observed are unknown, and that the whole purpose of deploying a sensornet is to observe and analyze these raw, minimally processed signals.

In this talk, we will discuss the design of a complete system for data archiving. A salient feature of our system is its modular architecture that enables easy reconfigurability, an architecture that is solidly grounded in pure information theoretic concepts. Simulation results, as well as our first "real" results (collected in a real deployment consisting of 16 Mica2 motes), seem to suggest that the performance achieved by our system is at least competitive with that of state-of-the-art, vertically integrated systems.

(Joint work with Joao Barros, Yong Yao and Johannes Gehrke.)

---

Speaker:

Sergio Verdú.

Title:

Noiseless Data Compression with Error Correcting Codes.

Abstract:

In this talk I will present new schemes for noiseless data compression based on modern random-like codes such as low-density parity-check codes, fountain codes and belief propagation decoding. Comparisons of these schemes with the state of the art in nosieless data compression will be given shown regarding compression ratio and resilience to errors. Related algorithms for interactive data exchange and coding with feedback will also be presented.

(Joint work with Giuseppe Caire and Shlomo Shamai.)

---

Speaker:

Babak Hassibi.

Title:

Some Results in Wireless Networks.

Abstract:

There has been a great deal of recent interest in studying the capabilities of wireless ad hoc networks. While given all the vagaries of the wireless medium (fading, mobility, path-loss, etc.), "exact" information-theoretic capacity results seem beyond reach, recent progress has been made for certain idealized models. This talk will discuss two such models.

The first is the so-called wireless erasure network where all links are modeled as (possibly correlated) packet erasure channels. Such a model may be appropriate for systems where all transmissions are packet-based and some form of error-control is employed so that packets are either received error-free or dropped entirely. For such networks we give an exact capacity result for the multi-cast problem (one transmitter sending the same information to many users). In particular, we show that, by giving appropriate side information to the receivers, the standard cut-set bounds become achievable. We will discuss the implications of this result, as well as connections to other topics such as network coding.

The second is the so-called random wireless network where all the fading coefficients between the network nodes are drawn iid from a given distribution. This model is appropriate for ad hoc networks of small physical size where the dominant factor determining channel strengths is a random event (such as the existence of an obstacle), rather than the distance between the transmitter and receiver. For such networks we show that the throughput scaling is heavily influenced by the distribution from which the fading coefficients are drawn. For a wide class of distributions, we show that throughput scales as O(n/log^a n), for some fixed a>1, which is a substantial improvement over the O(\sqrt{n}) scaling obtained from path-loss models such as that of Gupta and Kumar. We finally generalize the models to physically larger networks where at a "local" scale channels are drawn iid and at a "global" scale they are determined by a path-loss model. We again obtain throughput scaling laws that are favorable to O(\sqrt{n}).

---

Speaker:

Greg Wornell.

Title:

When Network Theorists Think Like Leeches.

Abstract:

Many networks are overprovisioned in one or more resources. The associated surpluses can often be exploited to create parasitic bit pipes by opportunistic resource scavenging algorithms. By examining some associated fundamental limits, we investigate the degree to which global resource efficiency is possible when such scavenging is subject to the required transparency constraints. While bandwidth scavenging may be what first comes to mind, we focus on the equally important cases in which there are surpluses in channel quality (which can allow, e.g., a form of energy scavenging at the physical layer) or content fidelity (which can be exploited through forms of requantization at the application layer). In both cases, we show suitably designed scavenging algorithms can be at least nearly globally efficient. In the process, we analyze a meaningful game-theoretic model for the successive degradation problem of transcoding. More generally, our analysis also provides other insights for designers of practical source codes and channel codes.

Based on recent joint work with Aaron Cohen, Stark Draper, and Emin Martinian, as well as earlier joint work with Brian Chen.

---

Speaker:

Yoram Bresler.

Title:

Sampling Theory and Adaptive Acquisition for Cardiac Magnetic Resonance Imaging.

Abstract:

Heart disease is the main cause of death in the western world. Early diagnosis, therapy management, and surgical intervention all require improved methods for cardiac imaging. Cardiac Magnetic Resonance Imaging (CMRI) holds the promise of replacing the gold standard of invasive catheterization and x-ray imaging by benign radio frequency waves and magnetic fields. However, MR imaging of the beating heart is a significant technological challenge. While CMRI is already a clinical tool in hospitals, it does not offer sufficient temporal resolution, its spatial resolution is insufficient to discern small blocked arteries, and it requires long breath-holds that can not be performed by infants or the sick.

We describe a model-based approach for real-time cardiac imaging that does not require cardiac gating. Unlike previous methods, the current approach produces a movie ("cine") in which each reconstructed heartbeat is temporally resolved, rather than being a composite or weighted average of multiple actual heartbeats. The model used in the method captures the spatial and temporal-spectral characteristics of the heart. The model parameters are estimated as part of the MRI experiment and drive both data acquisition and cine reconstruction algorithm. The approach relies on a formulation of Dynamic MRI as a time-sequential sampling (TSS) problem, where only one sample in k-space can be acquired at any one time. The TSS theory provides a design for minimum redundancy data acquisition and reconstruction optimized for the dynamic object being imaged. The approach can produce a high temporal and spatial resolution movie of the heart, with multifold reduction in acquisition rate requirements compared to conventional methods. The method is demonstrated by simulation and in-vivo experiments. An extension of the method enables ungated free-breathing real-time cardiac imaging, by accounting in the model for both cardiac and respiratory motion during imaging.

Work with: Nitin Aggarwal, Qi Zhao, Saptarshi Bandyopadhyay

---

Speaker:

Anant Sahai.

Title:

Delay, Feedback, and the Price of Ignorance.

Abstract:

In 1959, Shannon made a profound comment:
"[The duality between source and channel coding] can be pursued further and is related to a duality between past and future and the notions of control and knowledge. Thus we may have knowledge of the past and cannot control it; we may control the future but have no knowledge of it."
This comment cannot be understood in the traditional block-code setting and as a result, has remained entirely mysterious. To understand it, we must step back and consider end-to-end delay, since delay is what fundamentally allows the exploitation of the laws of large numbers to give reliability.

In channel coding, we show that while feedback often does not improve fixed block-length reliability functions, it can significantly improve the reliability with respect to fixed delay! (Contrary to a "theorem" by Pinsker claiming otherwise.) A new bound, that we call the "focusing bound," allows us to calculate the limit of what is possible when the encoder is not ignorant of the channel's past behavior. In source coding, the price of ignorance is demonstrated by considering what happens when receiver side-information is withheld from the transmitter. Block-codes perform equally poorly, but nonblock codes can use side- information to dramatically improve the fixed-delay error exponent. Furthermore, a closer look at the dominant error events for these cases gives Shannon's otherwise cryptic comment a precise interpretation.

These results suggest that the traditional information theoretic recommendation of using messages as big as possible is flawed as far as architectural guidance is concerned. When encoders are not ignorant, messages should be as *small* as possible while avoid integer effects, and queueing ideas should be employed to do appropriate flow control, even when facing hard end-to-end latency constraints.

---

Speaker:

Tom Schneider.

Title:

Molecular Information Theory: From Clinical Applications to Molecular Machine Efficiency.

Abstract:

Information theory was introduced by Claude Shannon in 1948 to precisely characterize data flows in communications systems. The same mathematics can also be fruitfully applied to molecular biology problems. We start with the problem of understanding how proteins interact with DNA at specific sequences called binding sites. Information theory allows us to make an average picture of the binding sites and this can be shown with a computer graphic called a sequence logo.

Sequence logos show how strongly parts of a binding site are conserved, in bits of information. They have been used to study a variety of genetic control systems. More recently the same mathematics has been used to look at individual binding sites using another computer graphic called a sequence walker. Sequence walkers are being used to predict whether changes in human genes cause mutations or are neutral polymorphisms. It may be possible to predict the degree of colon cancer by this method.

Information theory can also be used to understand the relationship between the binding energy dissipated when two molecules stick together and the amount of sequence conservation of the molecules measured in bits. Using the Second Law of Thermodynamics, this relationship can be expressed as the efficiency of the molecular interaction. Surprisingly, many molecular systems including genetic systems, visual pigments and motility proteins have efficiencies near 70%. A purely geometrical explanation of this result shows that although biological systems are selected to have the highest efficiency, it is restricted to 70% because having precisely distinguishable molecular states is more important.

---

Speaker:

Venu Veeravalli.

Title:

Tracking with Sleepy Sensors.

Abstract:

We study the problem of tracking an object that is moving randomly through a dense network of wireless sensors. We assume that each sensor has a limited range for detecting the presence of the object, and that the network is sufficiently dense so that the sensors cover the area of interest. In order to conserve energy the sensors may be put into a sleep mode with a timer that determines the sleep duration. We assume that a sensor that is asleep cannot be communicated with or woken up. Thus the sleep duration needs to be determined at the time the sensor goes to sleep based on all the information available to the sensor. The objective is to track the location of the object to within the accuracy of the range of the sensor. Having sleeping sensors in the network could result in tracking errors, and hence there is a tradeoff between the energy savings and the tracking error that result from sleeping. We consider the design of sleeping policies that optimize this tradeoff.

---

Speaker:

Prakash Narayan.

Title:

Multiterminal Data Compression and Secret Key Generation.

Abstract:

Consider a situation in which multiple terminals observe separate but correlated signals. In a multiterminal data compression problem, a la the classic work of Slepian and Wolf, each terminal seeks to acquire the signals observed by all the other terminals by means of efficiently compressed interterminal communication. This problem does not involve any secrecy constraints. On the other hand, in a secret key generation problem, the same terminals seek to devise a ``common secret key" through public communication, which can be observed by an eavesdropper, in such a way that the key is concealed from the eavesdropper. Such a secret key can be used for subsequent encryption. We explain the innate connections that exist between these two problems and explore a constructive approach to secret key generation based on muliterminal data compression techniques.

This talk is based on joint work with Imre Csiszar and Chunxuan Ye.

---

Speaker:

Joao Barros.

Title:

Information-Theoretic Security in Wireless Networks: From Theory to Practice.

Abstract:

Recent theoretical and practical work has shown that novel physical layer security techniques have the potential to significantly strengthen the security of wireless networks. In the first part of this talk we will briefly review the fundamentals in information-theoretic security and discuss our most recent results. Formulating the problem as one in which two legitimate partners communicate over a quasistatic fading channel and an eavesdropper observes their transmissions through another independent quasi-static fading channel, we define the secrecy capacity in terms of outage probability and provide a complete characterization of the maximum transmission rate at which the eavesdropper is unable to decode any information. In sharp contrast with known results for Gaussian wiretap channels (without feedback), our results show that in the presence of fading information-theoretic security is achievable even when the eavesdropper has a better average signal-to-noise ratio (SNR) than the legitimate receiver.

In the second part of the talk, we will propose a practical security scheme by which two terminals (say Alice and Bob) are able to exploit the randomness of wireless fading channels to exchange data in an information-theoretically secure way. To ensure that a potential eavesdropper (say Eve) is unable to decode any useful information, Alice sends useful symbols to Bob only when the instantaneous secrecy capacity is strictly positive. In the remaining time, a specially designed class of LDPC codes is used for reconciliation, thus allowing the extraction of a secret key, which can be distilled using privacy amplification. We believe this opportunistic approach can be used effectively as a physical layer complement to existing cryptographic protocols.

Joint work with Miguel Rodrigues, Matthieu Bloch and Steve McLaughlin.

---

Speaker:

Andrea Goldsmith.

Title:

Capacity, Cooperation, and Cross-Layer Design in Wireless Networks.

Abstract:

We consider fundamental capacity limits in wireless networks where nodes can cooperate in transmission, reception, and routing. We propose novel cooperation techniques that approach the capacity bounds, including virtual MIMO transmission, relaying, and conferencing. The optimal cooperation strategy is cross-layer in nature and depends on the network topology, the channel SNR, and the channel side information available at the nodes. Moreover, when the network is constrained in energy or delay, cross-layer design is critical and leads to surprising forms of cooperation. We conclude with a discussion on combining cooperative compression and signal processing with cooperative communication, a form of joint source/channel/network coding.

---

Speaker:

Pablo Parrilo.

Title:

SOS/SDP Methods: From Optimization to Games.

Abstract:

In the last few years, techniques based on sum of squares (SOS) decompositions of multivariate polynomials, semidefinite programming (SDP), and results from real algebraic geometry have proved extremely useful in the formulation of hierarchies of convex relaxations for difficult polynomial optimization problems. In this talk we show how these can be extended to a game theoretic setting. In particular, we discuss a class of zero-sum two-person games with an infinite number of pure strategies, where the payoff function is a polynomial expression of the actions of the players. We show that the value of the game, and the corresponding optimal strategies, can be computed by solving a single semidefinite program, thus providing a natural generalization of the well-known LP characterization of finite games. We also study the possible extensions to correlated equilibria, and to the nonzero sum case. In addition, we show how the results can be applied, with suitable modifications, to a general class of semialgebraic games and problems with two quantifiers.

---

Speaker:

Marcelo Weinberger.

Title:

Discrete Universal Denoising: From Information Theory to Imaging Applications.

Abstract:

A discrete denoising algorithm estimates the input sequence to a discrete channel based on the observation of the entire output sequence. The discrete denoising problem was recently studied in a universal, information-theoretic setting, in which the channel is memoryless and no knowledge of the statistical properties of the input sequence is assumed. A low-complexity, discrete denoising algorithm (the "Dude") was proposed, which is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution.

Although the above asymptotic properties apply to any finite alphabet, their application in the non-asymptotic regime when the alphabet is very large (e.g., continuous-tone images) presents significant challenges, similar to those encountered in lossless image compression. As in the compression problem, a key component of the Dude framework is the determination of a probability distribution for the observations, conditioned on their contexts.

In this talk, we will review the Dude in its pure information-theoretic form. We will then discuss the challenges posed by continuous-tone images, and present the modeling tools used to address these challenges. Finally, we will show results obtained with the enhanced Dude framework on a variety of images. Just as lossless image compression, universal denoising exemplifies the delicate balance between universality in an information-theoretic sense and the art of data modeling. We will discuss the lessons learned from information-theoretic analysis, and how the theory should guide artisan modeling decisions.

---

Speaker:

Frederique Oggier.

Title:

Algebraic Distributed Space-Time Coding.

Abstract:

Recently, attention has been focused on wireless networks. Methods to exploit diversity using the antennas of different users in a cooperative way have been studied, in order to look for the diversity known to be achieved in the multiple antennas point to point case.

We consider a wireless network where a transmitter and a receiver are distinguished, with enough computational capacity and power to encode/decode the data, and use several antennas to transmit/receive the signal. The other nodes are relays, small devices with few power and computational ability, with only one antenna (as for example in sensor networks). In this scenario, it is not realistic to assume nodes can decode the information. We thus propose a strategy based on the idea of Distributed Space-Time Coding, where the nodes just do a very simple operation before forwarding the information. Our scheme relies on known algebraic Space-Time Codes. It is suitable for any number of transmit/receive antennas and nodes. It is shown to perform better than random codes, with less encoding complexity. We also briefly discuss the scenario where nodes may be down in the network, and show that our strategy is resistant to node failures.