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}
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.
![{\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)