5.9 Quadratic minimization and gradient descent

Quadratic minimization problems

The least squares optimal filter design problem is quadratic in the filter coefficients: $$(\epsilon ^2)=r_{\mathrm{dd}}(0)-2P^TW+W^TRW$$ If $R$ is positive definite, the error surface $(\epsilon ^2)\left(w_0,w_1,\dots ,w_{M-1}\right)$ is a unimodal "bowl" in $ℝ^N$ .

For a quadratic error surface, the bottom of the bowl can be found in one step by computing $R^{(-1)}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, anolder and simpler appraoch to nonlinear optimaztion exists, based on gradient descent .

By updating the coefficient vector by taking a step opposite the gradient direction : $W^{(i+1)}=W^i-\mu \nabla ^i$ , we go (locally) "downhill" in the steepest direction, which seems to be a sensible way to iterativelysolve a nonlinear optimization problem. The performance obviously depends on $\mu$ ; if $\mu$ is too large, the iterations could bounce back and forth up out of thebowl. However, if $\mu$ is too small, it could take many iterations to approach thebottom. We will determine criteria for choosing $\mu$ later.

In summary, the gradient descent algorithm for solving the Weiner filter problem is: $$\text{Guess }W^0$$ $$\text{do }i=1,$$∞ $$\nabla ^i=-(2P)+2RW^i$$ $$W^{(i+1)}=W^i-\mu \nabla ^i$$ $$\text{repeat}$$ $$W_{\mathrm{opt}}=W^{}$$∞ The gradient descent idea is used in the LMS adaptive fitleralgorithm. 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 moreslowly then the RLS algorithms we have discussed so far.