Adaptive filter

An adaptive filter is a system with a linear filter that has a transfer function controlled by variable parameters and a means to adjust those parameters according to an optimization algorithm. Because of the complexity of the optimization algorithms, almost all adaptive filters are digital filters. Adaptive filters are required for some applications because some parameters of the desired processing operation (for instance, the locations of reflective surfaces in a reverberant space) are not known in advance or are changing. The closed loop adaptive filter uses feedback in the form of an error signal to refine its transfer function.

Generally speaking, the closed loop adaptive process involves the use of a cost function, which is a criterion for optimum performance of the filter, to feed an algorithm, which determines how to modify filter transfer function to minimize the cost on the next iteration. The most common cost function is the mean square of the error signal.

As the power of digital signal processors has increased, adaptive filters have become much more common and are now routinely used in devices such as mobile phones and other communication devices, camcorders and digital cameras, and medical monitoring equipment.

Example application

The recording of a heart beat (an ECG), may be corrupted by noise from the AC mains. The exact frequency of the power and its harmonics may vary from moment to moment.

One way to remove the noise is to filter the signal with a notch filter at the mains frequency and its vicinity, but this could excessively degrade the quality of the ECG since the heart beat would also likely have frequency components in the rejected range.

To circumvent this potential loss of information, an adaptive filter could be used. The adaptive filter would take input both from the patient and from the mains and would thus be able to track the actual frequency of the noise as it fluctuates and subtract the noise from the recording. Such an adaptive technique generally allows for a filter with a smaller rejection range, which means, in this case, that the quality of the output signal is more accurate for medical purposes. ^{[1] [2]}

Block diagram

The idea behind a closed loop adaptive filter is that a variable filter is adjusted until the error (the difference between the filter output and the desired signal) is minimized. The Least Mean Squares (LMS) filter and the Recursive Least Squares (RLS) filter are types of adaptive filter.

Adaptive Filter. k = sample number, x = reference input, X = set of recent values of x, d = desired input, W = set of filter coefficients, ε = error output, f = filter impulse response, * = convolution, Σ = summation, upper box=linear filter, lower box=adaption algorithm

Adaptive Filter, compact representation. k = sample number, x = reference input, d = desired input, ε = error output, f = filter impulse response, Σ = summation, box=linear filter and adaption algorithm.

There are two input signals to the adaptive filter: ${\displaystyle d_{k}}$ and ${\displaystyle x_{k}}$ which are sometimes called the primary input and the reference input respectively. ^[3] The adaptation algorithm attempts to filter the reference input into a replica of the desired input by minimizing the residual signal, ${\displaystyle \epsilon _{k}}$. When the adaptation is successful, the output of the filter ${\displaystyle y_{k}}$ is effectively an estimate of the desired signal.

${\displaystyle d_{k}}$ which includes the desired signal plus undesired interference and

${\displaystyle x_{k}}$ which includes the signals that are correlated to some of the undesired interference in ${\displaystyle d_{k}}$.

k represents the discrete sample number.

The filter is controlled by a set of L+1 coefficients or weights.

${\displaystyle \mathbf {W} _{k}=\left[w_{0k},\,w_{1k},\,...,\,w_{Lk}\right]^{T}}$ represents the set or vector of weights, which control the filter at sample time k.

where ${\displaystyle w_{lk}}$ refers to the ${\displaystyle l}$'th weight at k'th time.

${\displaystyle \mathbf {\Delta W} _{k}}$ represents the change in the weights that occurs as a result of adjustments computed at sample time k.

These changes will be applied after sample time k and before they are used at sample time k+1.

The output is usually ${\displaystyle \epsilon _{k}}$ but it could be ${\displaystyle y_{k}}$ or it could even be the filter coefficients. ^[4] (Widrow)

The input signals are defined as follows:

${\displaystyle d_{k}=g_{k}+u_{k}+v_{k}}$

