Universal Switching FIR Filtering

摘要

We revisit recently considered universal finite-impulse-response (FIR) filtering problem and devise a scheme that asymptotically attains the expected mean-square error (MSE) of the best switching FIR filters for every underlying bounded, real-valued signal, provided that the switch rate of the best filters are sufficiently slow. As a performance metric, we consider adaptive expected regret, the maximum difference between the expected MSE of our filter and that of the best FIR filter over any contiguous time interval. Our algorithm is shown to have $O(log^{2} n)$ bound on the adaptive expected regret with $O(n^{2})$ time-complexity, where $n$ is the length of the signal; the bound implies that, regardless of the underlying signal, the expected MSE of our filter universally converges to that of the best switching FIR filters, if the number of switches is $o({{n} over {log^{2}n}})$ . The experimental results show that our filter outperforms its stationary counterpart particularly when the underlying signal has time-varying characteristics. We also show a heuristic scheme with $O(n)$ time-complexity works well without losing too much of the filtering performance.