Adaptive universal linear filtering

Dan Garber, Elad Hazan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We consider the problem of online estimation of an arbitrary real-valued signal corrupted by zero-mean noise using linear estimators. The estimator is required to iteratively predict the underlying signal based on the current and several last noisy observations, and its performance is measured by the mean-square-error. We design and analyze an algorithm for this task whose total square-error on any interval of the signal is equal to that of the best fixed filter in hindsight with respect to the interval plus an additional term whose dependence on the total signal length is only logarithmic. This bound is asymptotically tight, and resolves the question of Moon and Wiessman ['Universal FIR MMSE filtering,' IEEE Trans. Signal Process., vol. 57, no. 3, pp. 1068-1083, 2009]. Furthermore, the algorithm runs in linear time in terms of the number of filter coefficients. Previous constructions required at least quadratic time.

Original languageEnglish (US)
Article number6384815
Pages (from-to)1595-1604
Number of pages10
JournalIEEE Transactions on Signal Processing
Issue number7
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering


  • Filtering
  • logarithmic regret
  • online learning
  • regret minimization
  • universal filtering
  • unsupervised adaptive filtering


Dive into the research topics of 'Adaptive universal linear filtering'. Together they form a unique fingerprint.

Cite this