Adaptive_filter - Wikiparency

# Adaptive filter An **adaptive filter** is a [[Digital_filter|digital filter]] whose coefficients are not fixed by design but adjusted while it runs, by an [[Algorithm|algorithm]] that watches an error signal and changes the coefficients so as to make that error smaller on the next sample. The filter itself is usually an ordinary [[Finite_impulse_response|finite impulse response]] structure; what makes it adaptive is the loop wrapped around it. The loop is needed whenever the [[Transfer_function|transfer function]] that would do the job is unknown or changing: the acoustic path from a [[Loudspeaker|loudspeaker]] to a microphone, the [[Reverberation|reverberation]] of a room, the response of a telephone line, or the way a noise source leaks into a sensor. In each case the filter is told only what to minimise, and it discovers the coefficients itself. The most common criterion is the mean square of the error, and the most common algorithm is the least-mean-squares rule of Widrow and Hoff, published in 1960, which changes each coefficient by a step proportional to the error times the input sample that coefficient multiplies.[^wh60] The rule costs one multiply-add per coefficient per sample, needs no matrix inversion, and converges to the [[Wiener_filter]] solution for stationary inputs; its exact-least-squares cousin, recursive least squares, converges faster at higher cost, and the [[Kalman_filter]] is the same idea carried into state space. This article's microsim, *Adaptive filter*, runs a least-mean-squares noise canceller on a tone buried in noise, and lets the reader set the step size and the filter length while watching the coefficients converge onto the unknown noise path, the cleaned output climb out of the noise, and the learning curve fall. ## Example application The microsim runs the interference-cancelling configuration described by Widrow and his colleagues in 1975.[^widrow75] A primary sensor picks up the wanted signal `s[n]` corrupted by noise, `d[n] = s[n] + nP[n]`. A second, reference sensor picks up the noise source `x[n]` alone, before it has travelled through whatever unknown path turns it into `nP[n]`. The adaptive filter runs on the reference, producing `y[n]` as its guess of the noise in the primary, and the error `e[n] = d[n] - y[n]` is the cleaned output. Because `s[n]` is uncorrelated with `x[n]`, nothing the filter does to `x[n]` can cancel `s[n]`; the only way to shrink the mean-square error is to make `y[n]` match `nP[n]`, so minimising the error rebuilds the unknown path and leaves the signal standing. In the sketch the wanted signal is a 6 Hz [[Sine_wave|sine wave]] of unit amplitude at a sample rate of 200 Hz, and the reference is coloured noise, white noise passed through a one-pole [[Low-pass_filter|low-pass filter]] with a pole at 0.6. The unknown path is five taps long, `h = [0.90, -0.55, 0.35, 0.18, -0.10]`, and the filter starts with all its coefficients at zero. Its length `N` is 8 by default and its step size `mu` is 0.080. On the scope the grey primary trace shows the tone drowned in noise; within a few seconds of sketch time the orange cleaned output takes the shape of the faint cyan tone, and in the coefficient panel the cyan stems rise to meet the amber ticks marking the true path. The diagnostics panel gives the numbers. It reports the coefficient misalignment `||w - h||`, the distance between the learned and the true taps, and the noise suppression in [[Decibel|decibels]], the ratio of the noise power in the primary to the residual noise power `E[(nP - y)^2]` left in the output. At the default settings the stems find the shape of the path quickly but keep jittering about it: the misalignment settles near 0.4 rather than at zero, the suppression readout hovers around 2 dB, and the verdict line mostly reads "ADAPTING". The jitter is the tone's doing. The tone sits in the error, the error drives every coefficient update, and so the wanted signal itself shakes the coefficients at every step; with a smaller step size the shaking is smaller and the cancellation deeper. At `mu` = 0.010 the sketch's suppression readout climbs to about 12 dB, and at 0.003 to about 18 dB with the misalignment near 0.07, but each halving of the step roughly doubles the time the filter takes to get there, from tens of seconds to minutes. ## Block diagram ### Tapped delay line FIR filter The filter that adapts is a tapped delay line: the `N` most recent input samples are held, each is multiplied by its own coefficient, and the products are summed, `y[n] = sum_k w_k*x[n-k]` for `k` from 0 to `N-1`.[^stiber72] It is the [[Convolution|convolution]] of the input with a finite [[Impulse_response|impulse response]], and its [[Frequency_response|frequency response]] follows from the coefficients through the [[Z-transform|z-transform]].[^stiber74] Nothing in the structure is adaptive; the coefficients are simply variables that another process writes. ### Ideal case If the unknown path is itself a finite impulse response no longer than the filter, an exact solution exists: with `w = h` the filter reproduces the noise sample for sample, the residual `nP - y` is identically zero, and the error is the clean signal `s[n]`. The sketch's path has five taps and its filter has eight, so the ideal is reachable, with the three surplus coefficients ideally at zero. With `N` set below five the filter is too short, and the misalignment readout carries the note "can't fully fit"; at `N` = 3 the two unmodelled taps leave a floor of about 0.21 in the misalignment however the step size is set. ### Signal components in the reference input The reference must contain the noise, correlated with what reaches the primary, and must not contain the signal. If it does contain some of the signal, the filter will cancel that too, since it cannot tell the two apart; the outcome is a partly cancelled signal and a distorted output. Correlation here has its ordinary meaning, the normalised inner product of two sequences, which is the cosine of the angle between them when both are zero-mean and of unit variance.[^downey72] The sketch keeps the reference clean of the tone; the tone leaks into the adaptation only through the error, as the jitter described above. ### Adaptive Linear Combiner Seen abstractly, the tapped delay line is a linear combiner: an output that is a weighted sum of inputs, with the weights free. For fixed input statistics the mean-square error is a quadratic function of the weight vector, a bowl whose minimum is the [[Wiener_filter|Wiener]] solution `w_opt = R^-1*p`, where `R` is the [[Autocorrelation|autocorrelation]] matrix of the input vector and `p` its cross-correlation with the desired signal. Every adaptive algorithm is a way of descending that bowl without computing `R` and `p` explicitly. ### LMS algorithm The least-mean-squares algorithm descends the bowl by steepest descent with the crudest possible gradient estimate, the instantaneous one: it replaces the [[Expected_value|expected]] squared error by the current squared error, whose gradient with respect to `w_k` is `-2*e[n]*x[n-k]`. The update is `w_k <- w_k + mu*e[n]*x[n-k]`, applied to every coefficient after every sample, and it is the entire algorithm.[^wh60] The sketch's HUD shows this one line, and its `step()` function applies it once per sample with the same `mu` for every tap. A normalised variant divides the step by the input power so that the effective step does not change when the input level does. #### Convergence The gradient estimate is noisy, so the weights do not settle at the bottom of the bowl but wander about it, and the wandering costs an excess mean-square error, the misadjustment, that grows with the step size and with the number of taps. Convergence in the mean requires `0 < mu < 2/lambda_max`, where `lambda_max` is the largest eigenvalue of `R`; since the eigenvalues sum to `N` times the input power `Px`, the bound `mu < 2/(N*Px)` is the conservative form, and it is the one the sketch's panel displays against the current `mu`. Each eigenvalue also sets a time constant `1/(mu*lambda_i)`, so a coloured input, whose eigenvalues are spread, converges slowly along its weak directions however the step is chosen; for the sketch's one-pole reference the spread works out to about twelve at `N` = 8. The displayed bound governs the mean weights only. Convergence of the mean-square error needs a smaller step, and in the sketch the weights in fact blow up well before the displayed bound is reached: at `N` = 24 the panel shows a bound of about 0.39, but the coefficients run away from about `mu` = 0.25, and the verdict does not read "DIVERGING" until `mu` passes the displayed figure. ### Nonlinear Adaptive Filters When the unknown path is not linear, as when a loudspeaker distorts before its output reaches the microphone, a linear combiner cannot fit it however long it is made. Nonlinear adaptive filters extend the combiner with products of delayed inputs, the Volterra structure, or replace it with a [[Neural_network_(machine_learning)|neural network]] trained by the same error signal; both keep the loop and change only what sits inside it. ## Applications of adaptive filters The canonical application is echo cancellation. On a long telephone circuit the far talker's voice returns as an echo through the hybrid at the near end, and an adaptive filter fed with the far signal learns the echo path and subtracts it; Sondhi's adaptive echo canceller of 1967 was among the first practical uses of the idea.[^sondhi67] Hands-free telephony and video conferencing do the same for the acoustic path from loudspeaker to microphone, a path that changes whenever someone moves. Adaptive equalisation of a communication channel, in which the filter undoes the channel's distortion, dates from Lucky's work of 1965 and sits in every modem.[^lucky65] Noise cancelling in the sketch's configuration was demonstrated in 1975 on electrocardiograms, where the mother's heartbeat is subtracted from a fetal recording, and on speech in noisy environments.[^widrow75] [[Active_noise_control]] uses the same loop with a loudspeaker in it, cancelling [[Sound|sound]] in air rather than a signal in a wire. [[System_identification]] is the application turned inside out: the filter is driven with the same input as an unknown system and adapted until their outputs agree, after which its coefficients are the model. Adaptive beamforming in [[Radar|radar]] and [[Sonar|sonar]] arrays applies the same weights across sensors rather than across time. ## Filter implementations Almost all adaptive filters are finite-impulse-response structures, because the error surface of an FIR combiner is a single quadratic bowl with no local minima, and the structure has no poles that adaptation could push outside the unit circle. Adaptive [[Infinite_impulse_response|infinite impulse response]] filters model long paths with fewer coefficients but can place a pole outside the unit circle during adaptation, so they are used with care. Within the FIR family the algorithms differ in cost and speed. Least mean squares costs `N` multiply-adds per sample and converges at a rate set by the input's eigenvalue spread. Recursive least squares solves the least-squares problem exactly at every sample, updating the estimate and its covariance so that the recursive result equals the batch solution; the quantity that drives the update is the predicted residual, the error of the previous coefficients on the new data, and the cost is of order `N^2` per sample.[^teu33] Its convergence does not depend on the eigenvalue spread, which is why it is preferred where the input is strongly coloured, as in equalisers; a forgetting factor lets it track a changing path. Between the two sit the normalised and the transform-domain forms of least mean squares, which whiten the input cheaply, and block or frequency-domain implementations that apply the update once per block using the [[Fast_Fourier_transform|fast Fourier transform]], the usual choice for the thousands of taps an acoustic echo canceller needs. Lattice structures order the coefficients by delay so that the filter length can be changed without restarting the adaptation. In fixed-point hardware the step size, the coefficient word length and the input scaling are chosen together, since a small step and a short word can stall the adaptation entirely. ## Microsims The *Adaptive filter* sketch is a least-mean-squares noise canceller on a dark scope with three panels. The time-domain panel shows the grey primary `d(n)`, the faint cyan true tone `s(n)` and the orange cleaned output `e(n)`, which should settle onto the cyan guide. The coefficient panel shows the learned taps as cyan stems against amber ticks marking the true five-tap path. The learning-curve panel plots the residual noise power on a log scale and lists the diagnostics: the step size, the stability bound `2/(N*Px)` with an "ok" or "TOO BIG" note, the coefficient misalignment `||w-h||`, the noise suppression in dB, and a verdict of DIVERGING, ADAPTING or CONVERGED. **STEP SIZE mu** runs from 0.001 to 0.600 with a default of 0.080; **FILTER LENGTH N** runs from 1 to 24 taps with a default of 8, and changing it restarts the coefficients from zero; **reset weights** restarts the learning, and **pause** freezes the adaptation for inspection. The sketch is ILLUSTRATIVE in two respects: the reference noise is generated inside the sketch rather than measured, and the displayed stability bound is the mean-convergence bound, which the mean-square behaviour does not honour. *Try:* Leave N at 8 and drag mu from 0.080 down to 0.005; watch the cyan stems stop jittering around the amber ticks, the misalignment readout fall from about 0.4 toward 0.1, and the noise suppression climb from about 2 dB toward 15 dB, over a minute or more. Then set N to 24 and mu to 0.45 and watch the verdict turn to DIVERGING as the orange trace leaves the scope. A three.js companion on this page renders the error bowl and the descent of the weight vector in depth.  **Microsim — three.js (Wikitube framework), pending deploy:** *Adaptive filters: LMS descending the error bowl* will play here once `https://wikitube-3d-microsims.netlify.app/signal/Adaptive_filter.html` is live.  *Built from `MICROSIM_GUIDE/specs/sims/Adaptive_filter.json`; part of the [[Signal_processing]] set ([[PORTAL_Signal_Processing]]).*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Adaptive_filter) : [Wikitube](https://en.wikitube.io/wiki/Adaptive_filter) Skeleton mirrored at revision 1371735912. Prose, emphasis and the microsims are Wikitube's own. ## See also - [[Active_noise_control]] - [[System_identification]] - [[Wiener_filter]] - [[Kalman_filter]] - [[Digital_filter]] - [[Finite_impulse_response]] - [[Filter_(signal_processing)]] - [[Mathematical_optimization]] ## References Page numbers for the Portal Books are PDF pages of the open editions. [^wh60]: Widrow, B.; Hoff, M. E. "Adaptive switching circuits." *IRE WESCON Convention Record*, Part 4, 1960, pp. 96–104. [^widrow75]: Widrow, B.; Glover, J. R.; McCool, J. M.; et al. "Adaptive noise cancelling: Principles and applications." *Proceedings of the IEEE* 63(12), December 1975, pp. 1692–1716. [^stiber72]: Stiber, M.; Stiber, B.; Larson, E. *Signal Computing: Digital Signals in the Software Domain*. 2020, p. 72 (PDF page). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/signal-computing-digital-signals-in-the-software-domain . CC BY-SA. [^stiber74]: Stiber, M.; Stiber, B.; Larson, E. *Signal Computing: Digital Signals in the Software Domain*. 2020, p. 74 (PDF page). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/signal-computing-digital-signals-in-the-software-domain . CC BY-SA. [^downey72]: Downey, A. *Think DSP: Digital Signal Processing in Python*. 2012, pp. 63–66 and 72 (PDF pages). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python . CC BY-NC. [^sondhi67]: Sondhi, M. M. "An adaptive echo canceller." *Bell System Technical Journal* 46(3), March 1967, pp. 497–511. [^lucky65]: Lucky, R. W. "Automatic equalization for digital communication." *Bell System Technical Journal* 44(4), April 1965, pp. 547–588. [^teu33]: Teunissen, P. J. G. *Network quality control*. 2024, pp. 33–35 (PDF pages): the recursive least-squares update, its equality with the batch solution, and the predicted residual. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/network-quality-control . CC BY. ### Sources - Stiber, M.; Stiber, B.; Larson, E. *Signal Computing: Digital Signals in the Software Domain* (2020), CC BY-SA: feedforward FIR filters, delays and zeros. https://open.umn.edu/opentextbooks/textbooks/signal-computing-digital-signals-in-the-software-domain - Downey, A. *Think DSP: Digital Signal Processing in Python* (2012), CC BY-NC: noise, correlation and autocorrelation. https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python - Teunissen, P. J. G. *Network quality control* (2024), CC BY: recursive least squares. https://open.umn.edu/opentextbooks/textbooks/network-quality-control - Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory* (2026), CC BY: the portal's core text on linear filtering. https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory