TITLE: Discrete Denoising for Channels with Memory
SPEAKER: Rui Zhang (Stanford University)
DATE: 2:00 - 3:00 P.M., Tuesday March 1, 2005
LOCATION: Pi, 1L (PA)
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.
Specifically, we consider the problem of estimating a discrete signal X = (X1, .
. . ,Xn) based on its noise-corrupted observation signal Z = (Z1, . . . ,Zn).
The noise-free, noisy, and reconstruction signals are all assumed to have
components taking values in the same finite M-ary alphabet. For concreteness we
focus first on the additive noise channel Zi = Xi +Ni, where addition is
modulo-M, and {Ni} is the noise process. The cumulative loss is measured by a
given loss function. The distribution of the noise is assumed known, and may
have memory restricted only to stationarity and a mild mixing condition. We
develop a sequence of denoisers (indexed by the block length n) which we show to
be asymptotically universal in both a semi-stochastic setting (where the
noiseless signal is an individual sequence) and in a fully stochastic setting
(where the noiseless signal is emitted from a stationary source). It is detailed
how the problem formulation, denoising schemes, and performance guarantees carry
over to more general (non-additive) channels, as well as to higher-dimensional
data arrays.
The proposed schemes are shown to be computationally implementable. We also
discuss a variation on these schemes that is likely to do well on data of
moderate size. We conclude with a report of experimental results for the binary
burst noise channel, where the noise is a finite-state hidden Markov process
(FS-HMP), and a finite-state hidden Markov random field (FS-HMRF), in the
respective cases of one- and two-dimensional data. These support the theoretical
predictions and show that, in practice, there is much to be gained by taking the
channel memory into account.
This is joint work with Tsachy Weissman.
|
|
|
printable version
