Adaptive Filtering
Lecture 1
Introduction
Dr. Tahir Zaidi
Course Content
(Tentative)
Textbook:
S.Haykin, Adaptive Filter Theory, 4th Ed., Prentice Hall, 2002
Introduction
BACKGROUND REVIEW
2.
Discrete-time and random signals
3.
Mathematical Tools
OPTIMAL LINEAR FILTERS
4.
Wiener Filters
5.
Linear Prediction
ADAPTIVE FILTERING
6.
Stochastic Gradient Descent Algorithms
7.
Family of LMS Algorithms
8.
Method of Least Squares
9.
Recursive Least Squares (RLS) Algorithm
10.
Square-Root Algorithms
11.
LMS and RLS Algorithms: Practical Issues
12.
Kalman Filtering (?)
APPLICATIONS
13.
Spectrum Estimation
14.
Array Processing
Adaptive Signal Processing
1.
S.Haykin, Adaptive Filter Theory, 4th Ed.
Definition of filtering
A filter
is commonly used to refer to a system that is designed to
extract information
about a
prescribed quantity of interest
from
noisy data.
Adaptive Signal Processing
Filter
Remove undesired signals while not affecting the desired ones.
Often specified in frequency domain: lowpass, highpass etc. filters to
remove out of band signals.
Often the desired signals and undesired signals are at the same
frequency band. In such a case statistical characterization for filter
design is needed.
A filter is linear if its output is a linear function of the input, i.e.,
Input
Output
x1
y1
x2
y2
a1 x1 + a2 x2
a1 y1 + a2 y2
Applications
Communications; radar, sonar,
Control Systems; navigation,
Speech/Image Processing; echo and noise cancellation,
biomedical engineering
Others; seismology, financial engineering, etc.
Adaptive Signal Processing
Applications
!!! Noise and errors are statistical in nature !!!
We will use statistical tools.
Adaptive Signal Processing
Basic Kinds of Estimation
Filtering
(real-time operation)
Smoothing
(off-line operation)
Prediction
(real-time operation)
Adaptive Signal Processing
Filter
Linear
Non-Linear
Otherwise, it is non-linear.
A filter is linear if the filtered,
smoothed or predicted quantity
at the output of the filter is a
linear function of the observations
applied to the filter input.
u(t)
Linear
or
Non-linear
or
y(t)
Filter
u(n)
y(n)
!!! Non-linear filters may be hard to
Analyse, if not impossible !!!
Adaptive Signal Processing
Optimum Filter
Definition: Solution of an optimization problem wrt.
a certain criterion with statistical parameters.
Nonlinear:
Maximum Likelihood (ML) sense (very difficult to implement)
Linear:
Minimum Mean Square Error (MMSE) sense
Wiener filters, (Stationary environment)
Kalman filters, (Non-stationary environment)
Etc.
(Any other criterion, e.g. ZF)
Adaptive Signal Processing
10
The Filtering Problem
Given an optimality criteria we often can design optimal
filters
Requires a priori information about the environment
Example: Under certain conditions the so called Wiener filter is
optimal in the mean-squared sense
Adaptive filters are self-designing using a recursive
algorithm
Useful if complete knowledge of environment is not available a
priori
Adaptive Filters
Wiener Filter requires -a priori information of several statistics
-estimation (knowledge of the system)
is needed before filtering
-inversion of a huge matrix
-computationally inefficient!
Adaptive filtering can overcome these disadvantages!
Recursive algorithm
No complete a priori information required
Algorithm develops this information with increasing # of iterations.
If the environment is stationary converges to the Wiener soln.
non-stationary tracks the changes.
Adaptive Signal Processing
12
Analysis of Adaptive Filters
Rate of convergence (to the optimum Wiener soln.)
Misadjustment (deviation from the optimum Wiener
soln.)
Tracking (the variations in a non-stationary environment)
Robustness(to disturbances of small energy)
Computational Requirements/Cost
Numerical Properties (Numerical stability & accuracy)
Adaptive Signal Processing
13
Linear Filter Structure
Structure:
FIR (Finite-duration Impulse Response)
IIR
Transversal Filter (Tapped-delay line)
Lattice
Systolic array
(Infinite-duration Impulse Response)
Adaptive Signal Processing
14
Transversal Filter
Convolution
Sum
unit-delay
element
multiplier
adder
Adaptive Signal Processing
15
Transversal Filter
xH: Hermitian transpose
xH=(xT)*
Adaptive Signal Processing
16
Lattice Predictor
Predictor order (# of stages): M
Forward prediction error
Backward prediction error
m: the mth reflection coefficient
Input seq. u(n) is correlated, backward prediction error
b(n) is uncorrelated
Together with m, b(n) approximates d(n) (innovations
process).
Adaptive Signal Processing
17
Lattice Predictor
Adaptive Signal Processing
18
Systolic Array
Represents a parallel computing network
Used for efficient pipelined operation
Matrix multiplication
Triangularisation
Back substitution (Matrix eqn. solving)
Example 3x3 matrix/3x1 vector
Adaptive Signal Processing
19
Systolic Array
Boundary cell
Internal cell
s
y3
Adaptive Signal Processing
20
IIR Filter
May have stability problems,
We will prefer FIR filters for
Adaptive filtering.
Adaptive Signal Processing
21
Adaptive Filtering Algorithms
Error
Difference
between
the filter output
a desired response
Mean Square Error
Weighted
Filter
y(n)
d(n)
(n) : Error
+
-
Error Squares
Adaptive Signal Processing
22
Adaptive Filtering Algorithms
Stochastic Gradient Approach
Cost Function depends on Mean-Square Error criterion
(!!! Stochastic, depends on second order statistics !!!)
Solution of Wiener-Hopf Equations
Results in Wiener soln. but with an iterative approach
Based on Method of Steepest Descent
updated value
of tap - weight
vector
old value
of tap - weight
vector
learning rate gradient
parameter
of
(step size) cost function
Requires
Expectations
E{.}
Use instantaneous values instead of expectations (LMS)
updated value
of tap - weight
vector
old value
of tap - weight
vector
learning rate tap -
error
parameter
input
signal
(step size) vector
Adaptive Signal Processing
23
Adaptive Filtering Algorithms
Least-Squares Estimation
Cost Function depends on sum of weighted error squares
Low computational complexity due to recursive operation
Three
Standard RLS
Relies on Matrix Inversion Lemma
Numerically unstable, high computational complexity
Square-root RLS algorithm
categories
Based on QR-decomposition
Numerically stable
Fast RLS algorithm
Exploits certain matrix structures to reduce complexity.
Adaptive Signal Processing
24
Applications
Four Classes
Identification
Inverse modeling
deconvolution
adaptive and blind
equalisation
Prediction
system identification
layered earth modeling
linear predictive coding
adaptive differential PCM
spectrum analysis
signal detection
Interference cancellation
noise canceling
echo cancellation
adaptive beamforming
Adaptive Signal Processing
25
Applications of Adaptive Filters: Identification
Used to provide a linear model of an unknown plant
Parameters
u=input of adaptive filter=input to plant
y=output of adaptive filter
d=desired response=output of plant
e=d-y=estimation error
Applications:
System identification
System Identification
Observing the output of a
plant(system), given the input
signal, tries to estimate the
IR of the plant.
Filter coefficient are found by
an adaptive algorithm.
Adaptive Signal Processing
27
Applications of Adaptive Filters:
Inverse Modeling
Used to provide an inverse model of an unknown plant
Parameters
u=input of adaptive filter=output to plant
y=output of adaptive filter
d=desired response=delayed system input
e=d-y=estimation error
Applications:
Equalization
Adaptive Equalization
Removes intersymbol
interference (ISI).
Filter coefficient are found
by an adaptive algorithm
Adaptive Signal Processing
29
Applications of Adaptive Filters:
Prediction
Used to provide a prediction of the present value of a
random signal
Parameters
u=input of adaptive filter=delayed version of random signal
y=output of adaptive filter
d=desired response=random signal
e=d-y=estimation error=system output
Applications:
Linear predictive coding
Adaptive Spectrum Estimation
Parametric (AR)
model
Linear AR filter
input: white noise
output: observed
signal
aim: find the model
parameters by an
adaptive algorithm.
Adaptive Signal Processing
31
Applications of Adaptive Filters:
Interference Cancellation
Used to cancel unknown interference from a primary signal
Parameters
u=input of adaptive filter=reference signal
y=output of adaptive filter
d=desired response=primary signal
e=d-y=estimation error=system output
Applications:
Echo cancellation
Adaptive Noise Cancellation
Electrocardiography (ECG)
Acoustic noise in speech
Active noise cancellation
(headphones)
Adaptive Signal Processing
33
Echo Cancellation
Coupling due to imperfect
balancing in hybrid
transformer creates an echo
in analog telephone lines.
Echo signal can be estimated
by an adaptive filter and the
subtracted out.
Adaptive Signal Processing
34
Adaptive Beamforming
Multiple sensors
(antenna, microphone,
etc) used to steer the
beam to a specific
position.
Radar, sonar
Commun. systems,
Astrophysical
exploration,
Biomedical signal
processing, etc.
Adaptive Signal Processing
35
Historical Notes
To understand a science it is necessary to know its history.
Auguste Comte (1798-1857)
Linear Estimation Theory
Method of least squares, Gauss, 1795
Minimum mean square error estimation, late 1930s
Discrete-time Wiener-Hopf equation, Levinson, 1947
Kalman filter, Swerling, 1958 and Kalman, 1960
Stochastic gradient algorithms, late 1950s
Stochastic approximation, Robins and Monro, 1951
LMS algorithm, Widrow and Hoff, 1959
Gradient adaptive lattice (GAL) algorithm, Griffiths, 1977-8
Adaptive Signal Processing
36
Historical Notes
Recursive Least Squares Algorithm
Kalman filter, Godard Algorithm, Godard, 1974
Relationship between RLS and Kalman, Sayed and Kailath, 1994
QR decomposition based systolic array, Gentleman & Kung, 1981
Fast RLS algorithm, 1970s, Morf
Neural Networks
Logical calculus for neural networks, McCulloch and Pitts, 1943
Perceptron, Rosenblatt, 1958
Back-propagation algorithm, Rumelhart, et al., 1986
Radial basis function network, Broomhead and Lowe, 1988
Adaptive Signal Processing
37
Applications
Adaptive Equalisation, 1960s
Zero-forcing equaliser, Lucky, 1965
MMSE equaliser, Gersho, 1969, Proakis&Miller, 1969
Godard Algorithm, Godard, 1974
Fractionally Spaced Equaliser (FSE), Brady, 1970
Decision Feedback Equaliser (DFE), Austin 1967, MMSE,
Monsen, 1971.
Speech Coding
Maximum Likelihood speech prediction, Saito and Itakura, 1966
Linear Predictive Coding (LPC), Atal and Hanauer 1970-1
Adaptive Lattice Predictor, Nakhoul and Cossell, 1981
Adaptive Signal Processing
38
Applications
Spectrum Analysis, early 1900s
Maximum entropy method, Burg, 1967
Method of multiple windows, Thomson, 1982
Adaptive noise cancellation, started at 1965
Adaptive Beamforming
Intermediate Frequency (IF) sidelobe canceller, Howells, 1950
Control law for adaptive array antenna, Applebaum, 1966
Application of LMS, Widrow et al., 1967
Minimum Variance Distortionless Response (MVDR)
beamformer, Capon, 1969
Adaptive Signal Processing
39
Performance Measures of
Adaptive Filters
Rate of convergence
Misadjustment
Tracking
performance in nonstationary environment
Robustness
impact of small disturbances
Computational complexity
Structure
modularity, parallelism
Numerical properties
numerical stability
numerical accuracy
impact of quantization
