UC San Diego Professor Wins Top Information Theory Award

Article Content

ECE professor and ITA member Young-Han Kim, winner of the 2012 Information Theory Paper Award

Using powerful mathematical techniques from information theory, linear systems theory, convex optimization, and functional analysis, a professor of electrical and computer engineering at the University of California, San Diego resolved a 40-year-old open problem in the field of communication.

Professor Young-Han Kim tackled the problem in a paper titled, “Feedback capacity of stationary Gaussian channels,” which has now received the 2012 Information Theory Paper Award, one of the highest honors in the field of communication theory, awarded each year by the IEEE Information Theory Society.

“We are extremely proud of Young-Han Kim’s achievements,” said Electrical and Computer Engineering chair Shaya Fainman. “We are very fortunate in ECE to have a top-notch information theory group with younger faculty who are rising stars, and Professor Kim is certainly one of them.”

The award recognizes exceptional publications in the field of information theory that appeared in the preceding two calendar years. Kim’s paper first appeared in IEEE Transactions on Information Theory in January 2010.

In the paper, Kim characterized the maximum throughput, or ‘capacity’, of the Gaussian channel – the canonical model for both wired and wireless communication – thus establishing the optimality of such linear feedback communication.

“Feedback plays a pivotal role in control,” says Kim, who is also a member of the Information Theory and Applications (ITA) Center in the California Institute for Telecommunications and Information Technology (Calit2). “Without feedback, even a small amount of error can destabilize control systems in stochastic environments. Just imagine driving on a highway with eyes closed, without the feedback of seeing where you’re going.”

Communication systems, in which one ‘controls’ another's state of knowledge, are notable exceptions. By encoding data with a forward error-correcting code in long blocks, one can communicate reliably over a noisy channel without any interaction between the sender and the receiver. Nevertheless, most communication systems are built over inherently two-way channels, such as telephone lines and the Internet.

Young-Han Kim

“These channels allow potentially rich interactions among users,” explains ITA director Alon Orlitsky. “In his paper, Professor Kim explored whether feedback would improve the quality of communication at all, and if so, by how much. Ultimately he concluded what the optimal use of feedback in communication would be – thereby solving an open problem that many others have tried to solve but failed.”

Kim’s paper focused exclusively on the Gaussian channel. As in everyday conversations, feedback allows the sender (speaker) to iteratively refine the receiver's (listener's) knowledge about the intended message. By learning what the receiver knows at the moment through feedback, the sender can fill in the receiver's error, the error of the error, the error of the error of the error, and so on.

“Quite surprisingly,” notes Kim, “this simple communication method, which is tantamount to calculating a weighted sum of feedback signals and transmitting it back to the receiver, turns out to be optimal.”

So should the Internet be redesigned with simple linear feedback signaling? The UC San Diego researcher is less certain.

“While this result reveals an intriguing interplay between control, estimation, and communication,'' he warns, “our focus is more on the theoretical understanding of the role of feedback in communication than practical implications. Our linear iterative refinement method is based on the idealistic assumption that feedback is rather perfect.”

Nevertheless, Kim argues that the Internet’s popular transmission control protocol (TCP) can be viewed as another instance of iterative refinement, in which the receiver requests missing packets from the sender.

“Iterative refinement is a universal feature in every efficient feedback communication method," adds Kim. “In a sense, the way we talk to each other every day is optimal – provided that there aren't unknown unknowns.''

Finding the optimal feedback communication for Gaussian channels fits squarely into Kim’s overall research effort in network information theory. He works on two important challenges for high-speed, high-volume information processing systems: how to describe information efficiently, and how to transmit it reliably in the presence of noise and interference. With the ultimate goal of providing guidelines that can be put into practice,

“Young-Han Kim explores fundamental principles behind a variety of applications in communication, networking, compression, prediction, and data storage,” observes fellow information theorist Ramesh Rao, director of the UCSD division of Calit2. “The Information Theory Paper Award is one of the premier honors in our field and the 2012 award underscores the importance of Professor Kim’s solution to a longstanding open problem in communication.”

Kim’s research interests also include statistical inference, learning theory, and quantum information processing.

Young-Han Kim earned his Ph.D. in Electrical Engineering from Stanford University in 2006. After receiving B.S. degree with honors in Electrical Engineering from Seoul National University in 1996, Kim spent three-and-half years as a software architect the Seoul-based company Tong Yang Systems, then worked on several industry projects – including development of the communication infrastructure for the new Incheon International Airport – before resuming graduate studies at Stanford.

Kim received a 2008 NSF Faculty Early Career Development (CAREER) Award and the 2009 US-Israel Binational Science Foundation Bergmann Memorial Award. He serves on the Editorial Board of the IEEE Transactions on Information Theory as an Associate Editor for Shannon Theory. He is also a Distinguished Lecturer for the IEEE Information Theory Society.

*Young-Han Kim, “Feedback Capacity of Stationary Gaussian Channels,” IEEE Transactions on Information Theory, Vol. 56, pps. 57-85, Issue 1, January 2010.