How the Recursive Least Squares Algorithm Works

When a new data point arrives, do you really have to redo the entire fit? No. The recursive least squares algorithm (RLS) updates its parameter estimate in place, so a sensor, a radio, or a controller can keep learning while it runs.

What is recursive least squares?

RLS is an adaptive filtering method that finds the coefficients minimizing a weighted sum of squared errors, one sample at a time. Ordinary least squares needs the whole data set and a matrix inversion on every refresh. RLS carries a compact summary forward instead: an inverse correlation matrix, usually called P. Berkeley’s EECS 225 A lecture note describes a fast recursive update with O(n²) complexity.

How each update works

For every new input vector x and desired output d, the filter runs four steps:

1. Error: e = d − wᵀx
2. Gain: k = Px / (λ + xᵀPx)
3. Weights: w = w + k·e
4. Matrix: P = (P − k·xᵀP) / λ

Start with w at zero and P as a large multiple of the identity matrix. That big starting value says “I know nothing yet,” so the first samples carry heavy influence.

Choosing the forgetting factor

The symbol λ sits between 0 and 1. At exactly 1, every sample counts equally, and you land on ordinary least squares. Drop it to 0.98 or 0.995, and older data fades, which helps when the system drifts. Go too low and the estimates get jumpy. I’d begin near 0.99 and adjust, though that’s a rule of thumb, not a law.

RLS vs LMS

LMS costs only O(n) per step but crawls when inputs are correlated. RLS converges much faster because it effectively whitens the data. You pay in computation and memory. Tiny hardware? Choose LMS. Need quick convergence? RLS wins.

Where it’s used

Echo cancellation, channel equalization, adaptive control, and online system identification all lean on it. Published research notes RLS is widely applied in real-time signal processing, control, and communications.

A common pitfall

P can drift away from symmetric, positive-definite form through rounding error, especially when λ is below 1 and the input barely changes. The result? Sudden blow-ups. QR-based or square-root versions fix this.

FAQ

Is RLS the same as a Kalman filter?
Closely related. With λ = 1, RLS matches a Kalman filter estimating a constant parameter vector.

What’s the computational cost?
O(n²) per update, where n is the number of coefficients.

What forgetting factor should I use?
Between 0.98 and 0.999 for most drifting systems; 1 for fixed parameters.

Can it handle changing systems?
Yes, that’s the job of λ below 1.