Title :
Deinterleaving Markov processes via penalized ML
Author :
Seroussi, Gadiel ; Szpankowski, Wojciech ; Weinberger, Marcelo J.
Author_Institution :
Hewlett-Packard Labs., Palo Alto, CA, USA
fDate :
June 28 2009-July 3 2009
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 memoryless random switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the Markov processes, or the parameters of the switch. We present a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function, and show it to be strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, the original Markov and switch processes. Solutions are described for the case where a bound on the order of the Markov processes is available, and for the case where it is not. We demonstrate that the proposed scheme performs well in practice, requiring much shorter input sequences for reliable deinterleaving than previous solutions.
Keywords :
Markov processes; maximum likelihood estimation; deinterleaver; finite memory Markov processes; memoryless random switch; penalized maximum likelihood cost function; reliable deinterleaving; Application software; Computer science; Cost function; Data mining; H infinity control; Interleaved codes; Laboratories; Markov processes; Sequential analysis; Switches;
Conference_Titel :
Information Theory, 2009. ISIT 2009. IEEE International Symposium on
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-4312-3
Electronic_ISBN :
978-1-4244-4313-0
DOI :
10.1109/ISIT.2009.5205257