Discrete denoising for channels with memory
Tsachy Weissman, Rui Zhang · Communications in Information and Systems · 2005
We consider the problem of estimating a discrete signal X n = (X 1 , . . ., Xn) based on its noise-corrupted observation signal Z n = (Z 1 , . . ., Zn).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.