Chapter II

Adaptive filtering
1 Introduction
In this chapter we will address the issue of improving intelligibility of
the speech through adaptive filtering algorithms..

Then we will cite some adaptive filtering algorithms used in enhancement.

of the useful signal and echo cancellation, their mathematical development and their condition of
stability.

2 Adaptive filter
2.1 Definition of an adaptive filter

An adaptive filter is a digital filter whose coefficients modify themselves.

based on external signals. It is used whenever an environment is poor
known or changing, or to eliminate disturbances located in the field of
signal useful frequencies, what classic filters cannot do, It is made up of
two distinct parts (Figure II.1) [5].

Figure II.1: Principle of an adaptive filter.

2.2 Classification of adaptive filters

Adaptive filters can be classified based on the choices made regarding the
following points:

16
 The optimization criterion;

The algorithm for updating the coefficientsffi

The structure of the programmable filter;

The type of signal processed, mono or multidimensional.

There are two important classes of optimal linear filters:

Wiener filtering (where the signals considered and are stationary},

Kalman filtering (which is a generalization of the Wiener filter also applicable in the)
cases of non-stationary processes (or signals).

2.3 Choice of the algorithm

The choice of the algorithm will be based on the following criteria:

The rate of convergence which will be the number of iterations necessary to
converging 'quite close' to the optimal solution,
The measure of this 'closeness' between this optimal solution and the solution
obtained
The ability to track variations (non-stationarities) of
system

The robustness to noise,

The complexity,

The structure (modularity, parallelism, ...),

The numerical properties (stability and accuracy) in the case of limited precision
on data and the coéffifilter coefficients.

17
2.4 Applications of Adaptive Filters

Adaptive filtering is a powerful tool in signal processing, communications

digital, and automatic control. The applications are diverse but present the
following characteristics: we have an entrance as well as the desired response
(reference) etl error what is the difference between and the filter outlet , hard
to control (adapt) the values of the coeffiClients of the filter. What essentially differentiates
The applications come from the way of defining the desired response. We can distinguish
four major classes of applications :[6][5] :

The identification of systems,

The prediction,

Equalization

Cancellation of interferences.

2.4.1 Identification

is the output of the system that we wish to identify.

Having access to the input and output of a linear filter whose output is noisy, a problem
Direct identification consists of estimating the unknown linear filter. This problem corresponds
to the diagram in figure (III.2). When the unknown system is likely to vary over time
time, the identification process can be carried out using adaptive processing
[7][5].

Figure II.2: Identification of a direct system.

18
2.4.2 Prediction

is the signal at the moment and the signal predicted from the signal at the times
previous
In this case, if the error approaches 0, then the filter can predict future samples of
signal which are based on previous observations. This can work on the
periodic signals
One of the applications is the extraction of signals buried in noise. One can also
used this system to mitigate the variations of a signal, but it is an application
impossible to achieve in real time [7][5].

Figure II.3: Principle of prediction.

2.4.3 Equalization

is the (delayed) input of the system that we seek to invert.

The goal is to estimate the data from the observations. If one chooses to minimize
the power of the error between the transmitted data and the output of the equalizer filter, the
the best linear solution is the Wiener filter whose transfer function in z is written

⁄
(II.1)
( ⁄ )

So the equalization is an 'inverse identification'

19
 Figure II.4: Principle of inverse modeling.

2.4.4 Noise subtraction (echo)

is a signal containing the useful signal and the interferences to be canceled. is a
signal lacking (or almost) information and obtained by a sensor close to interference.
A typical diagram of a noise subtraction device is that of figure (II.5). A signal
observed consists of a useful signal, unobserved that we want to estimate, polluted by a
supposed noise independent of the useful signal. When this noise on the observation is obtained by
linear filtering of a noise source near which it is possible to place a sensor, it
It becomes feasible to estimate the noise in order to then subtract it from the observed signal.

Figure II.5: Cancellation of Interferences.

3 Clean filters

The maximization of the signal-to-noise ratio at the output of a band-pass filter leads to the

determination of Eigenvalues

20
 Figure II.6: Linear filtering.

The signal x(n) is a stationary process with zero mean whose matrix
autocorrelation is It is {assumed
} that the noise u(n) is white with mean
none, of variance and decorrelated from the signal x(n).

We consider a RIF filter don't the heartsfficlients are The

the power of the signal at the output of the RIF filter is: {| |}
The signal-to-noise ratio is therefore:

(II.2)

The optimization problem can be formulated as follows: to determine the vector

(RIF filter) which will maximize the signal-to-noise ratio with the constraint

