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.