Recursive least squares (RLS)

Also known as: RLS, recursive least squares, RLS algorithm

Recursive least squares (RLS) is an adaptive-filter algorithm that, at each new sample, updates the taps to be the exact least-squares solution over all data seen so far, achieving much faster and more uniform convergence than LMS — at the price of markedly higher computation.¹ Instead of taking a small gradient step, RLS recursively maintains an estimate of the inverse input-correlation matrix and uses it to make an optimally scaled correction to every tap.

RLS reaches its error floor in roughly as many samples as it has taps, while LMS decays gradually over many more — the payoff for RLS's O(N²) cost per sample.

How it works

RLS minimises an exponentially weighted sum of past squared errors, Σ λ^(n−i)·|e(i)|², and updates the solution recursively rather than re-solving from scratch:

It keeps a running inverse-correlation matrix P (the inverse of the weighted input autocorrelation). Applying the matrix inversion lemma lets P be updated from the previous P without an explicit matrix inverse each sample.
From P and the new input it forms a gain vector k (the RLS analogue of a Kalman gain) that says how strongly, and in which tap directions, to react to the latest error.
The taps update as w ← w + k·e, where e is the a priori error (computed with the old taps). Because k already encodes the input statistics, RLS effectively de-correlates the input, so — unlike LMS — its convergence is nearly independent of the input’s eigenvalue spread.

The upshot is convergence in roughly 2N samples for N taps, versus the many multiples of N that LMS needs on coloured inputs.

The forgetting factor

The forgetting factor λ (0 ≪ λ ≤ 1) sets how fast old data is discounted:

λ = 1 weights all history equally — best for a stationary channel, lowest steady error, but no ability to track change.
λ < 1 (typically 0.95–0.999) gives the filter a finite memory of about 1/(1−λ) samples, letting it track a time-varying channel at the cost of slightly higher steady-state error. Choosing λ trades tracking agility against noise immunity, the way μ does in LMS.

In practice

RLS’s speed comes with real costs: O(N²) work and storage per sample, and numerical sensitivity — the recursively propagated P can lose positive-definiteness in finite precision and cause divergence. Practical systems use square-root / QR-decomposition or fast RLS (FTF, lattice) variants that restore numerical stability or cut the cost back toward O(N). RLS is closely related to the Kalman filter, of which it is essentially a special case for a stationary weight vector.

Relevance to SDR

RLS is chosen when a channel must be equalized quickly from a short training burst — fast-fading HF/microwave links, burst modems, and initial acquisition where LMS would not converge inside the preamble. It sharpens the constellation and restores SNR with fewer training symbols than LMS, which is valuable when training overhead is scarce. GopherTrunk’s steady-rate P25/DMR/NXDN decode path does not deploy a full RLS equalizer — its narrowband, RRC-shaped signals are handled by matched filtering and synchronisation — so RLS is presented here as a general adaptive-filtering tool of the broader RF world.

Sources

Recursive least squares filter — Wikipedia, on the RLS recursion, the gain vector, and the forgetting factor. ↩