Universal Discrete Denoising

通用离散去噪

• 批准号: 0512140
• 负责人: Tsachy Weissman
• 金额: $ 16万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-03-01 至 2008-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0512140&HistoricalAwards=false
• 关键词: Universal; Discrete; Denoising

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.

这是一项针对新领域的集成研究计划，其中包含丰富的应用程序：从其噪声浪费版本中恢复信号的问题。恢复可以取决于应用程序的两种主要模式：非原因，即一旦整个信号可用，它就会启动；并因果关系，即在收到每个符号后必须立即做出决定。我们的重点是对于无噪声的字母以及噪声浪费的信号的字母是有限的。问题出在各种情况下，从键入和/或拼写校正到隐藏的马尔可夫进程状态估计；从DNA序列分析和处理到增强FACSIMILE和其他二元图像的增强；从盲目的均衡问题到连接源通道解码，当离散源通过离散噪声通道发送未编码时。已经研究了某些离散去命中问题的实例，特别是在对隐藏的马尔可夫过程估算的背景下，假设信号统计是已知的。但是，关于普遍环境的文献，即在这项研究之前，基本的无噪声信号和/或关于噪声浪费机制的分布存在不确定性一直很少。在我们的研究之前，基于压缩的普遍离散deoising方法引起了不可实施的方案，而相对于统计数据的统计数据，相对于统计数据的情况而言，这是相当大的。这项研究开发了离散deNOO的通用算法，用于无需知道无需无疑信号的统计表征。对于未知的离散源被各种离散渠道损坏的情况，可获得有希望的结果。我们表明，在任何给定的失真标准下，与知道并且是专门针对输入统计的算法相同的渐近性能，可以实现普遍相同的渐近性能。此外，我们通过计算复杂性来实现这一目标，该计算复杂性随数据的大小线性增长。