Universal filtering via prediction

Abstract—We consider the filtering problem, where a finite-al-phabet individual sequence is corrupted by a discrete memoryless channel, and the goal is to causally estimate each sequence compo-nent 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 re-sult: 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 guar-anteed of attaining the “finite-state filterability ” of any individual sequence by leveraging results from the prediction problem. Index Terms—Compound sequential decision problem, discrete denoising, expert advice, filtering, individual sequences, predic-tion, semistochastic setting. I