Technical Reports
HPL-2011-136
Click here for full text:
Deinterleaving Finite Memory Processes via Penalized Maximum Likelihood
Seroussi, Gadiel; Szpankowski, Wojciech; Weinberger, Marcelo J.
HP Laboratories
HPL-2011-136
Keyword(s): process deinterleaving; maximum-likelihood estimation; MDL principle; Markov sources
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.
37 Pages
External Posting Date: September 6, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: September 6, 2011 [Fulltext]