Abstract
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 fidelity criterion. For discrete signals corrupted by discrete memoryless channels it was recently shown, through the introduction of the DUDE algorithm, that this task can be performed with no knowledge of statistical properties of the input signal. The algorithm is also practical, being implementable in linear time and sub-linear working storage size.

The talk will describe the algorithm, discuss some of its performance guarantees and the intuition behind them, present a few empirical results of its implementation in real-life scenarios, and show how its variants can be applied to related problems.

I will also briefly mention more recent work triggered by the discovery of the DUDE, including the finite-input-general-output scheme, the LZ-based sequential DUDE, the optimality of singlet decoders, and sample properties of the empirical distribution of rate distortion codes.

Based on joint works with Amir Dembo, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger.