<< Chapter < Page | Chapter >> Page > |
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 $\mathbb{R}^{N}$ .
The problem is to find the bottom of the bowl. In an adaptive filter context, the shape and bottom of the bowl maydrift 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^{(-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 .
The idea is to iteratively find the minimizer by computingthe gradient of the error function: $E\nabla =\frac{\partial^{1}(\epsilon ^{2})}{\partial {w}_{i}}$ . The gradient is a vector in $\mathbb{R}^{M}$ pointing in the steepest uphill direction on the error surface at a given point $W^{i}$ , with $\nabla $ having a magnitude proportional to the slope of the error surface inthis steepest direction.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.
Notification Switch
Would you like to follow the 'Adaptive filters' conversation and receive update notifications?