Signal Processing

Convergence Analysis

Q: How is the LMS step-size stability bound derived?

For the least mean squares algorithm to converge in the mean, the step size mu must satisfy 0 < mu < 2 / lambda_max, where lambda_max is the largest eigenvalue of the input autocorrelation matrix R. In practice a tighter mean-square bound of 0 < mu < 2 / (3 times trace(R)) is used, where trace(R) equals the total input power summed across the N filter taps. Because trace(R) grows with both filter length and input power, longer adaptive filters or stronger signals require proportionally smaller step sizes. Normalized LMS sidesteps this by dividing mu by the instantaneous input power, giving a power-independent stability range of 0 < mu_tilde < 2 that holds regardless of signal level, which is why NLMS is preferred in RF predistortion and equalization where input power varies.

Q: Why does eigenvalue spread slow LMS convergence?

LMS converges along the eigenvectors of the input autocorrelation matrix R, and each mode has its own time constant tau_k that is inversely proportional to its eigenvalue lambda_k. The overall settling time is dominated by the slowest mode, which corresponds to lambda_min. The ratio lambda_max / lambda_min, called the eigenvalue spread or condition number chi(R), therefore sets a hard limit: the slow modes converge chi times slower than the fast ones. A flat, white input has chi near 1 and converges fast, while a strongly colored input such as a narrowband RF carrier or a peaky OFDM spectrum can have chi of 100 or more, stretching convergence by two orders of magnitude. RLS is insensitive to eigenvalue spread because it whitens the input via the inverse correlation matrix, which is why it converges in roughly 2N samples regardless of spectrum shape.

Q: What is misadjustment and how does step size trade against it?

Misadjustment M is the fractional excess mean-square error that an adaptive filter exhibits at steady state compared with the optimal Wiener solution, expressed as M = (excess MSE) / (minimum MSE). For LMS it is approximately M = mu times trace(R) / 2. This exposes the central convergence trade-off: a large step size gives fast convergence and good tracking of time-varying RF channels but leaves large residual error and gradient noise, while a small step size gives low misadjustment and a clean steady state but slow convergence. A typical design target keeps misadjustment at 5 to 10 percent. Variable-step-size and leaky-LMS variants start with a large mu for fast acquisition then shrink it to reduce steady-state error, getting the best of both regimes.

/kuhn-VUR-juhns uh-NAL-uh-sis/

The mathematical discipline that predicts whether an iterative or adaptive filter will settle to a stable, useful solution and how many samples that takes. For gradient-based updates such as LMS, convergence is governed by the step size μ, the eigenvalues of the input autocorrelation matrix, and the resulting steady-state misadjustment. A design that converges too slowly cannot track a fading RF channel, while one pushed past its stability bound diverges and the filter weights blow up. In RF systems this analysis sets the loop bandwidth of digital predistorters, the training length of channel equalizers, and the lock time of adaptive beamformers, typically requiring 10N to 20N samples for LMS or about 2N samples for recursive least squares with an N-tap filter.

Category: Signal Processing

LMS Settling: 10N to 20N samples

Stability Bound: 0 < μ < 2/λ_max

How Adaptive Algorithms Reach Steady State

Every adaptive RF subsystem, from a digital predistorter linearizing a GaN power amplifier to an equalizer cleaning up a multipath microwave link, runs an iterative weight-update loop that drives an error signal toward zero. Convergence analysis answers two practical questions about that loop: will it reach a stable solution at all, and how many update iterations does it need. The first question is a stability problem and the second is a transient-response problem, and both are decided by the interaction between the chosen step size and the statistics of the input signal. When the answers are wrong, the symptoms are unmistakable: a predistorter that never locks, an equalizer whose tap weights oscillate, or a beamformer that takes so long to settle that the target has already moved.

The cleanest way to reason about convergence is to transform the weight-error vector into the coordinate system defined by the eigenvectors of the input autocorrelation matrix R. In those coordinates the coupled update equations decouple into N independent first-order modes, one per eigenvalue. Each mode decays geometrically with its own time constant, and the slowest mode, tied to the smallest eigenvalue, dictates how long the whole filter takes to settle. This is why the eigenvalue spread λ_max/λ_min, not just the filter length, is the single most important predictor of LMS speed. A white, well-conditioned input converges in a handful of filter lengths; a narrowband or strongly correlated RF signal can stretch the same filter by one to two orders of magnitude.