${\displaystyle x_{k}=g_{k}^{'}+u_{k}^{'}+v_{k}^{'}}$

where:

g = the desired signal,

g' = a signal that is correlated with the desired signal g ,

u = an undesired signal that is added to g , but not correlated with g or g'

u' = a signal that is correlated with the undesired signal u, but not correlated with g or g',

v = an undesired signal (typically random noise) not correlated with g, g', u, u' or v',

v' = an undesired signal (typically random noise) not correlated with g, g', u, u' or v.

The output signals are defined as follows:

${\displaystyle y_{k}={\hat {g}}_{k}+{\hat {u}}_{k}+{\hat {v}}_{k}}$

${\displaystyle \epsilon _{k}=d_{k}-y_{k}}$.

where:

${\displaystyle {\hat {g}}}$ = the output of the filter if the input was only g',

${\displaystyle {\hat {u}}}$ = the output of the filter if the input was only u',

${\displaystyle {\hat {v}}}$ = the output of the filter if the input was only v'.

Tapped delay line FIR filter

If the variable filter has a tapped delay line Finite Impulse Response (FIR) structure, then the impulse response is equal to the filter coefficients. The output of the filter is given by

${\displaystyle y_{k}=\sum _{l=0}^{L}w_{lk}\ x_{(k-l)}={\hat {g}}_{k}+{\hat {u}}_{k}+{\hat {v}}_{k}}$

where ${\displaystyle w_{lk}}$ refers to the ${\displaystyle l}$'th weight at k'th time.

Ideal case

In the ideal case ${\displaystyle v\equiv 0,v'\equiv 0,g'\equiv 0}$. All the undesired signals in ${\displaystyle d_{k}}$ are represented by ${\displaystyle u_{k}}$. ${\displaystyle \ x_{k}}$ consists entirely of a signal correlated with the undesired signal in ${\displaystyle u_{k}}$.

The output of the variable filter in the ideal case is

${\displaystyle y_{k}={\hat {u}}_{k}}$ .

The error signal or cost function is the difference between ${\displaystyle d_{k}}$ and ${\displaystyle y_{k}}$

${\displaystyle \epsilon _{k}=d_{k}-y_{k}=g_{k}+u_{k}-{\hat {u}}_{k}}$. The desired signal g_k passes through without being changed.

The error signal ${\displaystyle \epsilon _{k}}$ is minimized in the mean square sense when ${\displaystyle [u_{k}-{\hat {u}}_{k}]}$ is minimized. In other words, ${\displaystyle {\hat {u}}_{k}}$ is the best mean square estimate of ${\displaystyle u_{k}}$. In the ideal case, ${\displaystyle u_{k}={\hat {u}}_{k}}$ and ${\displaystyle \epsilon _{k}=g_{k}}$, and all that is left after the subtraction is ${\displaystyle g}$ which is the unchanged desired signal with all undesired signals removed.

Signal components in the reference input

In some situations, the reference input ${\displaystyle x_{k}}$ includes components of the desired signal. This means g' ≠ 0.

Perfect cancelation of the undesired interference is not possible in the case, but improvement of the signal to interference ratio is possible. The output will be

${\displaystyle \epsilon _{k}=d_{k}-y_{k}=g_{k}-{\hat {g}}_{k}+u_{k}-{\hat {u}}_{k}}$. The desired signal will be modified (usually decreased).

The output signal to interference ratio has a simple formula referred to as power inversion.

${\displaystyle \rho _{\mathsf {out}}(z)={\frac {1}{\rho _{\mathsf {ref}}(z)}}}$.

where

${\displaystyle \rho _{\mathsf {out}}(z)\ }$ = output signal to interference ratio.

${\displaystyle \rho _{\mathsf {ref}}(z)\ }$ = reference signal to interference ratio.

${\displaystyle z\ }$ = frequency in the z-domain.

This formula means that the output signal to interference ratio at a particular frequency is the reciprocal of the reference signal to interference ratio. ^[5]

Example: A fast food restaurant has a drive-up window. Before getting to the window, customers place their order by speaking into a microphone. The microphone also picks up noise from the engine and the environment. This microphone provides the primary signal. The signal power from the customer's voice and the noise power from the engine are equal. It is difficult for the employees in the restaurant to understand the customer. To reduce the amount of interference in the primary microphone, a second microphone is located where it is intended to pick up sounds from the engine. It also picks up the customer's voice. This microphone is the source of the reference signal. In this case, the engine noise is 50 times more powerful than the customer's voice. Once the canceler has converged, the primary signal to interference ratio will be improved from 1:1 to 50:1.

Adaptive Linear Combiner

Adaptive linear combiner showing the combiner and the adaption process. k = sample number, n=input variable index, x = reference inputs, d = desired input, W = set of filter coefficients, ε = error output, Σ = summation, upper box=linear combiner, lower box=adaption algorithm.

Adaptive linear combiner, compact representation. k = sample number, n=input variable index, x = reference inputs, d = desired input, ε = error output, Σ = summation.

The adaptive linear combiner (ALC) resembles the adaptive tapped delay line FIR filter except that there is no assumed relationship between the X values. If the X values were from the outputs of a tapped delay line, then the combination of tapped delay line and ALC would comprise an adaptive filter. However, the X values could be the values of an array of pixels. Or they could be the outputs of multiple tapped delay lines. The ALC finds use as an adaptive beam former for arrays of hydrophones or antennas.

${\displaystyle y_{k}=\sum _{l=0}^{L}w_{lk}\ x_{lk}=\mathbf {W} _{k}^{T}\mathbf {x} _{k}}$

where ${\displaystyle w_{lk}}$ refers to the ${\displaystyle l}$'th weight at k'th time.

LMS algorithm

Main article: Least mean squares filter

If the variable filter has a tapped delay line FIR structure, then the LMS update algorithm is especially simple. Typically, after each sample, the coefficients of the FIR filter are adjusted as follows: ^[6]

for ${\displaystyle l=0\dots L}$

${\displaystyle w_{l,k+1}=w_{lk}+2\mu \ \epsilon _{k}\ x_{k-l}}$

μ is called the convergence factor.

The LMS algorithm does not require that the X values have any particular relationship; therefore it can be used to adapt a linear combiner as well as an FIR filter. In this case the update formula is written as:

${\displaystyle w_{l,k+1}=w_{lk}+2\mu \ \epsilon _{k}\ x_{lk}}$

The effect of the LMS algorithm is at each time, k, to make a small change in each weight. The direction of the change is such that it would decrease the error if it had been applied at time k. The magnitude of the change in each weight depends on μ, the associated X value and the error at time k. The weights making the largest contribution to the output, ${\displaystyle y_{k}}$, are changed the most. If the error is zero, then there should be no change in the weights. If the associated value of X is zero, then changing the weight makes no difference, so it is not changed.

Convergence

μ controls how fast and how well the algorithm converges to the optimum filter coefficients. If μ is too large, the algorithm will not converge. If μ is too small the algorithm converges slowly and may not be able to track changing conditions. If μ is large but not too large to prevent convergence, the algorithm reaches steady state rapidly but continuously overshoots the optimum weight vector. Sometimes, μ is made large at first for rapid convergence and then decreased to minimize overshoot.

Widrow and Stearns state in 1985 that they have no knowledge of a proof that the LMS algorithm will converge in all cases. ^[7]

However under certain assumptions about stationarity and independence it can be shown that the algorithm will converge if

${\displaystyle 0<\mu <{\frac {1}{\sigma ^{2}}}}$

where

${\displaystyle \sigma ^{2}=\sum _{l=0}^{L}\sigma _{l}^{2}}$ = sum of all input power

${\displaystyle \sigma _{l}}$ is the RMS value of the ${\displaystyle l}$'th input

In the case of the tapped delay line filter, each input has the same RMS value because they are simply the same values delayed. In this case the total power is

${\displaystyle \sigma ^{2}=(L+1)\sigma _{0}^{2}}$

where

${\displaystyle \sigma _{0}}$ is the RMS value of ${\displaystyle x_{k}}$, the input stream. ^[7]

This leads to a normalized LMS algorithm:

${\displaystyle w_{l,k+1}=w_{lk}+\left({\frac {2\mu _{\sigma }}{\sigma ^{2}}}\right)\epsilon _{k}\ x_{k-l}}$ in which case the convergence criteria becomes: ${\displaystyle 0<\mu _{\sigma }<1}$.

Nonlinear Adaptive Filters

The goal of nonlinear filters is to overcome limitation of linear models. There are some commonly used approaches: Volterra LMS, Kernel adaptive filter, Spline Adaptive Filter ^[8] and Urysohn Adaptive Filter. ^{[9] [10]} Many authors ^[11] include also Neural networks into this list. The general idea behind Volterra LMS and Kernel LMS is to replace data samples by different nonlinear algebraic expressions. For Volterra LMS this expression is Volterra series. In Spline Adaptive Filter the model is a cascade of linear dynamic block and static non-linearity, which is approximated by splines. In Urysohn Adaptive Filter the linear terms in a model

${\displaystyle y_{i}=\sum _{j=0}^{m}w_{j}\ x_{ij}}$

are replaced by piecewise linear functions

${\displaystyle y_{i}=\sum _{j=0}^{m}f_{j}(x_{ij})}$

which are identified from data samples.

Applications of adaptive filters

• Adaptive Noise Cancelling
• Acoustic Noise Control
• Signal prediction
• Adaptive feedback cancellation
• Echo cancellation

Filter implementations

• Least mean squares filter
• Recursive least squares filter
• Multidelay block frequency domain adaptive filter

See also

• 2D adaptive filters
• Filter (signal processing)
• Kalman filter
• Kernel adaptive filter
• Linear prediction
• MMSE estimator
• Wiener filter
• Wiener–Hopf equation

References

1. Thakor, N.V.; Zhu, Yi-Sheng (1991-08-01). "Applications of adaptive filtering to ECG analysis: noise cancellation and arrhythmia detection". IEEE Transactions on Biomedical Engineering. 38 (8): 785–794. doi:10.1109/10.83591. ISSN   0018-9294. PMID   1937512. S2CID   11271450.
2. Widrow, Bernard; Stearns, Samuel D. (1985). Adaptive Signal Processing (1st ed.). Prentice-Hall. p.  329. ISBN   978-0130040299.
3. Widrow p 304
4. Widrow p 212
5. Widrow p 313
6. Widrow p. 100
7. Widrow p 103
8. Danilo Comminiello; José C. Príncipe (2018). Adaptive Learning Methods for Nonlinear System Modeling. Elsevier Inc. ISBN   978-0-12-812976-0.
9. M.Poluektov and A.Polar. Urysohn Adaptive Filter. 2019.
10. "Nonlinear Adaptive Filtering". ezcodesample.com.
11. Weifeng Liu; José C. Principe; Simon Haykin (March 2010). Kernel Adaptive Filtering: A Comprehensive Introduction (PDF). Wiley. pp. 12–20. ISBN   978-0-470-44753-6.

Sources

• Hayes, Monson H. (1996). Statistical Digital Signal Processing and Modeling. Wiley. ISBN   978-0-471-59431-4.
• Haykin, Simon (2002). Adaptive Filter Theory. Prentice Hall. ISBN   978-0-13-048434-5.
• Widrow, Bernard; Stearns, Samuel D. (1985). Adaptive Signal Processing. Englewood Cliffs, NJ: Prentice Hall. ISBN   978-0-13-004029-9.