Least mean squares filter
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. Problem formulation. Relationship to the Wiener filter. The realization of the causal Wiener filter  looks a lot like the solution to the least squares estimate, except in the signal processing domain. The least squares solution, for input matrix formula_1 and output vector formula_2 is The 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 formula_4 is to be identified and the adaptive filter attempts to adapt the filter formula_5  to make it as close as possible to formula_4, while using only observable signals formula_7, formula_8 and formula_9; but formula_10, formula_11 and formula_12 are not directly observable. Its solution is closely related to the Wiener filter. Idea. The basic idea behind LMS filter is to approach the optimum filter weights formula_22, by updating the filter weights in a manner to converge to the optimum filter weight. This is based on the gradient descent algorithm. The algorithm starts by assuming small weights (zero in most cases) and, at each step, by finding the gradient of the mean square error, the weights  are updated. That is, if the MSE-gradient is positive, it implies the error would keep increasing positively if the same weight is used for further iterations, which means we need to reduce the weights. In the same way, if the gradient is negative, we need to increase the weights. The weight update equation is where formula_24 represents the mean-square error and formula_25 is a convergence coefficient. The negative sign shows that we go down the slope of the error, formula_24 to find the filter weights, formula_27, which minimize the error. The mean-square error as a function of  filter weights is a quadratic function which means it has only one extremum, that minimizes the mean-square error, which is the optimal weight. The LMS thus, approaches towards this optimal weights by ascending/descending down the mean-square-error vs filter weight curve. Derivation. The idea behind LMS filters is to use steepest descent to find filter weights formula_28 which minimize a cost function. We start by defining the cost function as and is independent of the input formula_7 and the real (unknown) impulse response formula_4. In the general case with interference (formula_33), the optimal learning rate is The  results above assume that the signals formula_11 and formula_7 are uncorrelated to each other, which is generally the case in practice. Proof. Let the filter misalignment be defined as formula_37, we can derive the expected misalignment for the next sample as: Let formula_40 and formula_41 Assuming independence, we have: The optimal learning rate is found at formula_46, which leads to: