\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, Apr 5, 2005}
\centerline{Sequoia Hall Room 200}
\centerline{(Cookies at 3:45 in 1st Floor Lounge)}

\bigskip
\baselineskip=15pt
\centerline{\sl Tsachy Weissman }
\centerline{Department of Electrical Engineering}
\centerline{Stanford University}
\bigskip
\centerline{\bf Discrete Denoising for Channels with Memory}
\bigskip

Abstract:

The problem of estimating a finite-alphabet signal corrupted by a 
finite-alphabet noise process, aka "discrete denoising", is arising in an 
increasing variety of applications spanning engineering, statistics, 
computer science, and biology.

For the case where the corruption mechanism (channel) is memoryless 
(independent noise components), a practical (linear time) algorithm dubbed 
DUDE (Discrete Universal DEnoiser) was recently introduced. This denoiser 
was shown to achieve optimum performance (in the limit of large data 
sets), with no a priori knowledge of statistical (or any other) properties 
of the noiseless data.

This talk will present an extension of the algorithm that accommodates 
possible memory (dependence) in the noise. We establish asymptotic 
optimality of the proposed denoiser under a mild mixing condition on the 
noise process. We also establish the practicability of the algorithm. A 
small sample of empirical evidence supporting the theoretical predictions 
and highlighting the benefit in taking the channel memory into account 
will be presented.

Based on joint work with Rui Zhang.

Time permitting, I will briefly mention related research on discrete 
denoising.
\bye