Questions: Advanced Adaptive Filtering

Question 1

The LMS algorithm uses a stochastic gradient: w(n+1) = w(n) − μ·e(n)·x(n), where e(n) is instantaneous error and μ is step-size. Why does LMS converge slowly compared to Recursive Least Squares (RLS), which computes the least-squares solution at each step?

• A. LMS is greedy and makes small adjustments; RLS uses matrix inversion to find the optimal update direction, converging much faster
• B. LMS uses a noisy gradient estimate (one sample per step), while RLS uses all past data weighted exponentially, giving a more accurate gradient direction. RLS convergence is exponential; LMS is geometric with rate proportional to eigenvalue spread of input autocorrelation
• C. LMS is inherently slower by design; RLS is faster but less stable
• D. RLS solves the optimization offline; LMS solves online, making LMS slower

Answer: (B)

LMS converges in roughly O(1/μ·condition_number) steps, where condition number characterizes the input's eigenvalue spread. RLS converges exponentially: the error decays as O(λ^n) for λ < 1. This exponential advantage comes from RLS using all past samples (with exponential weighting) to estimate the gradient direction, while LMS uses only the current sample. RLS computational cost is O(M²) per step (M is filter length, due to matrix updates); LMS is O(M). The trade-off is fundamental: faster convergence costs more computation and can be numerically unstable (matrix inversion in RLS can amplify errors if eigenvalues are tiny).

Question 2

In Normalized LMS (NLMS), the step-size is normalized by the input power: μ_n = μ / (α + ||x(n)||²). How does this normalization improve robustness, and what is the trade-off?

• A. NLMS automatically adapts to input scaling; if input amplitude changes, the step-size adjusts to maintain stable convergence. The cost is one additional division per step
• B. NLMS ensures the filter weight update is always in the direction of steepest descent
• C. NLMS removes the need for the step-size parameter μ; it is automatically determined
• D. NLMS is numerically identical to LMS; the normalization is a theoretical simplification only

Answer: (A)

Standard LMS with fixed μ has poor performance if the input signal's power varies: when power is low, the gradient noise dominates and LMS misadjusts; when power is high, convergence is slow (small relative step). NLMS divides by ||x(n)||², normalizing the update magnitude to the input power. This makes convergence rate (and stability) independent of input power scaling — a robustness feature essential in applications like echo cancellation where microphone level can vary wildly. The cost is one division and squaring per sample, negligible compared to the filter tap updates.

Question 3

Recursive Least Squares (RLS) maintains an M×M matrix P (inverse of input autocorrelation) and updates it via: P(n) = [P(n−1) − P(n−1)x(n)x(n)ᵀP(n−1) / (1 + x(n)ᵀP(n−1)x(n))] / λ, where λ is a forgetting factor < 1. What does the forgetting factor accomplish in a time-varying environment?

• T. True
• F. False

Answer: True

Without forgetting (λ = 1), RLS weights all past data equally, optimal for stationary systems but slow to adapt to changes. With λ ≈ 0.99–0.999, old data is downweighted exponentially, so the algorithm 'forgets' the past at an exponential rate. This allows RLS to track time-varying systems: when the unknown system changes, recent data gets high weight in the least-squares solution, and the filter adapts. The trade-off: forgetting reduces the effective sample size, so the filter has higher steady-state error in stationary conditions (it is not truly optimal because it underweights past data). Tuning λ is a design choice: λ closer to 1 suits slowly varying systems; λ closer to 0.99 suits rapidly changing systems.

Question 4

Echo cancellation in teleconferencing uses an adaptive filter to model and subtract the acoustic feedback path (speaker-to-microphone through the room). Why is this problem hard, and why does RLS outperform LMS here?

• T. True
• F. False

Answer: True

Echo cancellation is hard because: (1) the acoustic impulse response is typically long (many taps), giving a high-dimensional problem; (2) the room impulse response is time-varying (people moving, doors, temperature); (3) convergence must be fast enough to track voice changes in real-time; (4) eigenvalue spread of room acoustics is large (coloration), making LMS convergence very slow. RLS's exponential convergence (despite O(M²) cost) is justified by the need for real-time adaptation and long filters. Practical echo cancellation uses RLS with forgetting factor (to track room changes), preprocessing (decorrelation of input to improve conditioning), and constraint satisfaction (force filter taps to stay within expected acoustical bounds).

Question 5

Explain the relationship between Kalman filtering and optimal adaptive filtering: when is a Kalman filter the optimal adaptive filter, and what assumptions does it require?

Model answer: A Kalman filter is optimal adaptive filtering for linear systems with Gaussian noise: it minimizes mean-squared error when the system dynamics and noise statistics are known or estimated. Unlike LMS (which only minimizes error at the current step) or RLS (which minimizes cumulative squared error from all past steps), the Kalman filter jointly optimizes the system state estimate and output prediction, accounting for model uncertainties via process and measurement noise covariances Q and R. The Kalman gain balances prediction error and measurement noise: large Q (uncertain dynamics) increases the Kalman gain, trusting measurements more; large R (noisy measurements) decreases the gain, trusting the prediction more. When the filter order and noise statistics are known accurately, Kalman filtering achieves the Cramér-Rao lower bound (best possible MSE). The requirements: linearity (or local linearization in Extended Kalman Filter), Gaussian noise (or Laplace approximation if approximately true), and known statistics (Q and R must be estimated or assumed).

In practice, LMS and RLS are often preferred over Kalman because they don't require knowing or estimating Q and R, and they adapt automatically. But if the system is linear and noise statistics can be measured or estimated, Kalman filtering gives superior performance with the same computational budget (both are O(M) for LMS or O(M²) for RLS). The three algorithms represent a spectrum: LMS (simplest, slowest), RLS (fastest, most complex), Kalman (optimal if model is correct, intermediate complexity). Modern applications often use Kalman for control systems (GPS/IMU fusion in drones) and RLS for communication systems (channel estimation, echo cancellation).