Universal Filtering Via Prediction

Weissman, Tsachy ; Ordentlich, Erik ; Weinberger, Marcelo J. ; Somekh-Baruch, Anelia ; Merhav, Neri

HP Development Company

关键词: filtering;    prediction;    universal;    sequential compound Bayes;    finite state;    Lempel-Ziv;   

RP-ID  :  HPL-2006-75

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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. 26 Pages