
Click here for full text:
Universal Filtering Via Prediction
Weissman, Tsachy; Ordentlich, Erik; Weinberger, Marcelo J.; SomekhBaruch, Anelia; Merhav, Neri
HPL200675
Keyword(s): filtering; prediction; universal; sequential compound Bayes; finite state; LempelZiv
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 "finitestate filterability" of any individual sequence by leveraging results from the prediction problem.
26 Pages
Back to Index
