TITLE:     Universal Discrete Denoising for a Known Channel

 

SPEAKER:   Dr. Tsachy Weissman (HP Labs and Stanford)

 

DATE:      2-3PM, Friday, November 8, 2002

 

LOCATION:  Sigma Conference Room, 1L (PA)

 

HOST:      Gadiel Seroussi

 

-----------------------------------------------------------------------

 

ABSTRACT:

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.