Princeton-Rutgers Seminar Series in Communications and Information Theory

Chris Rose and Sergio Verdú, Co-Chairs

Title: Universal Discrete Denoising: Known Channel

Speaker: Tsachy Weissman, Stanford University and HP Labs

Date: Thursday November 21, 2002 4:30 pm

Location: Princeton University, Friend 101


We propose a discrete denoising algorithm, that, based on the observation of the output of a known Discrete Memoryless Channel (DMC), estimates the input sequence to minimize a given fidelity measure. The algorithm does not assume knowledge of statistical properties of the input sequence. Yet, it is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary and ergodic. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the noise. The proposed denoising algorithm is practical, as it can be implemented in near-linear time and with linear storage complexity. Based on joint work with Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger.

Seminar Sponsored by DIMACS Special Focus on Computational Information Theory and Coding.