Universal Discrete Denoising

这是一个综合研究计划，在一个新的领域与丰富的应用阵列：从其噪声损坏的版本恢复信号的问题。根据应用的不同，恢复可以采用两种主要模式：非因果模式，即一旦整个信号可用就开始恢复；以及因果关系，即必须在接收到每个符号后立即做出决定。我们的重点是理论和实践去噪的情况下，无噪声的字母表，以及被噪声污染的信号，是有限的。问题出现在各种情况下，从输入和/或拼写纠正到隐马尔可夫过程状态估计；从DNA序列分析和处理到传真和其他二值图像的增强；从盲均衡问题到通过离散噪声信道发送未编码的离散信源的信路联合解码。研究了离散去噪问题的某些实例，特别是在隐马尔可夫过程的状态估计的背景下，假设信号统计量是已知的。然而，在本研究之前，关于普遍设置的文献很少，其中存在关于潜在无噪声信号分布和/或关于噪声破坏机制的不确定性。在我们的研究之前，基于压缩的通用离散去噪方法产生了一些方案，这些方案无法以合理的复杂性实现，并且相对于已知统计数据的情况而言，这是相当次优的。本研究开发了离散去噪的通用算法，而不需要知道无噪声信号的统计特性。对于未知的离散源被各种类型的离散信道破坏的情况，得到了令人满意的结果。我们表明，在任何给定的失真准则下，作为一种知道并专门为输入统计量量身定制的算法，有可能实现普遍相同的渐近性能。此外，我们通过计算复杂度来实现这一点，计算复杂度随着数据的大小线性增长。

This is an integrated research program on a new area with a rich array of applications: the problem of recovering a signal from its noise-corrupted version. The recovery can assume two major modes depending on the application: noncausal, i.e. it starts once the entire signal is available; and causal, i.e. decisions must be made immediately after each symbol is received. Our focus is on the theory and practice of denoising for the case where the alphabet of the noiseless, as well as that of the noise-corrupted signal, are finite. The problem arises in a variety of situations ranging from typing and/or spelling correction to hidden Markov process state estimation; from DNA sequence analysis and processing to enhancement of facsimile and other binary images; from blind equalization problems to joint source-channel decoding when a discrete source is sent unencoded through a discrete noisy channel. Certain instances of the discrete denoising problem have been studied, particularly in the context of state estimation for hidden Markov processes, assuming that the signal statistics are known. However, the literature on the universal setting, where there is uncertainty regarding the distribution of the underlying noiseless signal and/or regarding the noise-corrupting mechanism, has been sparse until this research. The compression-based approach to universal discrete denoising that preceded our research gave rise to schemes that were not implementable with reasonable complexity, and were considerably suboptimal relative to the case where the statistics are known.This research develops universal algorithms for discrete denoising without the need to know the statistical characterization of the noiseless signal. Promising results are obtained for the case of an unknown discrete source corrupted by various types of discrete channels. We show that it is possible to achieve universally the same asymptotic performance under any given distortion criterion as an algorithm that knows, and is specifically tailored for, the input statistics. Furthermore, we accomplish this with computational complexity that grows linearly with the size of the data.