RLS Algorithm

The Recursive Least Squares (RLS) algorithm is an adaptive filtering algorithm that minimizes a weighted sum of past squared errors rather than just the instantaneous squared error used by LMS. It achieves significantly faster convergence than LMS, especially in correlated input environments, at the cost of higher computational complexity. Understanding RLS is important for GATE aspirants because it represents a fundamentally different philosophy of adaptation compared to LMS.

Core Concept of RLS

The fundamental difference between RLS and LMS lies in the cost function being minimized. LMS minimizes the instantaneous squared error at each step, which is a noisy estimate. RLS minimizes a weighted least squares cost function that sums all past squared errors with exponentially decaying weights. This gives RLS access to far more information per update, leading to much faster and more accurate convergence.

The forgetting factor lambda (0 < lambda <= 1) controls how quickly past data is discounted. A value of lambda = 1 weights all past data equally, suitable for stationary signals. A value of lambda = 0.98 discounts older samples, allowing the filter to track slowly varying signals. This is a key design parameter in RLS and is frequently tested in GATE.

Internally, RLS maintains an inverse of the input correlation matrix denoted P(n). This matrix captures the statistical relationship between all past inputs, enabling optimal weight updates in one step. The Woodbury matrix identity is used to recursively update P(n) without directly inverting the full matrix, keeping the algorithm tractable.

Mathematical Expression

At each time step, RLS first computes the Kalman gain vector k(n) using the current input x(n) and the matrix P(n-1). The gain determines how much the error at time n should influence each weight. The weight update then adds the scaled error correction, and finally P(n) is updated using the outer product correction term. All three steps happen in sequence for each new sample.

The gain vector computation is k(n) = P(n-1)*x(n) / (lambda + x^T(n)*P(n-1)*x(n)). The weight update is w(n) = w(n-1) + k(n)*e(n). The matrix update is P(n) = (1/lambda)*[P(n-1) - k(n)*x^T(n)*P(n-1)]. The complexity is O(M^2) per sample due to the matrix-vector products.

Practical Understanding

RLS converges in approximately M iterations regardless of the input signal's eigenvalue spread, whereas LMS convergence depends strongly on the condition number of the input correlation matrix. This makes RLS dramatically superior for correlated inputs such as speech signals or narrowband interference.

The major drawback is computational cost. RLS requires O(M^2) operations per sample compared to O(M) for LMS. For a filter of order M=100, this means 10,000 versus 200 operations per sample, a 50x increase. Fast RLS variants such as Fast Transversal Filter (FTF) reduce this to O(M) but at the cost of numerical stability issues.

Given:
Filter order M = 3, Forgetting factor lambda = 0.95
Initial P(0) = delta_inverse * I where delta = 0.01

Why this formula applies:
P(0) must be initialized to a large value to allow fast early adaptation

Formula:
P(0) = (1/delta) * I_M

Substitution:
P(0) = (1/0.01) * I_3 = 100 * I_3

Calculation:
P(0) = diag(100, 100, 100)
Effective memory length L_eff = 1/(1-lambda) = 1/(1-0.95) = 20 samples

Final Answer:
P(0) is a 3x3 diagonal matrix with all diagonal entries = 100.
The filter forgets data older than approximately 20 samples.

Exam Tip: RLS always converges in approximately M steps. LMS convergence time depends on eigenvalue spread of R_xx. For GATE, remember: RLS is O(M^2) per sample, LMS is O(M) per sample. Forgetting factor lambda = 1 means infinite memory.

• RLS minimizes weighted sum of all past squared errors using a forgetting factor lambda.
• The P(n) matrix is the inverse of the weighted input correlation matrix and is updated recursively.
• Gain vector k(n) performs a Kalman-filter-like optimal correction at each step.
• RLS convergence is independent of input eigenvalue spread, unlike LMS.
• Higher complexity O(M^2) limits RLS use in high-order or real-time systems.

Quick Revision

• RLS cost function: sum of lambda^(n-k) * e^2(k) for k from 0 to n.
• Key equations: k(n) gain, w(n) update, P(n) matrix update.
• Forgetting factor: lambda=1 (infinite memory), lambda<1 (finite, tracks non-stationary).
• Effective memory length = 1/(1-lambda) samples.
• Complexity: O(M^2) vs O(M) for LMS.
• GATE trap: RLS does not have a step size; convergence speed is set by lambda, not a gain parameter.
• RLS converges in approximately M iterations regardless of input statistics.