Similarities between Wiener and LMS

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

${\displaystyle x[n]=\sum _{k=0}^{N-1}h_{k}s[n-k]+w[n]}$

where ${\displaystyle h_{k}}$ is an unknown filter tap coefficients and ${\displaystyle w[n]}$ is noise.

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

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

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

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

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

The total squared error ${\displaystyle E}$ can be expressed as:

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

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

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

Use the Minimum mean-square error criterion over all of ${\displaystyle n}$ by setting its gradient to zero:

${\displaystyle \nabla E=0}$ which is ${\displaystyle {\frac {\partial E}{\partial {\hat {h}}_{i}}}=0}$ for all ${\displaystyle i=0,1,2,...,N-1}$

${\displaystyle {\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 ${\displaystyle {\hat {x}}[n]}$:

${\displaystyle {\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}}_{k}s[n-k]+(\sum _{k=0}^{N-1}{\hat {h}}_{k}s[n-k])^{2}]}$

Distribute the partial derivative:

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

Using the definition of discrete cross-correlation:

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

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

Rearrange the terms:

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

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

The resulting coefficients of the Wiener filter can be determined by: ${\displaystyle W=R_{xx}^{-1}P_{xs}}$, where ${\displaystyle P_{xs}}$ is the cross-correlation vector between ${\displaystyle x}$ and ${\displaystyle s}$.

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

The squared error can be expressed as:

${\displaystyle E=(d[n]-y[n])^{2}}$

Using the Minimum mean-square error criterion, take the gradient:

${\displaystyle {\frac {\partial E}{\partial w}}={\frac {\partial }{\partial w}}(d[n]-y[n])^{2}}$

Apply chain rule and substitute definition of y[n]

${\displaystyle {\frac {\partial E}{\partial w}}=2(d[n]-y[n]){\frac {\partial }{\partial w}}(d[n]-\sum _{k=0}^{N-1}{\hat {w}}_{k}x[n-k])}$

${\displaystyle {\frac {\partial E}{\partial w_{i}}}=-2(e[n])(x[n-i])}$

Using gradient descent and a step size ${\displaystyle \mu }$:

${\displaystyle w[n+1]=w[n]-\mu {\frac {\partial E}{\partial w}}}$

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

${\displaystyle w_{i}[n+1]=w_{i}[n]+2\mu (e[n])(x[n-i])}$

This is the LMS update equation.

• Wiener filter
• Least mean squares filter

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