TY - JOUR

T1 - Universal discrete denoising

T2 - Known channel

AU - Weissman, Tsachy

AU - Ordentlich, Erik

AU - Seroussi, Gadiel

AU - Sergio, Verdú

AU - Weinberger, Marcelo J.

N1 - Funding Information:
Manuscript received February 10, 2003; revised September 28, 2004. The material in this paper was presented in part at the 2002 IEEE Information Theory Workshop, Bangalore, India, at the 2003 IEEE International Symposium on Information Theory, Yokohama, Japan, and at the 2003 IEEE International Conference on Image Processing, Barcelona, Catalonia, Spain. The work of T. Weissman was supported in part by the National Science Foundation under Grant CCR-0312839. Part of this work was performed while T. Weissman was with Hewlett-Packard Laboratories and S. Verdú was a Hewlett-Packard/Mathematical Sciences Research Institute (MSRI) Visiting Research Professor.

PY - 2005/1

Y1 - 2005/1

N2 - 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.

AB - 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.

KW - Context models

KW - Denoising

KW - Discrete filtering

KW - Discrete memoryless channels (DMCs)

KW - Individual sequences

KW - Noisy channels

KW - Universal algorithms

UR - http://www.scopus.com/inward/record.url?scp=12444304529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=12444304529&partnerID=8YFLogxK

U2 - 10.1109/TIT.2004.839518

DO - 10.1109/TIT.2004.839518

M3 - Article

AN - SCOPUS:12444304529

VL - 51

SP - 5

EP - 28

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

ER -