Competitive On-line Linear FIR MMSE Filtering

We consider the problem of causal estimation, i.e., filtering, of a real-valued signal corrupted by zero mean, i.i.d., real-valued additive noise under the mean square error (MSE) criterion. We build a competitive on-line filtering algorithm whose normalized cumulative MSE, for every bounded underlying signal, is asymptotically as small as the best linear finite-duration impulse response (FIR) filter of order d. We do not assume any stochastic mechanism in generating the underlying signal, and assume only the variance of the noise is known to the filter. The regret of our scheme is shown to decay in the order of O (log n/n), where n is the length of the signal. Moreover, we present a concentration of the average square error of our scheme to that of the best d-th order linear FIR filter. Our analysis combines tools from the problems of universal filtering and competitive on-line regression.