The equation(III.2)mobetween, except for the factor ⁄

the signal-to-noise ratio is equal to the Rayleigh quotient for the RIF filter:

(II.3)

We can see that the optimal filtering problem presented here can be viewed as a
eigenvalue problem. So we have:
The maximum value of the signal-to-noise ratio is given by:

(II.4)

Where is the largest eigenvalue of the autocorrelation matrix .

The optimal filter to achieve the highest signal-to-noise ratio east

(II.5)

21
Where is the eigenvector corresponding to the largest eigenvalue from the matrix
R.
Such a RIF filter is calledclean filter

4 Wiener filtering
Wiener filtering is suitable for situations where the signal or
noise is stationary [8]

4.1 Problem formulation

We have a set of samples from an input signal.{ } and one
set of samples of a desired response{ }.
In the family of filters calculating their output according to:

∑ (II.6)

Find the parameters{ } in such a way as to minimizethe error

mean square error (EQM or MSE) or criterion

{ } (II.7)

where the error signal is:

∑ (II.8)

The family of filters(II.6)is the family of linear RIF filters.

It is more convenient to use a matrix notation for the filter output:

(II.9)

Where is a vector of length containing the heartsfficlients of

RIF filter and is the vector of the input data
the most recent.

22
4.2 Principle of Orthogonality

The optimal vector is the one that cancels the gradient of the criterion[8]:

On a:

{ }

{ } (II.10)

Therefore, at the optimum, we have:

{ } (II.11)

Where is the error for which is minimized (for the optimal filter).
It is the principle of orthogonality meaning that all entries
are decorrelated from the error
In other words, the criterion attend its minimum if and only if the error is
orthogonal to the samples of the input signal .

At the optimum, we also have:

{ {} ∑ }

∑ { }

(II.12)

It is the corollary of theprinciple of orthogonality. are the coëfficoefficients of the optimal filter:

[ ]

In other words, when the criterion reaches its minimum then the error is
orthogonal to the output of the filter [8].

23
4.3 Wiener Equation

We know that for the optimal filter , we have { In}

developing this equation, we obtain:

{ [ ]}
Let it be:

{ } { } (II.13)

Or again

with solution: (II.14)

{ is the autocorrelation
} matrix of the input signal This
matrix is positive definite, Toeplitz, and symmetric. is { the vector
}
of intercorrelation between the desired and the entrance

The equation(III.15)is called the Wiener equation-

4.4 Minimum mean squared error (MSE)

The error signal is so the cost function can still

to write to each other { }
{ } { } { }
(II.15)

Where is{the}variance of the desired signal.

At the optimum, knowing that we have:

( )

(II.16)

Where is the optimal filtered signal and { } the variance of this

signal.

24
 This relationship shows that for the optimal filter, the MSE is the diffdifference between the
variance of the desired signal and that of the estimate of this signal produced by the filter.

Thus, the value of the minimum EQM (MMSE - minimum mean-square-error) for the filter
the optimal Wiener is:
(II.17)

The normalized minimal EQM is defined as follows:

(II.18)

The normalized minimum EQM is satisfied ̃

5 Common Optimization Algorithms

We have seen how signal processing problems can be reduced to
the optimization of a cost criterion as a function of a parameter vector. The case of filtering
Wiener RIF, our basic problem, leads to a function quadratic.

So we have to cancel the gradient, a linear system in (normal equations). However

adaptive implementation involves a recursive approach based on algorithms
optimization numbers. We then study their main representatives, who
serving as models for the construction of adaptive algorithms [5].

5.1 Deterministic gradient algorithm (steepest descent)

The deterministic gradient algorithm is a first approach to solve

the Wiener-Wopf equation iteratively, without the need to invert a matrix
[5][9].

Principle of the deterministic gradient algorithm

Let it be a cost function continuous and differentiable, depending on a vector

unknown .
We want to find an optimal solution. which satisfies [9] :

( ) (II.20)

25
The principle of a simple iterative algorithm is as follows:

Starting with an initial condition generate a sequence of vectors

in such a way that the value of the function decreases at each iteration:

(II.21)

We hope that the algorithm will converge towards the optimal solution.
A classic algorithm is the deterministic gradient algorithm:

(II.22)

where denotes the iteration, µ is a positive constant (no adaptation), and is the gradient
of the cost function

(II.23)

From the iteration to the iteration the vector is updated as follows:

(II.24)

To show that the deterministic gradient algorithm satisfies on

use a first-order Taylor expansion around :

(II.25)

What is justified for µ small. We have therefore:

