Quadratic minimization problems

The least squares optimal filter design problem is quadratic in the filter coefficients: Eε2= r dd 0-2PTW+WTRW ε 2 r dd 0 2 P W W R W If RR is positive definite, the error surface Eε2 w 0 w 1 … w M - 1 ε 2 w 0 w 1 … w M - 1 is a unimodal "bowl" in ℝN ℝ 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-1P R P . Most modern nonlinear optimization methods (which are used, for example, to solve the LP 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.

The idea is to iteratively find the minimizer by computing the gradient of the error function: E ∇=∂∂ w i Eε2 E ∇ w i ε 2 . The gradient is a vector in ℝM ℝ M pointing in the steepest uphill direction on the error surface at a given point Wi 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 : Wi+1=Wi-μ∇i 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  W0 Guess  W 0 do  i=1 , ∞ do  i 1 , ∇i=-2P+2RWi ∇ i 2 P 2 R W i Wi+1=Wi-μ∇i W i 1 W i μ ∇ i repeat repeat W opt =W∞ W opt W The gradient descent idea is used in the LMS adaptive fitler algorithm. As presented, this alogrithm costs OM2 O M 2 computations per iteration and doesn't appear very attractive, but LMS only requires OM 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.