Adaptive Filters & LMS

Chapter 1: The Wiener Filter

Before going adaptive, let's find the optimal filter assuming we know the statistics. This is the Wiener filter — the gold standard that adaptive methods try to approximate.

We want to minimize the mean squared error:

Expand this:

Define the autocorrelation matrix and cross-correlation vector:

Then J(w) = σ_d² − 2w^Tr_ud + w^TR_uw. Taking the gradient and setting to zero:

The MSE Surface

J(w) is a quadratic bowl in w-space. The minimum is at w_opt, and the minimum MSE is:

The eigenvalues of R_u determine the shape of the bowl. If the eigenvalues are spread (high eigenvalue spread = ratio λ_max/λ_min), the bowl is elongated — a narrow valley. This makes gradient descent slow, as we'll see.

Worked Example: 2-Tap Wiener Filter

Suppose u[n] is white noise with σ_u² = 1 (so R_u = I₂), and the cross-correlation is r_ud = [0.8, −0.3]^T. Then:

The minimum MSE is J_min = σ_d² − r_ud^Tw_opt. If σ_d² = 1, then J_min = 1 − (0.64 + 0.09) = 0.27. The filter removes 73% of the error power.

For correlated input (non-identity R_u), the contours become elliptical, and the condition number κ = λ_max/λ_min controls how elongated they are. Gradient descent spirals slowly through elongated valleys.

Chapter 2: Gradient Descent on the MSE Surface

Instead of inverting R_u, we can slide down the MSE bowl using gradient descent. The gradient of J(w) is:

The steepest descent update:

where μ is the step size (learning rate). This still requires R_u and r_ud, but it avoids the matrix inverse. Each step costs O(M²) instead of O(M³).

Convergence in Eigenvector Coordinates

Transform to the eigenvector basis of R_u: let v = Q^T(w − w_opt), where Q diagonalizes R_u. Each component of v evolves independently:

where λ_k is the k-th eigenvalue of R_u. For convergence, we need |1 − 2μλ_k| < 1 for all k, which gives:

The Eigenvalue Spread Problem

The convergence time constant for mode k is τ_k = 1/(2μλ_k). The slowest mode has τ_max = 1/(2μλ_min). But μ must stay below 1/λ_max, so the worst case is:

where χ(R_u) = λ_max/λ_min is the condition number. High condition number → slow convergence. This motivates normalized variants of LMS.

Chapter 3: The LMS Algorithm

Steepest descent requires the true gradient ∇J = 2R_uw − 2r_ud, which requires the ensemble statistics R_u and r_ud. Widrow and Hoff's insight (1960): replace the ensemble average with the instantaneous value.

The true gradient is E[2u_n(u_n^Tw − d[n])] = E[−2u_ne[n]]. The instantaneous (single-sample) approximation is just −2u_ne[n]. This gives the Least Mean Squares (LMS) algorithm:

Derivation from Stochastic Gradient Descent

LMS is stochastic gradient descent (SGD) on the MSE cost. The instantaneous cost at sample n is:

The gradient: ∇J_n = −2u_ne[n]. So the update w[n+1] = w[n] − (μ/2)∇J_n = w[n] + μ·e[n]·u_n. (We absorb the factor of 2 into μ.)

The gradient estimate is noisy (based on a single sample) but unbiased: E[−2u_ne[n]] = ∇J. Over many iterations, the noise averages out and the algorithm converges to the vicinity of w_opt.

Implementation

python
import numpy as np

def lms(u, d, M, mu):
    """LMS adaptive filter.
    u: input signal, d: desired signal
    M: filter length, mu: step size"""
    N = len(u)
    w = np.zeros(M)           # init weights to zero
    e = np.zeros(N)           # error signal
    y = np.zeros(N)           # filter output

    for n in range(M, N):
        u_n = u[n:n-M:-1]      # [u[n], u[n-1], ..., u[n-M+1]]
        y[n] = w @ u_n          # filter output
        e[n] = d[n] - y[n]     # error
        w = w + mu * e[n] * u_n # LMS update

    return y, e, w

Worked Example: LMS Step by Step

M = 2 taps, μ = 0.1, w[0] = [0, 0]. Input: u = [1, 0.5, −0.3, 0.8, ...]. Desired: d = [0.8, −0.1, 0.6, ...].

n = 0: u₀ = [1, 0], y[0] = [0,0]·[1,0] = 0, e[0] = 0.8 − 0 = 0.8, w[1] = [0,0] + 0.1·0.8·[1,0] = [0.08, 0].

n = 1: u₁ = [0.5, 1], y[1] = [0.08, 0]·[0.5, 1] = 0.04, e[1] = −0.1 − 0.04 = −0.14, w[2] = [0.08, 0] + 0.1·(−0.14)·[0.5, 1] = [0.073, −0.014].

Each step only uses the current input and error. After hundreds of steps, w converges near the Wiener solution — without ever computing R_u or its inverse.

Chapter 4: Convergence Analysis

When does LMS converge? And to what? Since the gradient is noisy, LMS doesn't converge to w_opt exactly — it wanders around it. The step size μ controls the tradeoff between convergence speed and steady-state noise.

Convergence in the Mean

Take expectations of the LMS update: E[w[n+1]] = E[w[n]] + μ E[u_ne[n]]. Under certain assumptions (independence of w[n] and u_n, which is approximate), this reduces to the same recursion as steepest descent. The convergence condition is the same:

Since we usually don't know λ_max, a practical bound uses the trace:

because λ_max ≤ tr(R_u) = ∑λ_k = M · σ_u² for white input with variance σ_u².

Excess MSE and Misadjustment

At steady state, the MSE is higher than J_min by an amount called the excess MSE:

The misadjustment M is the ratio of excess MSE to minimum MSE:

For 10% misadjustment with M = 10 taps and σ_u² = 1: μ < 0.02.

Worked Example: Choosing μ

Echo canceller with M = 64 taps, input is speech with σ_u² ≈ 0.01. The stability bound is μ < 2/(64 · 0.01) = 3.125. For 5% misadjustment: μ < 2 · 0.05 / (64 · 0.01) = 0.156. A typical choice would be μ = 0.05 — well within stability and giving about 1.6% misadjustment.

The convergence time constant is approximately τ ≈ 1/(2μλ_min). If the smallest eigenvalue of R_u is 0.001, then τ ≈ 1/(2 · 0.05 · 0.001) = 10,000 samples. At 8 kHz, that's 1.25 seconds to converge. Increasing μ speeds this up but increases steady-state noise.

Weight Error Vector Analysis

Define the weight error vector c[n] = w[n] − w_opt. The LMS update becomes:

where v[n] = d[n] − w_opt^Tu_n is the optimal error (noise floor). The first term drives c toward zero (convergence). The second term adds noise (the stochastic gradient is imperfect). At steady state, these two effects balance.

NLMS: Normalized LMS

A common improvement: normalize the step size by the input energy:

where δ is a small constant for numerical stability. NLMS removes the dependence on input power, making μ ∈ (0, 2) the universal stability range.

Chapter 5: Noise Cancellation

The classic application of adaptive filtering. You have two inputs:

• Primary: d[n] = s[n] + v[n] — signal s[n] corrupted by noise v[n]
• Reference: u[n] — correlated with v[n] but uncorrelated with s[n]

The adaptive filter takes u[n] as input and tries to make its output y[n] = w^Tu_n approximate v[n]. The error e[n] = d[n] − y[n] = s[n] + v[n] − y[n]. When w converges, y[n] ≈ v[n], so e[n] ≈ s[n]. The error IS the clean signal.

Why Does Minimizing MSE Cancel Noise?

The MSE is E[e²[n]] = E[(s[n] + v[n] − y[n])²]. Expand: E[s²] + E[(v − y)²] + 2E[s(v − y)]. Since s is uncorrelated with both v and u (and hence y), the cross term vanishes. So:

The first term is constant (signal power). Minimizing MSE = minimizing E[(v − y)²] = making y[n] approximate v[n]. When the filter converges, y[n] ≈ v[n], so e[n] = s[n] + v[n] − v[n] ≈ s[n]. The proof is elegant: you never told the filter about s[n], yet it recovers it by removing everything correlated with the reference.

