Computer Science – Information Theory
Scientific paper
2011-08-25
Computer Science
Information Theory
Scientific paper
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 \emph{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.
Seroussi Gadiel
Szpankowski Wojciech
Weinberger Marcelo J.
No associations
LandOfFree
Deinterleaving Finite Memory Processes via Penalized Maximum Likelihood does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deinterleaving Finite Memory Processes via Penalized Maximum Likelihood, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deinterleaving Finite Memory Processes via Penalized Maximum Likelihood will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-501441