A Context Quantization Approach to Universal Denoising

We revisit the problem of denoising a discrete-time continuous-amplitude signal corrupted by a known memoryless channel. By modifying our earlier approach to the problem, we obtain schemes that are much more tractable than the original ones, while retaining their universal optimality properties. The schemes involve a simple preprocessing step of quantizing the noisy symbols to generate quantized contexts which (according to the quantized context value of each symbol) are then used to partition the unquantized symbols to subsequences. A universal context-free denoiser (of zero context length for the unquantized sequences) is then separately employed on each of the subsequences. We identify a rate in which the context length and quantization resolution should be increased so that the resulting scheme is universal in both the semi-stochastic and fully stochastic settings. The proposed family of schemes is computationally attractive, having linear complexity with a proportionality constant that is independent of the context length and the quantization resolution. Experimental results show that these schemes are not only superior from a computational viewpoint, but also achieve better denoising in practice.