Universal discrete denoising: Known channel

Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Verdú Sergio, Marcelo J. Weinberger

Research output: Contribution to journalArticle

151 Scopus citations

Abstract

A discrete denoising algorithm estimates the input sequence to a discrete memoryless 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. 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 sublinear working storage size relative to the input data length.

Original languageEnglish (US)
Pages (from-to)5-28
Number of pages24
JournalIEEE Transactions on Information Theory
Volume51
Issue number1
DOIs
StatePublished - Jan 1 2005

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Context models
  • Denoising
  • Discrete filtering
  • Discrete memoryless channels (DMCs)
  • Individual sequences
  • Noisy channels
  • Universal algorithms

Fingerprint Dive into the research topics of 'Universal discrete denoising: Known channel'. Together they form a unique fingerprint.

  • Cite this

    Weissman, T., Ordentlich, E., Seroussi, G., Sergio, V., & Weinberger, M. J. (2005). Universal discrete denoising: Known channel. IEEE Transactions on Information Theory, 51(1), 5-28. https://doi.org/10.1109/TIT.2004.839518