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 [ edit ] Given a known input signal
s
[
n
]
{\displaystyle s[n]}
x
[
n
]
{\displaystyle x[n]}
x
[
n
]
=
∑
k
=
0
N
−
1
h
k
s
[
n
−
k
]
+
w
[
n
]
{\displaystyle x[n]=\sum _{k=0}^{N-1}h_{k}s[n-k]+w[n]}
where
h
k
{\displaystyle h_{k}}
w
[
n
]
{\displaystyle w[n]}
The model system
x
^
[
n
]
{\displaystyle {\hat {x}}[n]}
x
^
[
n
]
=
∑
k
=
0
N
−
1
h
^
k
s
[
n
−
k
]
{\displaystyle {\hat {x}}[n]=\sum _{k=0}^{N-1}{\hat {h}}_{k}s[n-k]}
where
h
^
k
{\displaystyle {\hat {h}}_{k}}
The error between the model and the unknown system can be expressed as:
e
[
n
]
=
x
[
n
]
−
x
^
[
n
]
{\displaystyle e[n]=x[n]-{\hat {x}}[n]}
The total squared error
E
{\displaystyle E}
E
=
∑
n
=
−
∞
∞
e
[
n
]
2
{\displaystyle E=\sum _{n=-\infty }^{\infty }e[n]^{2}}
E
=
∑
n
=
−
∞
∞
(
x
[
n
]
−
x
^
[
n
]
)
2
{\displaystyle E=\sum _{n=-\infty }^{\infty }(x[n]-{\hat {x}}[n])^{2}}
E
=
∑
n
=
−
∞
∞
(
x
[
n
]
2
−
2
x
[
n
]
x
^
[
n
]
+
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
n
{\displaystyle n}
gradient to zero:
∇
E
=
0
{\displaystyle \nabla E=0}
∂
E
∂
h
^
i
=
0
{\displaystyle {\frac {\partial E}{\partial {\hat {h}}_{i}}}=0}
i
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\displaystyle i=0,1,2,...,N-1}
∂
E
∂
h
^
i
=
∂
∂
h
^
i
∑
n
=
−
∞
∞
[
x
[
n
]
2
−
2
x
[
n
]
x
^
[
n
]
+
x
^
[
n
]
2
]
{\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
x
^
[
n
]
{\displaystyle {\hat {x}}[n]}
∂
E
∂
h
^
i
=
∂
∂
h
^
i
∑
n
=
−
∞
∞
[
x
[
n
]
2
−
2
x
[
n
]
∑
k
=
0
N
−
1
h
^
k
s
[
n
−
k
]
+
(
∑
k
=
0
N
−
1
h
^
k
s
[
n
−
k
]
)
2
]
{\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:
∂
E
∂
h
^
i
=
∑
n
=
−
∞
∞
[
−
2
x
[
n
]
s
[
n
−
i
]
+
2
(
∑
k
=
0
N
−
1
h
^
k
s
[
n
−
k
]
)
s
[
n
−
i
]
]
{\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 :
R
x
y
(
i
)
=
∑
n
=
−
∞
∞
x
[
n
]
y
[
n
−
i
]
{\displaystyle R_{xy}(i)=\sum _{n=-\infty }^{\infty }x[n]y[n-i]}
∂
E
∂
h
^
i
=
−
2
R
x
s
[
i
]
+
2
∑
k
=
0
N
−
1
h
^
k
R
s
s
[
i
−
k
]
=
0
{\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:
R
x
s
[
i
]
=
∑
k
=
0
N
−
1
h
^
k
R
s
s
[
i
−
k
]
{\displaystyle R_{xs}[i]=\sum _{k=0}^{N-1}{\hat {h}}_{k}R_{ss}[i-k]}
i
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\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:
W
=
R
x
x
−
1
P
x
s
{\displaystyle W=R_{xx}^{-1}P_{xs}}
P
x
s
{\displaystyle P_{xs}}
x
{\displaystyle x}
s
{\displaystyle s}
Derivation of the LMS algorithm [ edit ] By relaxing the infinite sum of the Wiener filter to just the error at time
n
{\displaystyle n}
The squared error can be expressed as:
E
=
(
d
[
n
]
−
y
[
n
]
)
2
{\displaystyle E=(d[n]-y[n])^{2}}
Using the Minimum mean-square error criterion, take the gradient:
∂
E
∂
w
=
∂
∂
w
(
d
[
n
]
−
y
[
n
]
)
2
{\displaystyle {\frac {\partial E}{\partial w}}={\frac {\partial }{\partial w}}(d[n]-y[n])^{2}}
Apply chain rule and substitute definition of y[n]
∂
E
∂
w
=
2
(
d
[
n
]
−
y
[
n
]
)
∂
∂
w
(
d
[
n
]
−
∑
k
=
0
N
−
1
w
^
k
x
[
n
−
k
]
)
{\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])}
∂
E
∂
w
i
=
−
2
(
e
[
n
]
)
(
x
[
n
−
i
]
)
{\displaystyle {\frac {\partial E}{\partial w_{i}}}=-2(e[n])(x[n-i])}
Using gradient descent and a step size
μ
{\displaystyle \mu }
w
[
n
+
1
]
=
w
[
n
]
−
μ
∂
E
∂
w
{\displaystyle w[n+1]=w[n]-\mu {\frac {\partial E}{\partial w}}}
which becomes, for i = 0, 1, ..., N-1,
w
i
[
n
+
1
]
=
w
i
[
n
]
+
2
μ
(
e
[
n
]
)
(
x
[
n
−
i
]
)
{\displaystyle w_{i}[n+1]=w_{i}[n]+2\mu (e[n])(x[n-i])}
This is the LMS update equation.
J.G. Proakis and D.G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, Prentice-Hall, 4th ed., 2007. 
![{\displaystyle s[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffe878c033cc70d1aa3ffbd156394791aa8dffde)
![{\displaystyle x[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864cbbefbdcb55af4d9390911de1bf70167c4a3d)
![{\displaystyle x[n]=\sum _{k=0}^{N-1}h_{k}s[n-k]+w[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29d41ffb9167c860cce2987a1c1d7cff8030c784)
![{\displaystyle w[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a4e3e5afc2a8c6da9020b8c6b21450959101a18)
![{\displaystyle {\hat {x}}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fee9146195da61b726bebb68b2d9999c22b32375)
![{\displaystyle {\hat {x}}[n]=\sum _{k=0}^{N-1}{\hat {h}}_{k}s[n-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e99c12580f9be872405e0fe1e438d2ea3bd4a49)
![{\displaystyle e[n]=x[n]-{\hat {x}}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce6a7691f1713e4f03cf5267dc298e154f673615)
![{\displaystyle E=\sum _{n=-\infty }^{\infty }e[n]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74020f9287004f13d8a581ff697af14465459553)
![{\displaystyle E=\sum _{n=-\infty }^{\infty }(x[n]-{\hat {x}}[n])^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30a2b943f4c0ef0ed1d6a62e443c1a4e0aeedf34)
![{\displaystyle E=\sum _{n=-\infty }^{\infty }(x[n]^{2}-2x[n]{\hat {x}}[n]+{\hat {x}}[n]^{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f04965570d5a3527c08f828e41ae89e62ff1e5f)
![{\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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f74b4f305ccf81c69472c6baed33d36eff495f57)
![{\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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/494c25e285acf543f55c3378d49e7c6ae51b50b4)
![{\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]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23993057b95398bea838c81467dca8ac5f7ea806)
![{\displaystyle R_{xy}(i)=\sum _{n=-\infty }^{\infty }x[n]y[n-i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6dd0be6cdff7c6826db2c50ef465cc70c6a6c560)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3725ae5e10c4be1368fc3815e6e8c110ba0cce4)
![{\displaystyle R_{xs}[i]=\sum _{k=0}^{N-1}{\hat {h}}_{k}R_{ss}[i-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6322bb6368aff651f5397cafde1e2472c4559fa3)
![{\displaystyle E=(d[n]-y[n])^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/992c761863a1024e1abe940e681b112c2f19f420)
![{\displaystyle {\frac {\partial E}{\partial w}}={\frac {\partial }{\partial w}}(d[n]-y[n])^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e782154b068787c1b580dae3f0890d434e65024)
![{\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])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19888f66d939baf75866c50d012a65a7f826e176)
![{\displaystyle {\frac {\partial E}{\partial w_{i}}}=-2(e[n])(x[n-i])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d03c1011cfacbdd64160c7e09337bdeb1fe7599)
![{\displaystyle w[n+1]=w[n]-\mu {\frac {\partial E}{\partial w}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f68ce4b36bdb6c59f24ea7dd309ff9fa00dc0fba)
![{\displaystyle w_{i}[n+1]=w_{i}[n]+2\mu (e[n])(x[n-i])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12a8a0b31c71c2f62a444aba32ac66e4efd2cd6d)