Efficient pruning of bi-directional context trees with applications to universal denoising and compression
Erik Ordentlich, M.J. Weinberger, Tsachy Weissman · Manufacturing Engineer · 2005
The classical framework of context-tree models, customary in sequential decision problems such as compression and prediction, is generalized to a setting in which the observations are multi-tracked or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. The notion of a bi-directional context set is formalized and the generalization of the classical context-tree-based representation for a well defined set of bi-directional contexts is presented, together with an efficient dynamic programming algorithm for determining the best set of bi-directional contexts for a given individual sequence, maximum context depth, and loss function. After briefly describing how this framework can be applied to universal data compression, we focus on its application to universal denoising, where we pair the proposed framework with a new technique for estimating the loss of a denoising algorithm based only on noisy observations.