Skip to content Skip to navigation

Connexions

You are here: Home » Content » Introduction to Adaptive Filtering

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Introduction to Adaptive Filtering

Module by: Clayton Scott, Robert Nowak. E-mail the authors

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

The Kalman filter is just one of many adaptive filtering (or estimation) algorithms. Despite its elegant derivation and often excellent performance, the Kalman filter has two drawbacks:

  1. The derivation and hence performance of the Kalman filter depends on the accuracy of the a priori assumptions. The performance can be less than impressive if the assumptions are erroneous.
  2. The Kalman filter is fairly computationally demanding, requiring OP2 O P 2 operations per sample. This can limit the utility of Kalman filters in high rate real time applications.
As a popular alternative to the Kalman filter, we will investigate the so-called least-mean-square (LMS) adaptive filtering algorithm.

The principle advantages of LMS are

  1. No prior assumptions are made regarding the signal to be estimated.
  2. Computationally, LMS is very efficient, requiring OP O P per sample.
The price we pay with LMS instead of a Kalman filter is that the rate of convergence and adaptation to sudden changes is slower for LMS than for the Kalman filter (with correct prior assumptions).

Adaptive Filtering Applications

Channel/System Identification

Figure 1
Channel/System Identification
Channel/System Identification (csid.png)

Noise Cancellation

Suppression of maternal ECG component in fetal ECG (Figure 2).

Figure 2: Cancelling maternal heartbeat in fetal electrocardiography (ECG): position of leads.
Figure 2 (.png)
Figure 3
Figure 3 (ecg.png)
y ̂ y is an estimate of the maternal ECG signal present in the abdominal signal (Figure 4).
Figure 4: Results of fetal ECG experiment (bandwidth, 3-35Hz; sampling rate, 256Hz): (a)reference input (chest lead); (b)primary input (abdominal lead); (c)noise-canceller output.
Figure 4 (.png)

Channel Equalization

Figure 5
Channel Equalization
Channel Equalization (ce.png)

Adaptive Controller

Figure 6: Here, the reference signal is the desired output. The adaptive controller adjusts the controller gains (filter weights) to keep them appropriate to the system as it changes over time.
Adaptive Controller
Adaptive Controller (ac.png)

Iterative Minimization

Most adaptive filtering alogrithms (LMS included) are modifications of standard iterative procedures for solving minimization problems in a real-time or on-line fashion. Therefore, before deriving the LMS algorithm we will look at iterative methods of minimizing error criteria such as MSE.

Conider the following set-up: x k : observation x k : observation y k : signal to be estimated y k : signal to be estimated

Linear estimator

ŷk= w 1 x k + w 2 x k 1 +…+ w p x k p 1 y k w 1 x k w 2 x k 1 … w p x k p 1 (1)
Figure 7
Figure 7 (fir.png)
Impulse response of the filter: … , 0 , 0 , w 1 , w 2 , … w p , 0 , 0 , … … , 0 , 0 , w 1 , w 2 , … w p , 0 , 0 , …

Vector notation

ŷk=xkTw y k x k w (2)
Where xk= x k x k 1 ⋮ x k p 1 x k x k x k 1 ⋮ x k p 1 and w= w 1 w 2 ⋮ w p w w 1 w 2 ⋮ w p

Error signal

e k = y k −ŷk= y k −xkTw e k y k y k y k x k w (3)

Assumptions

( xk , y k ) ( x k , y k ) are jointly stationary with zero-mean.

MSE

E e k 2=E y k −xkTw2=E y k 2−2wTExk y k +wTExkxkTw= R yy −2wTRxy+wTRxxw e k 2 y k x k w 2 y k 2 2 w x k y k w x k x k w R yy 2 w R xy w R xx w (4)
Where R yy R yy is the variance of y k 2 y k 2 , Rxx R xx is the covariance matrix of xk x k , and Rxy=Exk y k R xy x k y k is the cross-covariance between xk x k and y k y k

Note:

The MSE is quadratic in W W which implies the MSE surface is "bowl" shaped with a unique minimum point (Figure 8).
Figure 8
Figure 8 (mse.png)

Optimum Filter

Minimize MSE:

∂∂wE e k 2=-2Rxy+2Rxxw=0⇒wopt=Rxx-1Rxy w e k 2 -2 R xy 2 R xx w 0 w opt R xx R xy (5)
Notice that we can re-write Equation 5 as
ExkxkTw=Exk y k x k x k w x k y k (6)
or
Exk y k −xkTw=Exk e k =0 x k y k x k w x k e k 0 (7)
Which shows that the error signal is orthogonal to the input xk x k (by the orthogonality principle of minimum MSE estimator).

Steepest Descent

Although we can easily determine wopt w opt by solving the system of equations

Rxxw=Rxy R xx w R xy (8)
Let's look at an iterative procedure for solving this problem. This will set the stage for our adaptive filtering algorithm.

We want to minimize the MSE. The idea is simple. Starting at some initial weight vector w0 w 0 , iteratively adjust the values to decrease the MSE (Figure 9).

Figure 9
In One-Dimension
In One-Dimension (iterative.png)
We want to move w0 w 0 towards the optimal vector wopt w opt . In order to move in the correct direction, we must move downhill or in the direction opposite to the gradient of the MSE surface at the point w0 w 0 . Thus, a natural and simple adjustment takes the form
w1=w0−12μ∂∂wE e k 2|w=w0 w 1 w 0 1 2 μ w w 0 w e k 2 (9)
Where μμ is the step size and tells us how far to move in the negative gradient direction (Figure 10).
Figure 10
Figure 10 (adjust.png)
Generalizing this idea to an iterative strategy, we get
wk=wk−1−12μ∂∂wE e k 2|w=wk−1 w k w k 1 1 2 μ w w k 1 w e k 2 (10)
and we can repeatedly update w w: w0 , w1 , … , wk w 0 , w 1 , … , w k . Hopefully each subsequent wk w k is closer to wopt w opt . Does the procedure converge? Can we adapt it to an on-line, real-time, dynamic situation in which the signals may not be stationary?

Content actions

Give Feedback:

E-mail the module authors | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

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

| A lens (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to Connexions 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 Connexions 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