Skip to content
Digital Signal Processing

Adaptive filters: Wiener, LMS and noise and echo cancellation

Normal equations and the orthogonality principle proved, the LMS algorithm as gradient descent, the convergence condition proved, normalised LMS, noise and echo cancellation, equalisation.

5 min read 0 comments

The filters seen so far have fixed coefficients, computed once from the specifications. But often the signal and the disturbance change over time, or are not known in advance: the echo of a phone call depends on the room, a modem’s channel changes with the line, the noise of an engine with its speed. An adaptive filter updates its own coefficients at every sample to minimise an error. In this lesson we derive the Wiener filter with the orthogonality principle, the LMS algorithm as gradient descent with the proof of the convergence condition, the normalised version and the applications.

The problem

An FIR filter with coefficients w = (w_0, \dots, w_{N-1})^T receives the vector of the last N input samples x[n] = (x[n], \dots, x[n-N+1])^T and produces y[n] = w^Tx[n]. There is a desired signal d[n], and the error is e[n] = d[n] - y[n]. We look for the coefficients that minimise the mean squared error J(w) = E[e^2[n]].

The Wiener filter

Expanding the square, with the input autocorrelation matrix R = E[x\,x^T] and the cross-correlation vector p = E[d\,x]:

    \[ J(w) = E[d^2] - 2p^Tw + w^TRw \]

It is a quadratic function of the coefficients, a “bowl” with a single minimum.

Theorem. The optimal coefficients satisfy the normal equations R\,w_o = p, and at the optimum the error is uncorrelated with every input sample: E[e\,x] = 0.

Proof. The gradient of J with respect to w is \nabla J = -2p + 2Rw. The minimum of a convex quadratic function (R is positive semidefinite) is where the gradient vanishes, Rw_o = p. Moreover E[e\,x] = E[(d - x^Tw)x] = p - Rw, which is zero at w_o. ∎

The second result is the orthogonality principle: the optimal error no longer contains anything that can be predicted from the input. The Wiener filter, however, requires knowing R and p and solving a linear system, and if the statistics change one has to start again.

The LMS algorithm

The idea of Widrow and Hoff (1960) is to go down the gradient one step at a time, using instead of the true gradient, which would require statistical averages, its instantaneous estimate. Replacing R and p with x\,x^T and d\,x, the estimated gradient is -2(d - x^Tw)x = -2e\,x, and the descent step becomes

    \[ w[n+1] = w[n] + \mu\,e[n]\,x[n] \]

with the step size \mu (the factor 2 is absorbed into \mu). Each coefficient is corrected in proportion to the error and to the input sample it multiplies. The cost is about 2N multiplications per sample: the same order as the filter.

Convergence

Theorem. With stationary inputs, independent from one step to the next, the LMS coefficients converge in the mean to the Wiener solution if and only if

    \[ 0 \lt \mu \lt \frac{2}{\lambda_{max}} \]

where \lambda_{max} is the largest eigenvalue of R.

Proof. Let v[n] = w[n] - w_o be the deviation from the optimum. Taking the mean of the update, with the independence assumption E[x\,x^Tw] = R\,E[w], gives E[w[n+1]] = E[w[n]] + \mu(p - R\,E[w[n]]), i.e., using p = Rw_o,

    \[ E[v[n+1]] = (I - \mu R)\,E[v[n]] \]

R is symmetric, R = Q\Lambda Q^T with Q orthogonal; in the coordinates Q^Tv the components evolve separately as (1 - \mu\lambda_i)^n. They tend to zero if and only if |1 - \mu\lambda_i| \lt 1 for every i, i.e. 0 \lt \mu \lt 2/\lambda_i; the most restrictive condition is that of the largest eigenvalue. ∎

In practice the estimate \lambda_{max} \le \mathrm{tr}\,R = N\sigma_x^2, easy to measure, is used: \mu \lt 2/(N\sigma_x^2). The convergence speed, instead, is set by the smallest eigenvalue: if the eigenvalues are very different (a very coloured input), LMS converges slowly along some directions. A large \mu converges quickly but leaves the coefficients “jittering” around the optimum (the misadjustment, an excess error); a small \mu is accurate but slow to track changes.

Normalised LMS

If the input power varies, a fixed \mu becomes too large or too small. NLMS divides the step by the current energy of the samples:

    \[ w[n+1] = w[n] + \frac{\tilde\mu}{\varepsilon + \|x[n]\|^2}\,e[n]\,x[n],\qquad 0 \lt \tilde\mu \lt 2 \]

with a small \varepsilon to avoid division by zero. It is the version used almost always, for instance in echo cancellers. More expensive algorithms such as RLS (recursive least squares) converge much faster at the price of N^2 operations per sample, and the Kalman filter is their generalisation to systems described in state space.

Applications

Adaptive noise canceller with the LMS algorithm
The desired signal d contains the useful signal s plus a noise v. A second sensor measures a reference x correlated with the noise but not with the signal. The adaptive filter w estimates the noise from the reference and subtracts it; the error e, which is the cleaned signal, drives the coefficient update.
  • Noise cancellation. One microphone picks up voice plus noise, a second one picks up only the noise (the reference). The filter learns the transformation between the two noises and subtracts it: by the orthogonality principle the minimum error is exactly the voice, which is uncorrelated with the reference. Active noise-cancelling headphones use a variant of this.
  • Echo cancellation. In speakerphones and video calls the loudspeaker leaks back into the microphone. The filter, with the far-end voice as reference, estimates the echo path in the room (hundreds of milliseconds, thousands of coefficients) and removes it.
  • Equalisation. In a modem or a radio receiver, the filter compensates the channel distortion by learning from a known sequence, then keeps tracking using the receiver’s decisions.
  • Identification. Placed in parallel with an unknown system, with the same input, the filter converges to its impulse response: it is used to measure acoustics, channels and processes.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x