Adaptive filters: LMS

Here a filter with two taps learns to copy an unknown system, nudging its taps after every sample. Each pair of taps is a point on a map of the error, and the lowest error is at the cross. Watch the solid path wobble down towards it.

A filter that learns

The Wiener filter (26.2) found the best FIR filter from correlations. It needed the input’s autocorrelation matrix $\mathbf{R}$ and the cross-correlation vector $\mathbf{r}$, known in advance. Often nobody knows them. A phone does not know the echo path of the room it is in, and that path changes when someone moves.

So let the filter learn them. It starts with some taps, watches its own error, and nudges the taps after every sample so that the error shrinks. A filter that does this is adaptive. This page builds the simplest and most widely used one, the LMS algorithm.

I assume that the input is stationary while the filter learns, as in “Stationary, and ergodic” of Random processes (24.2). If the statistics drift slowly, the filter keeps learning and follows them.

An unknown system to copy

Here is the task for the first half of the page. An unknown FIR system with two taps, $\mathbf{h}_\text{true}=(0.8,-0.4)$, is driven by an input $x[n]$. I can measure its output, with noise $v[n]$ of standard deviation 0.1 added. Finding the system from its input and output is called system identification.

The noisy output is what my filter tries to match, so it plays the part of 26.2’s desired signal:

My filter has two taps too, $\mathbf{h}=(h_0,h_1)$. At sample $n$ it sees the two latest inputs, stacked as a column, newest first:

This $\mathbf{x}_n$ is the tap-input vector. The snapshot of 25.4 ran forward in time; this one runs backward. The output is $y[n]=\mathbf{h}^\top\mathbf{x}_n=h_0x[n]+h_1{x[n-1]}$, and the error is $e[n]=d_\text{des}[n]-y[n]$, as in 26.2.

The input is coloured noise, the AR(1) process of “White noise forgets, coloured noise remembers” in 24.2. Each sample is $0.6\,{x[n-1]}$ plus white noise of variance 0.64. Its power is then $0.64/(1-0.6^2)=1$, and $R_x[\ell]=0.6^{\lvert\ell\rvert}$. With two taps, the matrix $\mathbf{R}$ of 26.2 has entries 1 and 0.6:

The error is a bowl

How good is a choice of taps? In 26.2 the measure was the mean-square error $J=\mathbb{E}\{e^2[n]\}$. Square $e[n]=d_\text{des}[n]-\mathbf{h}^\top\mathbf{x}_n$ and average:

Here $\sigma_\text{des}^2$ is the power of $d_\text{des}[n]$, and $\mathbf{r}$ has the entries $\mathbb{E}\{d_\text{des}[n]\,x[n-k]\}$.

The best taps solve 26.2’s Wiener–Hopf equations, $\mathbf{R}\mathbf{h}_\text{opt}=\mathbf{r}$, and leave the least error $J_\text{min}=\sigma_\text{des}^2-\mathbf{r}^\top\mathbf{h}_\text{opt}$. Put $\mathbf{r}=\mathbf{R}\mathbf{h}_\text{opt}$ into $J$ and collect the terms:

The last term is the mean square of $(\mathbf{h}-\mathbf{h}_\text{opt})^\top\mathbf{x}_n$, so it is never negative. Over the two taps, $J$ is a bowl with its bottom at $\mathbf{h}_\text{opt}$, at height $J_\text{min}$. This bowl is the error surface.

For our task the bottom is where you would hope. The noise is uncorrelated with the input, so $\mathbf{r}=\mathbf{R}\mathbf{h}_\text{true}$ and $\mathbf{h}_\text{opt}=\mathbf{h}_\text{true}$. What is left at the bottom is the noise: $J_\text{min}=0.1^2=0.01$. At $\mathbf{h}=(0,0)$ the filter outputs nothing, and $J$ is the whole power of $d_\text{des}[n]$, 0.426.

The shape of the bowl

