Least mean squares (LMS) algorithms are a class of adaptive filter used to mimic a desired filter by finding the filter coefficients that relate to producing the least mean square of the error signal (difference between the desired and the actual signal). It is a stochastic gradient descent method in that the filter is only adapted based on the error at the current time. It was invented in 1960 by Stanford University professor Bernard Widrow and his first Ph.D. student, Ted Hoff, based on their research into single-layer neural networks. Specifically, they used gradient descent to train an ADALINE to recognize patterns, and called the algorithm "delta rule". They applied the rule to filters, resulting in the LMS algorithm.
Problem formulation The picture shows the various parts of the filter. x {\displaystyle x} is the input signal, which is then transformed by an unknown filter h {\displaystyle h} that we wish to match using h ^ {\displaystyle {\hat {h}}} . The output from the unknown filter is y {\displaystyle y} , which is then interfered with a noise signal ν {\displaystyle \nu } , producing d = y + ν {\displaystyle d=y+\nu } . Then the error signal e = d − y ^ = y + ν − y ^ {\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}} is computed, and it is fed back to the adaptive filter, to adjust its parameters in order to minimize the mean squared error, ∑ e 2 / n {\displaystyle \sum e^{2}/n} .
Relationship to the Wiener filter The realization of the causal Wiener filter resembles the solution to the least squares estimate, except in the signal processing domain. The least squares solution for input matrix X {\displaystyle \mathbf {X} } and output vector y {\displaystyle {\boldsymbol {y}}}
is
β ^ = ( X T X ) − 1 X T y . {\displaystyle {\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.}
The finite impulse response (FIR) least mean squares filter is related to the Wiener filter, but minimizing the error criterion of the former does not rely on cross-correlations or auto-correlations. Its solution converges to the Wiener filter solution. Most linear adaptive filtering problems can be formulated using the block diagram above. That is, an unknown system h ( n ) {\displaystyle \mathbf {h} (n)} is to be identified and the adaptive filter attempts to adapt the filter h ^ ( n ) {\displaystyle {\hat {\mathbf {h} }}(n)} to make it as close as possible to h ( n ) {\displaystyle \mathbf {h} (n)} , while using only observable signals x ( n ) {\displaystyle x(n)} , d ( n ) {\displaystyle d(n)} and e ( n ) {\displaystyle e(n)} ; but y ( n ) {\displaystyle y(n)} , v ( n ) {\displaystyle v(n)} and h ( n ) {\displaystyle h(n)} are not directly observable. Its solution is closely related to the Wiener filter.
Definition of symbols
n {\displaystyle n} is the number of the current input sample
p {\displaystyle p} is the number of filter taps
{ ⋅ } H {\displaystyle \{\cdot \}^{H}} (Hermitian transpose or conjugate transpose)
x ( n ) = [ x ( n ) , x ( n − 1 ) , … , x ( n − p + 1 ) ] T {\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}
… excerpt ends here. Continue reading the full article.
