Time+Place: Wednesday 28/05/2014 15:30 Room 337 Taub Bld.
Title: Deinterleaving Finite Memory Processes via Penalized Maximum Likelihood
Speaker: Gadiel Seroussi - CSpecial lecture - NOTE UNUSUAL DAY AND TIME http://www.msri.org/people/staff/gadiel/
Affiliation: Universidad de la Republica, Montevideo, Uruguay
Host: Ronny Roth

Abstract:

We study the problem of deinterleaving a set of finite-memory (Markov)
processes over disjoint finite alphabets, which have been randomly
interleaved by a finite-memory switch. The deinterleaver has access to a
sample of the resulting interleaved process, but no knowledge of the number
or structure of the component Markov processes, or of the switch. We study
conditions for uniqueness of the interleaved representation of a process,
showing that certain switch configurations, as well as memoryless component
processes, can cause ambiguities in the representation. We show that a
deinterleaving scheme based on minimizing a penalized maximum-likelihood
cost function is strongly consistent, in the sense of reconstructing, almost
surely as the observed sequence length tends to infinity, a set of component
and switch Markov processes compatible with the original interleaved
process. Furthermore, under certain conditions on the structure of the
switch (including the special case of a memoryless switch), we show that the
scheme recovers *all* possible interleaved representations of the original
process. Experimental results are presented demonstrating that the proposed
scheme performs well in practice, even for relatively short input samples.

Joint work with W. Szpankowski and M. Weinberger.

Short Bio:

Gadiel Seroussi is an independent consultant on applications of 
information theory, based in Cupertino, California. He is also a 
professor of Electrical Engineering and Computer Science at Universidad 
de la Republica, Montevideo, Uruguay. Previously, he was with 
Hewlett-Packard Laboratories in Palo Alto, California, where he founded 
the Information Theory Research group, was its director until 2005, and 
a research consultant to the group until 2013. His research interests 
include the mathematical foundations and practical applications of 
information theory, error correcting codes, data compression, image 
processing, and cryptography.
Seroussi is a coauthor of the book Elliptic Curves in Cryptography 
(1999), and a coeditor of Advances in Elliptic Curve Cryptography 
(2005), both published by Cambridge University Press.
He holds B.Sc., M.Sc., and D.Sc. degrees from Technion, Israel Institute 
of Technology, and is a Fellow of the IEEE.

Desserts will be served from 15:15
Lecture starts at 15:30