The goal of a denoising algorithm is to recover a signal from its noise-corrupted observations. Perfect recovery is seldom possible and performance is measured under a given single-letter fidelity criterion. For discrete signals corrupted by a known discrete memoryless channel (DMC), the Discrete Universal DEnoiser (DUDE) was recently shown to perform this task asymptotically optimally, without knowledge of the statistical properties of the source. In the present work, we address the scenario where, in addition to the lack of knowledge of the source statistics, there is also uncertainty in the channel characteristics. We propose a family of discrete denoisers and establish their asymptotic optimality under a minimax performance criterion which we argue is appropriate for this setting. As we show elsewhere, the proposed schemes can also be implemented computationally efficiently.

We study the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. We give a complete characterization of this relationship for independent and identically distributed (i.i.d.) processes over arbitrary alphabets, stationary ergodic processes over discrete alphabets, and a broad family of stationary ergodic processes over uncountable alphabets. For cases where the entropy rate of the pattern process is infinite, we characterize the possible growth rate of the block entropy.

Recent work by Orlitsky et al. (2004) has motivated the study of pattern sequences and their compressibility properties. Emphasis in this recent line of work has been on compressing pattern sequences under uncertainty in the source that has generated them, thus focusing on universal schemes and their redundancy. Our interest in this work is in the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. We give a complete characterization of this relationship for i.i.d. processes over arbitrary alphabets, stationary and ergodic: processes over discrete alphabets, as well as more general processes that can be represented as the output of an additive white-noise channel. For cases where the entropy rate of the pattern process is infinite, we characterize the possible growth rate of the block entropy.

The recent study of pattern sequences and their compressibility properties has led to interest in the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. In this work we give a complete characterization of this relationship for general discrete Markov processes as well as for a broad family of Markov and additive noise processes over a continuous alphabet

We consider the problem of denoising a binary image corrupted by a noisy medium which flips each component in the original image, independently, to its complementary value with some fixed but unknown probability /spl delta/<1/2. We propose a denoiser which assumes no knowledge of statistical properties of the image, yet asymptotically attains the performance of the scheme that knows the noisy image statistics and operates optimally in a minimax sense. The proposed scheme is implementable, with complexity linear in the image size. Preliminary experimental results are presented which indicate that the scheme has the potential to do well on real data.

The assumption of a known channel was inherent in the structure of the denoising under channel uncertainty (DUDE). There are many scenarios where the DUDE is effective for denoising. A denoising scheme is sought, which will accommodate uncertainty in the statistical characteristics of the noisy medium. Unfortunately, it can be shown that in this setting the task of attaining the performance of the optimum nonuniversal distribution-dependent scheme is impossible, even for a "genie-aided" scheme with complete knowledge of the noisy signal statistics. In this paper, the noise-corrupted signal with the clean components and their values in the finite alphabet are assumed. The corruption mechanism is a discrete memoryless channel (DMC) with an associated invertible channel matrix. It lies in a given uncertainty set.