University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Wednesday, April 9, 2003

DTC Seminar Series

DUDE: An Algorithm for Discrete Universal Denoising


Gadiel Seroussi
Hewlett-Packard Laboratories

Wednesday, April 9, 2003
1:00 pm

402 Walter Library

Slide presentation (pdf 469 KB) A discrete denoising algorithm estimates the input sequence to a discrete memory-less channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary and ergodic. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sub-linear working storage size relative to the input data length. Examples of application of the denoiser to synthetic sources, noisy binary images, and English text are presented. Joint work with Tsachy Weissman, Erik Ordentlich, Sergio Verdú, and Marcelo Weinberger.


Dr. Gadiel Seroussi is Director of Information Theory Research at Hewlett-Packard Laboratories in Palo Alto, California, where he joined in 1988. He received a B.S. degree in Electrical Engineering and the M.Sc. and D.Sc. degrees in Computer Science from Technion — Israel Institute of Technology, Haifa, Israel, in 1977, 1979 and 1981, respectively. Dr. Seroussi is a Fellow of the IEEE, cited "for contributions to the theory and practice of error correction and data compression algorithms and architectures." He is a co-author of the algorithm at the core of the JPEG-LS lossless image compression standard, as well as a contributor to the coding algorithm of the JPEG-2000 standard. His research interests include the mathematical foundations and practical applications of information theory, error correcting codes, data and image compression and cryptography. Dr. Seroussi has published numerous journal and conference articles in these areas, and is a co-author of the book Elliptic Curves in Cryptography, published by Cambridge University Press. He has invented and been granted more than twenty U.S. patents.