MIT/HP Alliance Colloquium: "Universal
Discrete Denoising for a Known Channel"
Dr. Tsachy Weissman, Stanford University, 4-5pm,
The problem of discrete denoising arises in various scenarios including
channel decoding, hidden Markov model state estimation, image enhancement,
biomolecular sequence analysis, text correction, and many more.
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 criterion. The algorithm
is universal in the sense that it requires no knowledge of the input
sequence or its statistical properties. Yet, asymptotically it performs
as well as the optimum distribution-dependent scheme. The proposed
denoising algorithm is practical, and can be implemented in O(n
log n) time and linear storage complexity.
Based on joint work with Erik Ordentlich, Gadiel Seroussi, Sergio
Verdu, and Marcelo Weinberger.