LMS Algorithm

The Least Mean Squares (LMS) algorithm is the most widely used adaptive filtering algorithm in digital signal processing. It adjusts filter coefficients iteratively to minimize the mean squared error between the filter output and a desired signal. Its popularity comes from computational simplicity combined with reliable convergence under stationary conditions, making it essential for GATE preparation and real-world DSP applications.

Core Concept of LMS

An adaptive filter modifies its own coefficients based on incoming data. The LMS algorithm accomplishes this using the method of steepest descent applied to the mean squared error (MSE) cost function. The key insight is that computing the true gradient of MSE requires statistical expectations, which are not available in real time. The LMS algorithm replaces the true gradient with an instantaneous estimate, making it computationally feasible.

At each time step n, the filter computes an output y(n) by convolving the input vector x(n) with the current weight vector w(n). The error signal e(n) is computed as the difference between a desired reference signal d(n) and the filter output y(n). This error signal is then used to nudge the weight vector in the direction that reduces future error.

The physical meaning is straightforward. If the filter output is too large compared to the desired signal, the error is negative, and the weights are pulled down. If the output is too small, the error is positive, and the weights are pushed up. Over many iterations, the weights converge to values that minimize the average squared error.

Mathematical Expression

The LMS weight update equation is the heart of the algorithm. Given a filter of order M, the weight vector at time n+1 is updated as follows. The term step size mu (written as the Greek letter mu) controls how aggressively the weights change per iteration.

The filter output is computed as y(n) = w^T(n) x(n), where w(n) is the M-dimensional weight vector and x(n) is the input vector containing the M most recent samples. The error is e(n) = d(n) - y(n). The weight update rule is w(n+1) = w(n) + 2*mu*e(n)*x(n).

For convergence, the step size mu must satisfy 0 < mu < 1/(M * P_x), where P_x is the input signal power and M is the filter order. If mu is too large, the algorithm diverges. If mu is too small, convergence is very slow. Choosing the right mu is a critical design decision and a common GATE examination topic.

Practical Understanding

The LMS algorithm is favored in practice because it requires only 2M+1 multiplications and additions per iteration, making it one of the most computationally efficient adaptive algorithms. This simplicity comes at a cost: in non-stationary environments where signal statistics change over time, LMS can track slowly because the step size trades off convergence speed and steady-state error.

The misadjustment parameter M_adj quantifies the excess MSE compared to the Wiener filter optimal solution. It is approximately equal to mu * M * P_x. This means a larger step size or higher filter order increases steady-state error. Engineers balance these trade-offs depending on application requirements.

Given:
Filter order M = 4, Input power P_x = 0.5 W, Step size mu = 0.08

Why this formula applies:
Convergence requires 0 < mu < 1/(M * P_x)

Formula:
mu_max = 1 / (M * P_x)

Substitution:
mu_max = 1 / (4 * 0.5) = 1 / 2

Calculation:
mu_max = 0.5
Chosen mu = 0.08 which satisfies 0 < 0.08 < 0.5, so convergence is guaranteed.
Misadjustment = mu * M * P_x = 0.08 * 4 * 0.5 = 0.16 (16% excess MSE)

Final Answer:
mu_max = 0.5, Misadjustment = 0.16 (dimensionless ratio)

Exam Tip: In GATE problems, always check convergence by verifying mu < 1/(M*P_x). If the input is white noise with variance sigma^2, then P_x = sigma^2. Misadjustment = mu*M*P_x is a commonly tested formula.

• Small mu gives slow convergence but low steady-state MSE.
• Large mu gives faster initial convergence but high excess MSE or divergence.
• The algorithm tracks non-stationary signals but with a lag proportional to 1/mu.
• LMS requires no matrix inversion, making it O(M) per update.
• The gradient noise causes fluctuations around the Wiener solution even after convergence.

Quick Revision

• LMS update: w(n+1) = w(n) + 2*mu*e(n)*x(n) where e(n) = d(n) - y(n).
• Convergence condition: 0 < mu < 1/(M * P_x).
• Misadjustment = mu * M * P_x, a ratio of excess MSE to minimum MSE.
• Computational cost: O(M) per sample, no matrix inversion needed.
• Increasing mu speeds convergence but raises steady-state error.
• GATE trap: LMS uses instantaneous gradient, not true gradient of MSE.
• For white noise input with variance sigma^2, P_x = sigma^2 directly.