Competitive Randomized Nonlinear Prediction Under Additive Noise

We consider sequential nonlinear prediction of a bounded, real-valued and deterministic signal from its noise-corrupted past samples in a competitive algorithm framework. We introduce a randomized algorithm based on context-trees [1]. The introduced algorithm asymptotically achieves the performance of the best piecewise affine model that can both select the best partition of the past observations space (from a doubly exponential number of possible partitions) and the affine model parameters based on the desired clean signal in hindsight. Although the performance measure including the loss function is defined with respect to the noise-free clean signal, the clean signal, its past samples or prediction errors are not available for training or constructing predictions. We demonstrate the performance of the introduced algorithm when applied to certain chaotic signals.