Cut the bowl at a fixed height and the edge is an ellipse. Its axes are the eigenvectors of $\mathbf{R}$, from “Directions that are only stretched” in High-resolution frequency estimation (25.4). Here you can check them by hand: $\mathbf{R}$ sends $(1,1)$ to $(1.6,1.6)$ and $(1,-1)$ to $(0.4,-0.4)$. So the eigenvalues are $\lambda_\text{max}=1.6$ and $\lambda_\text{min}=0.4$.

Step a distance $s$ from the bottom along a unit eigenvector, and $J$ rises by $\lambda s^2$. So the bowl is steep along $(1,1)$ and shallow along $(1,-1)$. The ellipse’s long axis runs along $(1,-1)$, the direction of the smaller eigenvalue.

At $J=0.17$, for example, the ellipse reaches 0.632 from the bottom along $(1,-1)$ and 0.316 along $(1,1)$. The ratio of the eigenvalues, 4 here, is the eigenvalue spread: the longer the ellipse, the larger it is.

Walking downhill

If you know the bowl, you can walk down it. The slope of $J$ along each tap is its derivative with respect to that tap. Together the two derivatives form the gradient, which points uphill:

Steepest descent takes a small step against the gradient, again and again, each new value from the last as in Difference equations (6.1). I fold the 2 into the step:

Here $\mathbf{h}_n$ is the taps at step $n$, and $\mu$ is the step size, a small positive number. On this page and in 26.4, a bare $\mu$ is a step size, not the fractional position of Resampling by any factor (22.3).

There is a catch. Steepest descent needs $\mathbf{R}$ and $\mathbf{h}_\text{opt}$, and if I knew those I would not need to walk.

LMS: the slope from one sample

Look again at the step. Since $\mathbf{R}\mathbf{h}_\text{opt}=\mathbf{r}$, it is $\mathbf{r}-\mathbf{R}\mathbf{h}_n$, the average of $\mathbf{x}_n\big(d_\text{des}[n]-\mathbf{x}_n^\top\mathbf{h}_n\big)$. That is the average of $e[n]\,\mathbf{x}_n$.

The LMS algorithm, for “least mean squares”, drops the average. It uses the error and the inputs of the current sample only:

Each tap costs about two multiplications per sample, one for the output and one for its update. No correlations are estimated at all. B. Widrow and M. E. Hoff published it in 1960.

Each step points downhill only on average. Think of walking downhill in fog: you judge the slope from the patch of ground under your feet. Each step is a little off, but on average you go down.

Downhill, one noisy step at a time

The picture at the top of the page runs LMS and steepest descent side by side on this bowl, for 300 steps each, with μ = 0.05. LMS starts at (0, 0), high on the bowl, at $J$ = 0.426. After 30 steps it has come down to $J$ = 0.077, wobbling about the smooth steepest-descent path. After 300 it is near the bottom, $J$ = 0.012 against the least possible 0.010, and keeps wandering a little around it. When the clip ends, try the three step sizes.

Notice where the two paths end. After 300 steps at μ = 0.05, LMS is at (0.812, −0.369) and steepest descent at (0.799, −0.399). The smooth path has nearly reached the bottom; the noisy one is close and still moving.

Fast and slow directions

Why does the walk curve? Write the distance from the bottom as $\mathbf{h}_n-\mathbf{h}_\text{opt}$. Steepest descent multiplies it by $\mathbf{I}-\mu\mathbf{R}$ at each step. Along an eigenvector, that is a plain number, $1-\mu\lambda$.

So the distance along each eigenvector shrinks by its own factor at every step. After $1/(\mu\lambda)$ steps it has fallen to about 0.37 of its start, and that count is the time constant of the direction. At μ = 0.05 the steep direction has the time constant $1/(0.05\cdot1.6)=12.5$ steps and the shallow one 50.0 steps.

That is the curve you saw. The path first drops quickly across the narrow width of the ellipse, then crawls along its long axis. A larger eigenvalue spread makes the crawl longer compared with the drop.

Speed against wander

Near the bottom the two walks behave differently. Steepest descent settles. LMS keeps taking noisy steps, so its taps keep wandering around the bottom.

