Information Theory paper wins IEEE prize

By Jamie Beckett, Aug. 2006

A paper by a team of HP Labs researchers and their colleagues has received the IEEE Communication Society and Information Theory Joint Paper Award, given annually to recognize an outstanding paper published in the main journals of these IEEE societies during the previous calendar year.

The paper, "Universal Discrete Denoising: Known Channel," describes a new algorithm, the Discrete Universal Denoiser (DUDE), for removing noise from data. ("Noise" refers to anything that interferes with the communication of data – dust on a scanner, errors in text, low-light sensor noise in a digital photograph, etc.)

Typically, cleaning data to most closely match the original requires an algorithm that is tailored to a specific type of noise and data. The HP Labs algorithm described in the paper is universal; it has the potential to perform just as well as specialized algorithms without "knowing" a priori what type of data is involved.

"The problem we set up to solve is how to make optimal decisions – that is, how to minimize the distortion between the denoised data and the clean data," says Marcelo Weinberger, manager of the Information Theory Research group at HP Labs. "In most denoising algorithms, you would have some assumption about what caused the noise and what type of data you have. We prove – in a well-defined mathematical sense -- that our algorithm universally attains the performance of any algorithm fully informed about the statistical characteristics of the data."

Weinberger co-authored the paper with Tsachy Weissman, an assistant professor in Stanford University's Department of Electrical Engineering; Erik Ordentlich, HP Labs; Gadiel Seroussi, from the Mathematical Sciences Research Institute (MSRI); and Sergio Verdú, a professor of Electrical Engineering at Princeton University.

The research effort on this paper started when all of the authors had links to HP Labs. Weissman was a post-doctoral associate at HP Labs’ Information Theory Research group, Seroussi was director of the group, and Verdú was the Hewlett-Packard Visiting Research Professor at MSRI. Some 20 patent applications have been filed in relation to this work.

"The outcome of this research is a testament to an environment that fosters academic/industrial collaboration," Weinberger said.

The paper, originally published as an HP Labs technical report appeared in its final form in the January 2005 issue of the IEEE Transactions on Information Theory.