H∞ Optimality of the LMS Algorithm

We show that the celebrated LMS (Least-Mean Squares) adaptive algorithm is H 1 optimal. The LMS algorithm has been long regarded as an approximate solution to either a stochastic or a deterministic least-squares problem, and it essentially amounts to updating the weight vector estimates along the direction of the instantaneous gradient of a quadratic cost function. In this paper we show that LMS can be regarded as the exact solution to a minimization problem in its own right. Namely, we establish that it is a minimax filter: it minimizes the maximum energy gain from the disturbances to the predicted errors, while the closely related so-called normalized LMS algorithm minimizes the maximum energy gain from the disturbances to the filtered errors. Moreover, since these algorithms are central H 1 filters, they minimize a certain exponential cost function and are thus also risk-sensitive optimal. We discuss the various implications of these results, and show how they provide theoretica..