Computer Science – Information Theory
Scientific paper
2007-08-20
Computer Science
Information Theory
30 pages, 3 figures, submitted to IEEE Trans. Inform. Theory
Scientific paper
We introduce S-DUDE, a new algorithm for denoising DMC-corrupted data. The algorithm, which generalizes the recently introduced DUDE (Discrete Universal DEnoiser) of Weissman et al., aims to compete with a genie that has access, in addition to the noisy data, also to the underlying clean data, and can choose to switch, up to $m$ times, between sliding window denoisers in a way that minimizes the overall loss. When the underlying data form an individual sequence, 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 is emitted by a piecewise stationary process, we show that the S-DUDE achieves the optimum distribution-dependent performance, provided that the same sub-linearity condition is imposed on the number of switches. To further substantiate the universal optimality of the S-DUDE, we show that when the number of switches is allowed to grow linearly with the size of the data, \emph{any} (sequence of) scheme(s) fails to compete in the above senses. Using dynamic programming, we derive an efficient implementation of the S-DUDE, which has complexity (time and memory) growing only linearly with the data size and the number of switches $m$. Preliminary experimental results are presented, suggesting that S-DUDE has the capacity to significantly improve on the performance attained by the original DUDE in applications where the nature of the data abruptly changes in time (or space), as is often the case in practice.
Moon Taesup
Weissman Tsachy
No associations
LandOfFree
Discrete Denoising with Shifts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Discrete Denoising with Shifts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete Denoising with Shifts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-532596