‖ ‖ (II.26)

This shows that is smaller than Thus, by increasing , the

function decreases gradually, approaching its minimal value when

5.1.1 Application of the deterministic gradient algorithm to Wiener filtering

In Wiener filtering, we minimize the mean squared error (MSE):

{ } (II.27)

26
Where is the error signal, is a FIR filter of length L, is the input signal, and
is the desired signal.

(II.28)

The gradient of est :

{ }
{ }
(II.29)

We deduce the deterministic gradient algorithm for Wiener filtering:

(II.30)

This algorithm can still be written using the error signal:

(II.31)

Eventually, at infinity, the algorithm converges to the optimal Wiener solution. :

(II.32)

5.2 Stochastic gradient algorithm (least-mean-square –LMS):

The LMS algorithm is a search algorithm in which a simplification of

the calculation of the gradient vector is made possible by suitably modifying the function
objective. The LMS algorithm, as well as others related to it, is commonly used.
in various applications of adaptive filtering due to computational simplicity. The
The convergence characteristics of the LMS algorithm are examined to establish a range.
of values for the convergence factor that will ensure stability [10][11].

27
The convergence speed of LMS proves to be dependent on the choice of the adaptation step. According to

The studies conducted, the choice of the adjustment step is essential for proper functioning.
the LMS. In order to find a compromise between the speed of convergence and performance of
the algorithm, some algorithms are developed with a variable step [5].

5.2.1 Principle of the LMS stochastic gradient algorithm:

Since and
{ are} unknown,{ we will }approach these
deterministic quantities through estimates ̂ and̂ at the moment In the case of the LMS, we
choose the simplest possible estimates, namely :[11]

̂ (II.33)
̂ (II.34)

These are simply the instantaneous estimates of the correlations.

By replacing ̂ ̂ in the deterministic gradient algorithm equation (II.22) we

and
obtains

[̂ ] ̂

(II.35)

What is the LMS algorithm. It should be noted that is now a random variable
since at each new iteration , depends on random processes and ].

The LMS algorithm is very simple: it only requires multiplications and

additions by iteration, where is the number of coéffifilter coefficients.

5.2.2 Variants of the LMS algorithm

There are many variants of the LMS algorithm. We will see a few of them.
ones that are very useful.

5.3 Normalized LMS Algorithm (Normalized LMS –NLMS)

For non-stationary signals (the energy of the signal varies with time,
the LMS algorithm will struggle to work properly since is constant

The normalized LMS algorithm (Normalized LMS –NLMS) was created to address this.
problem in minimizing the following cost function[5][9]:

28
 ‖ ‖ (II.36)

With the constraint:

(II.37)

This amounts to minimizing the update of the filter coefficients while minimizing the signal.
of error for .

The solution to this problem is obtained using the technique of Lagrange multipliers.
Indeed, we will seek to minimize with respect to :

‖ ‖

Where is the Lagrange multiplier. We obtain:

(II.38)

Let it be:

(II.40)

Or, according to the constraint of equation (II.37):

(II.41)

What gives:

(II.42)

Finally, we obtain the NLMS algorithm by replacing equation (II.42) in the equation
(II.40) :

(II.43)

In practice, to better control the update of the filter coefficients, we introduce a

positive factor where :

29
In fact, for sufficiently large and for a stationary signal, we have:

∑
(II.45)

(II.46)

is the adaptation step of the LMS.

To avoid numerical difficulties (division by small numbers) when the energy of the
the input signal is small, we modify the algorithm as follows:

(II.47)

Where is a regularization parameter.

Regarding the stability of the NLMS algorithm, it is assumed that The error of
signal also called 'a priori' error because it uses the filter coefficients before the setting
day is :

(II.48)

The 'a posteriori' error is calculated once the update has been made and is defined by:

(II.49)

The algorithm can be considered stable if the absolute value of the "a posteriori" error.
is smaller than that of the 'a priori' error, which makes sense since exploit
more information.

By substituting the NLMS equation (II.44) into the equation (II.49) of the 'a posteriori' error,
we obtain:

(II.49)

So | |||

| |

30
 | |

(II.50)

What is the stability condition of the NLMS algorithm.

6 Conclusion
In this chapter, we defined discrete signals and their time representations.
frequencies. Discrete filters have also been defined as linear systems that
are mathematically represented by convolutions in the time domain and by
products of rational polynomials in the frequency domain. Adaptive IIR filters have
were also introduced and several adaptation methods, based on optimizations, have
were presented. In the following chapter, we will consider block adaptive filters in the
two temporal and frequency domains.

31