A larger step arrives sooner and wanders more. On this record, the first step within 0.05 of the bottom is step 663 for μ = 0.01, 116 for μ = 0.05 and 45 for μ = 0.12. Over samples 1000 to 2000, the taps stray from $\mathbf{h}_\text{true}$ by RMS 0.013, 0.026 and 0.040.

The wander costs error. The bowl’s height at the wandering taps, averaged over samples 1000 to 2000, is 0.0101, 0.0106 and 0.0115 against $J_\text{min}=0.0100$. The extra error as a fraction of $J_\text{min}$ is the misadjustment: 1.2 %, 5.5 % and 14.8 % here.

For small steps the misadjustment is about $\mu N_hR_x[0]/2$, with $N_h$ taps of input power $R_x[0]$. That gives 1 %, 5 % and 12 %, close for the two smaller steps. So choosing μ is a trade: halve it, and you halve the extra error but wait twice as long.

Too big a step

Steepest descent converges when every factor $1-\mu\lambda$ lies between −1 and 1. That needs

which is 1.25 here. LMS needs a margin below that, because single noisy steps can overshoot. On this record, μ = 0.3 is about a quarter of that limit, yet at one point LMS throws the taps about 96 away from the bottom.

There is a second trap. The limit depends on the input’s level. Turn this record’s input up three times, and every entry of $\mathbf{R}$ grows nine times: $\lambda_\text{max}=14.4$, and the limit falls to 0.139. On that louder record, LMS with μ = 0.05 blows up, its taps reaching about 3500.

NLMS, normalised LMS, removes that dependence. It divides the step by the energy of the current inputs, $\lVert\mathbf{x}_n\rVert^2=x[n]^2+{x[n-1]}^2$:

Make the input three times louder and $e[n]\,\mathbf{x}_n$ grows nine times, but so does $\lVert\mathbf{x}_n\rVert^2$: the steps do not change. NLMS is stable for μ between 0 and 2. In practice a small constant is added to $\lVert\mathbf{x}_n\rVert^2$, so that a nearly silent moment does not make the step huge.

The hum fades as the weights settle

Now the second use, noise cancelling. A voice is recorded with 50 Hz mains hum on top, $0.8\sin(2\pi\,50t+0.6)$. That recording is the primary input, and it plays the part of $d_\text{des}[n]$. The hum comes from the power line, so I can take a clean copy of it there: a 50 Hz sine and its cosine, the reference input.

The filter’s two weights rebuild the hum from the reference. Here $\mathbf{x}_n$ is not a row of past samples: its two entries are the sine and the cosine at sample $n$. At a sample rate of 1 kHz, 50 Hz is $\Omega=2\pi\cdot50/1000=0.1\pi$, so

The filter’s output $y[n]$ is the rebuilt hum. The error $e[n]$, primary minus rebuild, is the cleaned voice. LMS runs as before, with μ = 0.01.

Which weights rebuild the hum exactly? Expand the sine of a sum:

So the target weights are $0.8\cos0.6=0.660$ and $0.8\sin0.6=0.452$. The voice is unrelated to the reference, so on average it does not pull the weights anywhere.

The reference’s $\mathbf{R}$ has $\tfrac12$ on the diagonal, because a sine squared averages to $\tfrac12$. Its off-diagonal entries are 0, because a sine times its cosine averages to 0. Both eigenvalues are 0.5, so both weights learn at one rate. Its time constant is $1/(0.01\cdot0.5)=200$ samples, 0.20 s.

The voice here is a stand-in: seeded noise through a resonance at 200 Hz, scaled to an RMS of 0.3. There is no recording and no sound.

The hum’s RMS is $0.8/\sqrt2=0.566$. The next instrument measures the “hum left”: the RMS of the hum still in the output, over the last 0.1 s.

Watch the solid output lose its hum as the two weights climb to their dotted targets. Half a second in, the hum left is 0.069; after two seconds it is 0.011, −34.1 dB relative to the start.

Notice the weights at the end: 0.665 and 0.435, close to the hum’s sine and cosine parts, 0.660 and 0.452. The output has become the voice.

