Discrete denoising for channels with memory

We consider the problem of estimating a discrete signal $X^n = (X_1, ... , X_n)$ based on its noise-corrupted observation signal $Zn = (Z_1, ... , Z_n)$. The noise-free, noisy, and reconstruction signals are all assumed to have components taking values in the same finite M-ary alphabet {$0, ... , M − 1$}. For concreteness we focus on the additive noise channel $Z_i = X_i + N_i$, where addition is modulo-$M$, and {$N_i$} 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 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.

Full Text (PDF format)

Published 1 January 2005