# Discrete Denoising with Shifts - Computer Science > Information Theory

Discrete Denoising with Shifts - Computer Science > Information Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We introduce S-DUDE, a new algorithm for denoising DMC-corrupted data. Thealgorithm, which generalizes the recently introduced DUDE Discrete UniversalDEnoiser of Weissman et al., aims to compete with a genie that has access, inaddition to the noisy data, also to the underlying clean data, and can chooseto switch, up to $m$ times, between sliding window denoisers in a way thatminimizes the overall loss. When the underlying data form an individualsequence, we show that the S-DUDE performs essentially as well as this genie,provided that $m$ is sub-linear in the size of the data. When the clean data isemitted by a piecewise stationary process, we show that the S-DUDE achieves theoptimum distribution-dependent performance, provided that the samesub-linearity condition is imposed on the number of switches. To furthersubstantiate the universal optimality of the S-DUDE, we show that when thenumber of switches is allowed to grow linearly with the size of the data,\emph{any} sequence of schemes fails to compete in the above senses. Usingdynamic programming, we derive an efficient implementation of the S-DUDE, whichhas complexity time and memory growing only linearly with the data size andthe number of switches $m$. Preliminary experimental results are presented,suggesting that S-DUDE has the capacity to significantly improve on theperformance attained by the original DUDE in applications where the nature ofthe data abruptly changes in time or space, as is often the case in practice.

Autor: Taesup Moon, Tsachy Weissman

Fuente: https://arxiv.org/