Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Adaptive Filters » Quadratic Minimization and Gradient Descent

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

In these lenses

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

  • SigProc display tagshide tags

    This module is included inLens: Signal Processing
    By: Daniel McKennaAs a part of collection: "Fundamentals of Signal Processing"

    Click the "SigProc" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • richb's DSP display tagshide tags

    This collection is included inLens: richb's DSP resources
    By: Richard Baraniuk

    Comments:

    "A good introduction in adaptive filters, a major DSP application."

    Click the "richb's DSP" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Quadratic Minimization and Gradient Descent

Module by: Douglas L. Jones. E-mail the author

Quadratic minimization problems

The least squares optimal filter design problem is quadratic in the filter coefficients: Eε2= r dd 02PTW+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 .

Figure 1
Figure 1 (fig1QuadraticMin.png)
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.

Figure 2
Contour plot of ε-squared
Contour plot of ε-squared (fig2QuadraticMin.png)
The idea is to iteratively find the minimizer by computing the gradient of the error function: E =Eε2 w i 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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks