\magnification=1200
\baselineskip=20pt
\nopagenumbers
\font\big=cmr12 scaled \magstep2

\centerline{\bf STANFORD UNIVERSITY}
\centerline{\bf DEPARTMENT OF STATISTICS}
\centerline{\big DEPARTMENTAL SEMINAR}
\bigskip

\baselineskip=12pt
\centerline{4:15 p.m., Tuesday, October 22, 2002}
\centerline{Sequoia Hall Room 200}
\centerline{(Cookies at 3:45 in 1st Floor Lounge)}

\bigskip
\baselineskip=15pt
\centerline{\sl Tsachy Weissman}
\centerline{\sl Stanford University and HP Labs}
\bigskip
\centerline{\bf Universal Discrete Denoising for a Known Channel}
\bigskip

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.


\bye