|
Universal Discrete Denoising: Known Channel
Tsachy Weissman,
Stanford University and HP Labs:
Thursday November 21, 2002 4:30 pm, 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.
|
 |