They never sit still, though. The voice is in $e[n]$ too, and every sample of it nudges the weights a little, as the noise did in the bowl. Over the last second the hum left moves between 0.005 and 0.017; at 1 s it read 0.005, lower than at the end. That is misadjustment again.

A notch that follows the hum

Once the weights have settled, the canceller is a fixed filter from the primary input to the output. Its transfer function, worked out by Glover in 1977, is a notch at $\theta=0.1\pi$:

Compare it with “Poles behind the zeros narrow the notch” in Resonators, notches and combs (17.4). The zeros sit on the unit circle at $\pm\theta$. The poles sit just inside, at radius $\sqrt{1-\mu}=0.995$ and almost the same angle.

17.4’s rule, a width of $2(1-r)$ rad/sample, gives 1.60 Hz at 1 kHz. The measured −3 dB width is 1.58 Hz. Since $r$ is close to $1-\mu/2$, the width is about $\mu$ rad/sample: a larger μ learns faster and cuts a wider notch.

17.4’s fixed notch for an ECG, with $r=0.95$, was 8.1 Hz wide. That width leaves room for the mains frequency to drift. The adaptive notch can be much narrower, because it sits wherever the reference is: if the mains drifts, the notch drifts with it.

Worked example

1. Two LMS steps by hand. Start from $\mathbf{h}_0=(0,0)$ with μ = 0.5. Feed one input sample of 1, so $\mathbf{x}_0=(1,0)$ and $\mathbf{x}_1=(0,1)$. The unknown system answers $d_\text{des}[0]=0.8$ and $d_\text{des}[1]=-0.4$, without noise.

Step 0: $e[0]=0.8-0=0.8$, and $\mathbf{h}_1=(0,0)+0.5\cdot0.8\cdot(1,0)=(0.4,0)$. Step 1: $e[1]=-0.4-(0.4\cdot0+0\cdot1)=-0.4$, and $\mathbf{h}_2=(0.4,0)+0.5\cdot(-0.4)\cdot(0,1)=(0.4,-0.2)$.

Each tap went half-way to $(0.8,-0.4)$. Here $\mu\lVert\mathbf{x}_n\rVert^2=0.5$, so each step removes half of the error in the direction of $\mathbf{x}_n$.

2. Time constants. For the bowl, μ = 0.05 and the eigenvalues 1.6 and 0.4 give $1/(0.05\cdot1.6)=12.5$ and $1/(0.05\cdot0.4)=50.0$ samples. The step limit is $2/1.6=1.25$.

3. The canceller’s targets. The hum $0.8\sin(0.1\pi n+0.6)$ splits into $0.660\sin(0.1\pi n)+0.452\cos(0.1\pi n)$. The reference’s eigenvalues are both 0.5, so at μ = 0.01 the time constant is 200 samples, 0.20 s. After 0.5 s the weights are 0.593 and 0.409, and after 2 s 0.665 and 0.435.

Where you’ll meet this

Echo cancellers are system identification. In a phone call or a video conference, the far-end voice comes out of your loudspeaker, travels round the room and enters your microphone. An adaptive filter fed with the far-end voice learns that echo path and subtracts its copy of the echo, often with NLMS. Network echo cancellers for telephone lines do the same, and ITU-T Recommendation G.168 sets what they must achieve.

Noise-cancelling headphones hear the noise with an outside microphone and play its opposite, using a variant of LMS. The 1975 paper by Widrow and his colleagues, “Adaptive noise cancelling: principles and applications”, used the canceller of this page on mains hum in an ECG. It also took the mother’s heartbeat out of a fetal ECG, with chest leads as the reference.

Receivers use adaptive filters as channel equalisers, which learn to undo the blur of a channel: Channels and equalisation (33.2). When LMS learns too slowly, for instance with a large eigenvalue spread, RLS and the Kalman filter (26.4) learns faster at a higher cost.

For more, see B. Widrow and S. D. Stearns, Adaptive Signal Processing (1985), and S. Haykin, Adaptive Filter Theory (5th ed., 2014), ch. 4 to 6.

Reference card