Quadratic minimization problems The least squares optimal filter design problem is quadratic in the filter coefficients: ε 2 r dd 0 2 P W W R W If R is positive definite, the error surface ε 2 w 0 w 1 … w M - 1 is a unimodal "bowl" in ℝ N .

The problem is to find the bottom of the bowl. In an adaptive filter context, the shape and bottom of the bowl may drift slowly with time; hopefully slow enough that the adaptive algorithm can track it. For a quadratic error surface, the bottom of the bowl can be found in one step by computing R P . Most modern nonlinear optimization methods (which are used, for example, to solve the L P optimal IIR filter design problem!) locally approximate a nonlinear function with a second-order (quadratic) Taylor series approximation and step to the bottom of this quadratic approximation on each iteration. However, an older and simpler appraoch to nonlinear optimaztion exists, based on gradient descent.

Contour plot of ε-squared The idea is to iteratively find the minimizer by computing the gradient of the error function: E ∇ w i ε 2 . The gradient is a vector in ℝ M pointing in the steepest uphill direction on the error surface at a given point W i , with ∇ having a magnitude proportional to the slope of the error surface in this steepest direction. By updating the coefficient vector by taking a step opposite the gradient direction : W i 1 W i μ ∇ i , we go (locally) "downhill" in the steepest direction, which seems to be a sensible way to iteratively solve a nonlinear optimization problem. The performance obviously depends on μ; if μ is too large, the iterations could bounce back and forth up out of the bowl. However, if μ is too small, it could take many iterations to approach the bottom. We will determine criteria for choosing μ later. In summary, the gradient descent algorithm for solving the Weiner filter problem is: Guess W 0 do i 1 , ∇ i 2 P 2 R W i W i 1 W i μ ∇ i repeat W opt W The gradient descent idea is used in the LMS adaptive fitler algorithm. As presented, this alogrithm costs O M 2 computations per iteration and doesn't appear very attractive, but LMS only requires O M computations and is stable, so it is very attractive when computation is an issue, even thought it converges more slowly then the RLS algorithms we have discussed so far.