Click here for full text:
Universal Filtering Via Prediction
Weissman, Tsachy; Ordentlich, Erik; Weinberger, Marcelo J.; Somekh-Baruch, Anelia; Merhav, Neri
Keyword(s): filtering; prediction; universal; sequential compound Bayes; finite state; Lempel-Ziv
Abstract: We consider the filtering problem, where a finite- alphabet individual sequence is corrupted by a discrete memoryless channel, and the goal is to causally estimate each sequence component based on the past and present noisy observations. We establish a correspondence between the filtering problem and the problem of prediction of individual sequences which leads to the following result: Given an arbitrary finite set of filters, there exists a filter which performs, with high probability, essentially as well as the best in the set, regardless of the underlying noiseless individual sequence. We use this relationship between the problems to derive a filter guaranteed of attaining the "finite-state filterability" of any individual sequence by leveraging results from the prediction problem.
Back to Index