Similarities between Wiener and LMS

The Least mean squares filter solution converges to the Wiener filter solution, assuming that the unknown system is LTI and the noise is stationary. Both filters can be used to identify the impulse response of an unknown system, knowing only the original input signal and the output of the unknown system. By relaxing the error criterion to reduce current sample error instead of minimizing the total error over all of n, the LMS algorithm can be derived from the Wiener filter.

Derivation of the Wiener filter for system identification

Given a known input signal $s\; [n]$, the output of an unknown LTI system $x\; [n]$ can be expressed as:

$x\; [n]\; =\; sum\_\{k=0\}^\{N-1\}\; h\_ks\; [n-k]\; +\; w\; [n]$

where $h\_k$ is an unknown filter tap coefficients and $w\; [n]$ is noise.

The model system $hat\{x\}\; [n]$, using a Wiener filter solution with an order N, can be expressed as:

$hat\{x\}\; [n]\; =\; sum\_\{k=0\}^\{N-1\}hat\{h\}\_ks\; [n-k]$

where $hat\{h\}\_k$ are the filter tap coefficients to be determined.

The error between the model and the unknown system can be expressed as:

$e\; [n]\; =\; x\; [n]\; -\; hat\{x\}\; [n]$

The total error $E$ can be expressed as:

$E\; =\; sum\_\{n=-infty\}^\{infty\}e\; [n]\; ^2$

$E\; =\; sum\_\{n=-infty\}^\{infty\}(x\; [n]\; -\; hat\{x\}\; [n]\; )^2$

$E\; =\; sum\_\{n=-infty\}^\{infty\}(x\; [n]\; ^2\; -\; 2x\; [n]\; hat\{x\}\; [n]\; +\; hat\{x\}\; [n]\; ^2)$

Use the MMSE criterion over all of $n$ by setting its gradient to zero:

$abla\; E\; =\; 0$which is$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; 0$ for all $i\; =\; 0,\; 1,\; 2,\; ...,\; N-1$

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; frac\{partial\}\{partial\; hat\{h\}\_i\}\; sum\_\{n=-infty\}^\{infty\}\; [x\; [n]\; ^2\; -\; 2x\; [n]\; hat\{x\}\; [n]\; +\; hat\{x\}\; [n]\; ^2\; ]$

Substitute the definition of $hat\{x\}\; [n]$:

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; frac\{partial\}\{partial\; hat\{h\}\_i\}\; sum\_\{n=-infty\}^\{infty\}\; [x\; [n]\; ^2\; -\; 2x\; [n]\; sum\_\{k=0\}^\{N-1\}hat\{h\}\_ks\; [n-k]\; +\; (sum\_\{k=0\}^\{N-1\}hat\{h\}\_ks\; [n-k]\; )^2\; ]$

Distribute the partial derivative:

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; sum\_\{n=-infty\}^\{infty\}\; [-2x\; [n]\; s\; [n-i]\; +\; 2(sum\_\{k=0\}^\{N-1\}hat\{h\}\_ks\; [n-k]\; )s\; [n-i]\; ]$

Using the definition of discrete cross-correlation:

$R\_\{xy\}(i)\; =\; sum\_\{n=-infty\}^\{infty\}\; x\; [n]\; y\; [n-i]$

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; -2R\_\{xs\}\; [i]\; +\; 2sum\_\{k=0\}^\{N-1\}hat\{h\}\_kR\_\{ss\}\; [i\; -\; k]\; =\; 0$

Rearrange the terms:

$R\_\{xs\}\; [i]\; =\; sum\_\{k=0\}^\{N-1\}hat\{h\}\_kR\_\{ss\}\; [i\; -\; k]$ for all $i\; =\; 0,\; 1,\; 2,\; ...,\; N-1$

This system of N equations with N unknowns can be determined.

Derivation of the LMS algorithm

By relaxing the infinite sum of the Wiener filter to just the error at time $n$, the LMS algorithm can be derived.

The squared error can be expressed as:

$E\; =\; (x\; [n]\; -\; hat\{x\}\; [n]\; )^2$

Using the Minimum_mean-square_error criterion, take the gradient:

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; frac\{partial\}\{partial\; hat\{h\}\_i\}(x\; [n]\; -\; hat\{x\}\; [n]\; )^2$

Apply chain rule and substitute definition of $hat\{x\}\; [n]$

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; 2(x\; [n]\; -\; hat\{x\}\; [n]\; )\; frac\{partial\}\{partial\; hat\{h\}\_i\}(x\; [n]\; -\; sum\_\{k=0\}^\{N-1\}hat\{h\}\_ks\; [n-k]\; )$

$frac\{partial\; E\}\{partial\; hat\{h\}\_i\}\; =\; -2(e\; [n]\; )(s\; [n-i]\; )$

From this equation, we can derive an update equation for each $h\_i$ at every new $n$ using gradient descent and a step size $mu$:

$hat\{h\}\_i^+\; =\; hat\{h\}\_i\; -\; mufrac\{partial\; E\}\{partial\; hat\{h\}\_i\}$

which becomes, for i = 0, 1, ..., N-1,

$hat\{h\}\_i^+\; =\; hat\{h\}\_i\; +\; 2mu(e\; [n]\; )(s\; [n-i]\; )$

This is the LMS update equation.

See also

* Wiener filter
* Least mean squares filter

References

* J.G. Proakis and D.G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, Prentice-Hall, 4th ed., 2007.