Recursive Least Squares (RLS)

RLS minimizes a deterministic cost function consisting of the exponentially weighted sum of squared errors. Unlike LMS, which minimizes the instantaneous squared error, RLS considers all past errors from the moment the algorithm was initialized. The forgetting factor (λ), typically between 0.95 and 0.999, assigns exponentially less weight to older data, enabling the filter to track time-varying channel statistics. This formulation provides the exact least squares solution for the finite data record available at each time step.

The computational core of RLS is the recursive update of the inverse of the input signal's autocorrelation matrix. Using the Woodbury matrix identity (also known as the matrix inversion lemma), RLS avoids explicitly inverting a large matrix at each iteration. Instead, it computes a rank-1 update to the inverse correlation matrix with O(N²) complexity, where N is the filter length. This recursive formulation is what gives the algorithm its name and enables its fast convergence properties.

At each iteration, RLS computes a Kalman gain vector that determines the optimal step size for updating filter coefficients. This gain vector is data-dependent and adjusts automatically based on the statistical properties of the input signal. Unlike the fixed step-size parameter in LMS, the Kalman gain provides an optimal variable learning rate for each filter tap, ensuring rapid convergence without manual tuning. The gain vector is computed from the inverse correlation matrix and the current input regressor.

A critical property of RLS is that its convergence rate is independent of the eigenvalue spread of the input signal's autocorrelation matrix. In LMS, a wide eigenvalue spread—common in signals with strong spectral dynamics—causes dramatically slow convergence. RLS whitens the input data implicitly through its inverse correlation matrix, achieving convergence within approximately 2N iterations, where N is the filter order. This makes RLS ideal for channel estimation in frequency-selective fading environments.

The superior convergence performance of RLS comes at a significant computational cost. Standard RLS requires O(N²) operations per iteration due to the matrix-vector multiplications in the gain vector and inverse correlation matrix updates. In contrast, LMS requires only O(N) operations. For a 32-tap equalizer, RLS may require over 1,000 multiply-accumulate operations per sample. Fast RLS variants, such as the QR-decomposition-based RLS and lattice RLS, reduce complexity to O(N) while preserving numerical stability.

RLS is susceptible to numerical instability due to the accumulation of round-off errors in the recursive inverse correlation matrix update. The matrix may lose symmetry or positive definiteness over time, causing algorithm divergence. To mitigate this, regularization is applied by initializing the inverse correlation matrix as δ⁻¹I, where δ is a small positive constant. Additionally, square-root formulations—such as QR-RLS—propagate the Cholesky factor of the inverse correlation matrix, guaranteeing positive definiteness and improving numerical robustness in fixed-point implementations.

A stochastic gradient descent algorithm that updates filter coefficients using only the instantaneous estimate of the gradient. Unlike RLS, LMS does not require matrix inversion, making it computationally lightweight but significantly slower to converge.

• Complexity: O(N) per iteration vs RLS O(N²)
• Convergence: Slower, especially for correlated inputs
• Use case: Real-time applications where simplicity outweighs speed
• Trade-off: Lower computational cost at the expense of slower adaptation to channel changes

A recursive Bayesian estimator that predicts and corrects the state of a dynamic system using a state-space model. While RLS is a special case of the Kalman filter for static parameter estimation, the full Kalman filter explicitly models process noise and measurement noise covariances.

• State-space formulation: Models both system dynamics and observations
• Optimality: Minimum variance estimator for linear Gaussian systems
• RLS relationship: RLS emerges when the state transition matrix is identity
• Application: Tracking rapid phase and amplitude fluctuations in mobile channels

A statistical estimation framework that computes the optimal linear filter by minimizing the expected value of the squared error. Unlike RLS, which operates recursively on streaming data, MMSE typically requires batch knowledge of second-order statistics.

• Requires: Auto-correlation matrix R and cross-correlation vector p
• Solution: Wiener-Hopf equation w = R⁻¹p
• RLS connection: RLS recursively approximates the Wiener solution as new data arrives
• Benchmark: MMSE provides the theoretical performance bound that RLS asymptotically approaches

A blind adaptive equalization algorithm that exploits the constant envelope property of PSK and FM signals. Unlike RLS, which requires a known training sequence, CMA updates filter taps by penalizing deviations from a fixed modulus.

• Cost function: Minimizes (|y(n)|² - R₂)² where R₂ is a constant
• No training required: Operates without a reference signal
• Convergence: Generally slower than trained RLS
• Application: Initial acquisition phase before switching to decision-directed RLS for fine tracking

A non-linear equalization architecture that uses previously detected symbols to cancel post-cursor ISI. RLS is frequently employed as the coefficient update mechanism within the feedforward and feedback filters of a DFE.

• Structure: Feedforward filter + feedback filter + slicer
• RLS role: Adaptively updates both filter sections simultaneously
• Advantage: Handles severe multipath without noise enhancement
• Complexity: RLS-DFE provides faster convergence than LMS-DFE at higher computational cost

The exponential weighting parameter λ (0 < λ ≤ 1) controls RLS memory. Values closer to 1 provide better steady-state performance in stationary environments, while smaller values enable faster tracking of non-stationary channels.

• λ = 1: Infinite memory, optimal for stationary channels
• λ = 0.99: Effective memory of ~100 samples
• λ = 0.95: Effective memory of ~20 samples, aggressive tracking
• Trade-off: Smaller λ increases misadjustment noise but improves Doppler tracking capability