Practical Requirements

For noise cancellation to work: (1) The reference u[n] must be correlated with the noise v[n] but uncorrelated with the signal s[n]. (2) The relationship between u[n] and v[n] must be approximately linear (for LMS to model it). (3) The filter length M must be long enough to capture the noise transfer path. If these are violated, the filter may distort the signal or fail to cancel the noise.

Chapter 6: Echo Cancellation

When you talk on a speakerphone, the far-end speaker's voice plays from your speaker, bounces around the room, and gets picked up by your microphone. The far-end listener hears their own voice delayed — an echo. This echo can be hundreds of milliseconds long, covering thousands of samples.

The Echo Path

The echo path from speaker to microphone is a linear filter (convolution with the room impulse response). Model it as an FIR filter with coefficients h = [h₀, h₁, ..., h_L−1]. The microphone signal is:

where u[n] is the far-end signal (known — we sent it to the speaker) and s[n] is the near-end talker (the voice we want to preserve).

An adaptive filter with input u[n] and desired output d[n] learns to approximate h. Its output y[n] ≈ ∑h_ku[n−k] is the estimated echo. Subtracting gives the echo-free signal: e[n] = d[n] − y[n] ≈ s[n].

Comparison of Algorithms

RLS (Recursive Least Squares) maintains a running estimate of R_u⁻¹ and updates it rank-1 at each step using the matrix inversion lemma (Woodbury identity):

where P[n] ≈ R_u⁻¹ and λ ∈ (0, 1] is a forgetting factor (typically 0.99). RLS converges in O(M) iterations regardless of eigenvalue spread, but costs O(M²) per sample. For long echo cancellers (M > 1000), the cost is prohibitive, so NLMS with subband decomposition is typical.

Practical Considerations

Real echo cancellers use a double-talk detector to freeze adaptation when both parties speak. The idea: if the error power suddenly increases (because near-end speech appeared), stop updating. Common detectors compare the ratio E[e²[n]]/E[d²[n]] to a threshold.

Subband adaptive filtering decomposes the signal into frequency bands, runs a short adaptive filter in each band (lower sampling rate = faster convergence), then reconstructs. This reduces the effective filter length and eigenvalue spread simultaneously.

Chapter 7: Mastery

Let's consolidate the journey from optimal filtering to online learning.

Connections

• Regression & AR Models — the batch/offline counterpart
• RKHS & Kernel Regression — kernel LMS extends adaptive filtering to nonlinear models
• Kalman filter — can be seen as an optimal adaptive filter for state-space models
• SGD in deep learning — same stochastic gradient idea, applied to nonlinear models with millions of parameters

The entire adaptive filtering framework — from Wiener to LMS to RLS — illustrates a recurring theme in engineering: replace exact computation with iterative approximation. The Wiener filter is beautiful but impractical. Steepest descent is practical but still batch. LMS drops everything except the current sample and somehow still works. This is the power of stochastic methods.

Beyond LMS

Modern adaptive filtering extends LMS in many directions:

• Frequency-domain LMS: Use FFT to compute the convolution, reducing per-sample cost to O(M log M / M) = O(log M) amortized
• Affine projection: Uses the last K input vectors (not just the current one) for a better gradient estimate. Convergence between LMS and RLS, cost O(KM)
• Kernel LMS: Replaces the linear filter with a kernel expansion, enabling nonlinear adaptive filtering (connects directly to RKHS)
• Sparse LMS: Adds an L1 penalty to promote sparse filter coefficients, useful when the true impulse response is sparse
• Variable step size: Adapts μ over time — large at start for fast convergence, small at steady state for low noise. GASS (gradient adaptive step size) and VSS-LMS automate this

In telecommunications, adaptive filters are ubiquitous. Every phone call uses echo cancellation. Every wireless receiver uses adaptive equalization to undo channel distortion. 5G MIMO systems use hundreds of adaptive filters running in parallel. The LMS algorithm, in some variant, is almost certainly running on the device you're reading this on right now.

"The LMS algorithm is perhaps the most widely used adaptive algorithm in practice. Its simplicity is its greatest strength." — Simon Haykin, Adaptive Filter Theory