IBM Israel Research Seminars

Recovery of corrupted data is a problem encountered in all branches of science and engineering. Perfect recovery is seldom possible and performance is measured under a given fidelity criterion. For discrete data corrupted by discrete noise, it was recently shown, through the introduction of an algorithm called DUDE, that this task can be performed essentially optimally with no knowledge of statistical (or any other type of) properties of the data, for large (and realistic) classes of possible corruption mechanisms.
The algorithm is practical: implementable in linear time and sub-linear working storage size. I will describe the DUDE, some of its performance guarantees, and empirical results showcasing its successful application to various types of discrete data. In the second part of the talk, I will survey more recent developments, where the DUDE framework has been extended to other problems. One example is a sequential (on-line) version of the algorithm, which combines the inner workings of the Lempel-Ziv data compression scheme with those of the DUDE. Other examples include lossy compression and error correction for discrete data, where DUDE-based decoding is emerging as a paradigm for developing schemes that are not only practical, but also near-optimal in senses that will be explained. The work I will survey has been carried out in collaboration with students and colleagues who will be given due mention during the talk.

About the speaker
Tsachy Weissman received the B.Sc. (Summa Cum Laude) and Ph.D. degrees, both in electrical engineering, from the Technion in 1997 and 2001, respectively. Following his graduation, he has held postdoctoral appointments with the statistics department at Stanford University and at Hewlett-Packard Laboratories. Since 2003, he has been on the faculty of the electrical engineering department at Stanford University, from which he is currently on leave. He joined the electrical engineering department at the Technion in the summer of 2007. Tsachy’s research interests span information theory and its applications, and statistical signal processing. His papers have focused mostly on data compression, prediction, denoising, communications, and learning. He is also inventor or co-inventor of several patents in these areas. In addition to his academic activities, Tsachy is a consultant to several high-tech companies. Among other prizes, Tsachy was awarded the Clore Foundation scholarship, the Intel Prize, the Viterbi scholarship, the Rothschild foundation scholarship for postdoctoral studies, the NSF CAREER award, and a Horev fellowship. He is a recipient of the 2006 IEEE joint IT/COM societies best paper award.