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.