Recursive least squares takes a different route to the same destination. Rather than stepping down a noisy gradient, RLS maintains a running estimate of the inverse correlation matrix and effectively pre-whitens the input, which makes its convergence rate independent of eigenvalue spread. The price is O(N²) arithmetic per sample versus the O(N) cost of LMS, plus the risk of numerical instability if the inverse-correlation update is not regularized. Choosing between the two families is itself a convergence-analysis decision: how fast must the loop settle, how colored is the input spectrum, and how much DSP budget is available.

Stability Bounds and Time Constants

Mean-Convergence Stability Bound (LMS):
0 < μ < 2 / λ_max  (tighter MSE bound: μ < 2 / [3·trace(R)])

Modal Time Constant (k-th mode):
τ_k ≈ 1 / (2 μ λ_k)  →  slowest mode set by λ_min

Eigenvalue Spread (condition number):
χ(R) = λ_max / λ_min  (χ ≈ 1 white input, χ > 100 strongly colored)

Steady-State Misadjustment (LMS):
M ≈ μ × trace(R) / 2  (target M ≈ 0.05 to 0.10)

Where μ = step size, λ_k = k-th eigenvalue of input autocorrelation matrix R, trace(R) = total input power across N taps. Example: white input, N=32, trace(R)=1 so each λ=1/32, μ=0.1 → M ≈ μ·trace(R)/2 = 0.05, τ ≈ 1/(2μλ) ≈ 160 samples (about 5N), settling in a few τ.

Convergence Behavior by Algorithm

Algorithm	Convergence Time	Eigenvalue-Spread Sensitivity	Cost / Sample	Steady-State Error	Typical RF Use
LMS	10N to 20N samples	High (slows with χ)	O(N)	Misadjustment ~5 to 10%	Echo cancel, simple DPD
NLMS	5N to 15N samples	High	O(N)	Power-independent bound	Equalizers, variable power
RLS	~2N samples	None (whitened)	O(N²)	Near-optimal Wiener	Fast-lock DPD, MIMO
Affine projection	3N to 8N samples	Moderate	O(KN)	Between LMS and RLS	Colored-input adaptation
Memory-polynomial DPD	2 to 8 iterations	Low (indirect learning)	Per-block LS	ACLR floor limited	GaN PA linearization

Common Questions

Frequently Asked Questions

How is the LMS step-size stability bound derived?

Convergence in the mean requires 0 < μ < 2/λ_max, where λ_max is the largest eigenvalue of the input autocorrelation matrix R. In practice a tighter mean-square bound μ < 2/(3·trace(R)) is used, where trace(R) is total input power across the N taps. Longer filters or stronger signals therefore need smaller μ. Normalized LMS divides μ by instantaneous input power, giving a power-independent range 0 < μ˜ < 2, which is why NLMS is favored for predistortion and equalization with varying signal levels.

Why does eigenvalue spread slow LMS convergence?

LMS converges along the eigenvectors of R, and each mode has time constant τ_k ≈ 1/(2μλ_k), so the slowest mode is fixed by λ_min. The spread χ = λ_max/λ_min then sets the gap: slow modes converge χ times slower than fast ones. A white input has χ near 1; a narrowband carrier or peaky OFDM spectrum can hit χ > 100, stretching settling by two orders of magnitude. RLS avoids this by whitening the input, converging in roughly 2N samples regardless of spectrum shape.

What is misadjustment and how does step size trade against it?

Misadjustment M is the fractional excess mean-square error at steady state versus the optimal Wiener solution; for LMS, M ≈ μ·trace(R)/2. This is the core trade-off: large μ gives fast convergence and good channel tracking but leaves large residual error, while small μ gives a clean steady state but slow settling. A typical target keeps M at 5 to 10 percent. Variable-step-size and leaky-LMS variants start with a large μ for fast acquisition then shrink it to drive down steady-state error.

Related Terms

← Controlled Ramp Convergence (DPD) →