Universal Denoising for the Finite-Input General-Output Channel
Amir Dembo, Tsachy Weissman · IEEE Transactions on Information Theory · 2005
We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noiseless signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O(n/sup 1+/spl epsiv//) operations (for any /spl epsiv/>0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memoryless channel (DMC).