Young-Han Kim  —  Research Overview

My research is focused on two important aspects of information processing  —  efficient description of data and reliable transmission of it. Together they span a wide spectrum of problems in statistical signal processing and information theory, motivated by practical challenges as well as theoretical curiosity. I explore fundamental principles behind the theory of information processing and provide implementable guidelines for practice.

Details of the current projects follow:

The role of feedback in two-way communication networks

Feedback is a pivotal element in many control and learning systems. Without feedback (or interaction between the observer and controller), even a tiny bit of error can destabilize a control system in stochastic environments. No one would willingly drive any reasonable distance with their eyes closed. Similarly, feedback (or interaction between the supervisor and learner) plays a crucial role in pattern classification or prediction — and at school in the form of exams. In this context, communication systems, in which one “controls” the other’s state of knowledge — or conversely, one “learns” the other’s intended message — are notable exceptions. As Shannon showed, one can communicate reliably without any feedback by encoding data in forward error correcting codes and sending it in long blocks. Through many breakthroughs in coding techniques over the past sixty years, several one-way communication systems such as blueray discs and deep-space probes nowadays can achieve performance close to the theoretical limit set by Shannon’s information theory.

Evolution of communication networks and emerging applications, however, bring up new challenges beyond this nonadaptive communication paradigm. Many communication situations occur over wireless networks and the Internet, in which interactivity of multiple users result in a rich dynamic environment. Hence, feedback (or interaction between the encoder and decoder) again plays an essential role in adapting communication to network dynamics, which is in certain cases imperative in order to maintain reliable communication and in general advantageous in improving the quality of communication. At the same time, modern applications — such as distributed multimedia, sensor networks, networked control systems, and peer-to-peer computing — demand simple, real-time, and interactive communication, which cannot be addressed by treating a communication network as a mere collection of one-way point-to-point links and employing traditional forward error correction techniques.

In order to meet these challenges, we investigate new paradigms of interactive feedback communication over networks and provide a common set of analytical and algorithmic tools derived from the following problems:

1. Capacity of channels with feedback and two-way channels

2. Practical feedback coding techniques

3. The role of Massey’s directed information in causal inference

4. Adaptive algorithms for signal processing

Feedback is a universal notion in many scientific and engineering disciplines and a deeper understanding of its role in one discipline (communication) will lead to a better understanding of its role in a broader multidisciplinary context.

This research is supported in part by the National Science Foundation under grant CCF-0729195 (co-PI: Tsachy Weissman at Stanford).

Network information theory: Coding for communication, control, and computing

Despite significant advances in information theory and its application to point-to-point communications, a general theory governing optimal information flow over networks does not yet exist. Except for a few simple network models, the capacity region of a general memoryless network remains unknown, due to the complex tradeoff between competition and cooperation among many nodes in the network. Modern applications such as sensor networks, peer-to-peer systems, and distributed storages further bring up a new set of challenging problems spanning control, estimation, compression, computation, communication, as well as networking.

This research program provides a common set of conceptual, mathematical, and algorithmic tools for the emerging convergence of computation, control, and communication over networks, with the ultimate goal of developing a unified framework for characterizing fundamental performance limits of such systems.

This research is supported in part by the National Science Foundation under grant CCF-0747111 (Faculty Early Career Development Award).