Discrete Universal Denoiser

In information theory and signal processing, the Discrete Universal Denoiser (DUDE) is a denoising scheme for recovering sequences over a finite alphabet, which have been corrupted by a discrete memoryless channel.

The DUDE was proposed in 2005 by Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú and Marcelo J.

, the DUDE counts of the occurrences of all the strings of length

This conditional distribution, in turn, can be estimated from an individual observed noisy signal

Under certain assumptions, the DUDE is a universal scheme in the sense of asymptotically performing as well as an optimal denoiser, which has oracle access to the unknown sequence.

More specifically, assume that the denoising performance is measured using a given single-character fidelity criterion, and consider the regime where the sequence length

, the DUDE asymptotically performs, in expectation, as well as the best denoiser, which has oracle access to the source distribution

In the single-sequence, or “semi-stochastic” setting with a fixed doubly infinite sequence

be the finite alphabet of a fixed but unknown original “noiseless” sequence

The sequence is fed into a discrete memoryless channel (DMC).

To compare candidate denoisers, we choose a single-symbol fidelity criterion

matrix, with columns of the form The DUDE corrects symbols according to their context.

The first step of the DUDE scheme is to calculate the empirical distribution of symbols in each possible two-sided context along the noisy sequence

(or its non-normalized version, the count vector) for each two-sided context found along

The second step of the DUDE scheme is to calculate, for each two-sided context

is not invertible, under the reasonable assumption that it has full row rank, we replace

is the Bayes response to the two-sided context of the symbol, namely This step requires

operations and used the data structure constructed in the previous step.

be an unknown noiseless sequence stationary source and

[1] The lower bound proof requires that the channel matrix

To motivate the particular definition of the DUDE using the Bayes response to a particular vector, we now find the optimal denoiser in the non-universal case, where the unknown sequence

Observe that the Bayes response is scale invariant in the sense that

is not invertible, under the reasonable assumption that it has full row rank, we can replace

with its Moore-Penrose pseudo-inverse and obtain Turning now to arbitrary

above shows that the optimal denoiser admits an alternative representation, namely

While the convergence arguments behind the optimality properties above are more subtle, we note that the above, combined with the Birkhoff Ergodic Theorem, is enough to prove that for a stationary ergodic source, the DUDE with context-length

The basic DUDE as described here assumes a signal with a one-dimensional index set over a finite alphabet, a known memoryless channel and a context length that is fixed in advance.

[3] Specifically: A DUDE-based framework for grayscale image denoising[6] achieves state-of-the-art denoising for impulse-type noise channels (e.g., "salt and pepper" or "M-ary symmetric" noise), and good performance on the Gaussian channel (comparable to the Non-local means image denoising scheme on this channel).

A different DUDE variant applicable to grayscale images is presented in.

[7] The DUDE has led to universal algorithms for channel decoding of uncompressed sources.