2008 Poster Sessions : Discrete Denoising with Shifts

Student Name : Taesup Moon
Advisor : Tsachy Weissman
Research Areas: Information Systems
We introduce S-DUDE, a new algorithm for denoising DMC-corruputed data. The algorithm extends the recently introduced DUDE (Discrete Universal DEnoiser) of Weissman et. al., and aims to compete with a genie that has access to both noisy and clean data, and can choose to switch, up to $m$ times, between sliding window denoisers in a way that minimizes the overall loss. The key issue is to learn the best segmentation of data and the associated denoisers of the genie, only based on the noisy data. Unlike the DUDE, we treat cases of one- and two-dimensional data separately due to the fact that the segmentation of two-dimensional data is significantly more challenging than that of one-dimensional data. We use dynamic programming and quadtree decomposition in devising our scheme for one- and two- dimensional data, respectively, and show that, regardless of the underlying clean data, our scheme achieves the performance of the genie provided that $m$ is sub-linear in the sequence length $n$ for one-dimensional data and $m\ln m$ is sub-linear in $n$ for two-dimensional data. We also prove the universal optimality of our scheme for the case where the underlying data are (spatially) stationary. The resulting complexity of our scheme is linear in both $n$ and $m$ for one-dimensional data, and linear in $n$ and exponential in $m$ for two-dimensional data. We also provide a sub-optimal scheme for two-dimensional data that has linear complexity in both $n$ and $m$, and present some promising experimental results involving this scheme.

Taesup Moon received the B.S. degree with honors in electrical engineering from Seoul National University, Seoul, Korea, in 2002, and the M.S. degree in electrical engineering from Stanford University, Stanford, CA, in 2004. He is currently working toward the Ph.D degree in the Information Systems Laboratory, the Department of Electrical Engineering at Stanford University, Stanford, CA. His research interests are in information theory, statistical signal processing, sequential decision making problems, online learning, game theory and communication.