Discrete denoising for channels with memory

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. Introduction.The problem of denoising an unknown discrete-time discretevalued signal corrupted by a known discrete memoryless channel (DMC) was recently studied in [26], which presented a practical denoising algorithm (DUDE), and established its asymptotic universal optimality.Subsequent work considered, among other things, the sequential version of the problem [22], the case of non-discrete noisy signal components [4], the case of channel uncertainty [7,8], and applications of the DUDE in communications [19].We refer to these papers, and to the references therein, for the increasing variety of applications where the discrete denoising problem is encountered.In this work we revisit the setting of [26] for the case where the noise, rather than being memoryless, is a more generally distributed process.For concreteness, we focus on the case of additive noise, though indicate how our findings carry over to the more general case.We first consider a one-dimensional index set in Section 2, where we begin with a concrete description of our setting and assumptions in Subsection 2-A.We then derive a denoiser, arguing intuitively why it should be effective for our setting, in Subsection 2-B.In Subsection 2-C we present a result establishing the asymptotic universal optimality of the scheme suggested in Section 2-B.In Subsec-