Approximate NLMS

1. Approximate NLMS

Context Recap

We already learned:

LMS is simple but its performance heavily depends on the step size μ, which in turn
depends on the eigenvalues of R . x

NLMS fixes this by adapting μ dynamically at every iteration using the input vector's
energy ∥x(n)∥ , making it better suited for non-stationary signals.
2

But: NLMS involves division, which is expensive in hardware.

Solution? Approximate NLMS - A clever hardware-friendly way to approximate the
NLMS weight update.

1. What’s the Problem?

NLMS update:
∗
e (n)x(n)
w(n + 1) = w(n) + β ⋅
2
∥x(n)∥ + ϵ

Here:

∥x(n)∥
2
is a vector norm.
This update involves division, which is:
Hard to implement efficiently in low-power or embedded processors.
Much slower than multiplication or shifting.

2. The Key Approximation Idea

Approximate the division by using floating point tricks:

Floating point numbers are stored like:

exponent
Number = mantissa × 2

So the norm squared can be written as:

2 k
∥x(n)∥ ≈ m ⋅ 2
 Where:

m ≈ 1 (approximate mantissa),
2
k
is the power-of-two part.
Then:

1 −k
≈ 2
∥x(n)∥ 2

✅ No real division! Just a bit shift. (Shifting right = dividing by 2)

3. Implementation: All Shift, No Mult or Div

If you do:
∗
e (n)x(n)
∗ −k
≈ e (n) ⋅ x(n) ⋅ 2
2
∥x(n)∥

And:

If you further approximate β as 2 , then:−b

Update ≈ Shif ted version of x(n)

All done using bit shifts.

You only compute the required shift amount once per sample, and apply it to the
entire vector.

4. Benefits

No division.
No multiplication (if error and β also approximated).
Works great in DSPs, embedded systems, or custom hardware (FPGAs).
Despite all the approximations, performance barely degrades and computational
efficiency improves massively.

Sign LMS Algorithm

2. Sign LMS Algorithm

What problem are we solving here?

We want to make LMS-style adaptive filters:

 Faster
Cheaper to compute
Especially useful on older or low-power hardware that struggles with
multiplications

Key Idea: Replace Multiplication with Signs (±1)

Multiplications are expensive, but adding or subtracting is cheap. If we just use the
signs (i.e., ±1) of numbers, we can turn the LMS update into pure addition/subtraction
— no multiply needed.

This leads to three main algorithms:

1. Sign-Error LMS

Replace the error e(n) with its sign:

w(n + 1) = w(n) + μ ⋅ sign(e(n)) ⋅ x(n)

Instead of scaling by the actual error, just move weights in the direction of the error
(positive or negative).
If μ is a power of 2, update becomes a simple bit-shift + add/subtract.

✅ Very simple
❌ But: You lose sensitivity — big and small errors cause same-size updates. So:
As you approach the optimal solution, error is small, but step size doesn't shrink.
Leads to high misadjustment unless you choose a very small μ (which slows
learning).

2. Sign-Data LMS

Replace input x(n) with its sign vector:

w(n + 1) = w(n) + μ ⋅ e(n) ⋅ sign(x(n))

So you keep the error’s actual value, but simplify input vector to just its signs.
The update step is now:
Just add/subtract scaled error, based on the direction of each input component.
✅ Keeps sensitivity to error size
✅ Still avoids full multiplications
✅ Works well if input signal statistics don't change too much
❌ Slightly worse than full LMS in dynamic environments

3. Sign-Sign LMS

Replace both e(n) and x(n) with their signs:

w(n + 1) = w(n) + μ ⋅ sign(e(n)) ⋅ sign(x(n))

This is the most aggressive simplification:

No multiplications
Only additions and subtractions of μ

✅ Super efficient (especially for hardware without multipliers)

✅ Used in early speech coding standards (e.g., ADPCM)
❌ Crude: Treats small and large errors the same
❌ Slower convergence, needs tiny step size to avoid divergence
❌ Doesn't adapt well to complex or fast-changing signals

Why Were These Algorithms Important?

“Back in the day, processors didn’t even have hardware multipliers.”

So:

These sign-based methods let engineers build real-time adaptive filters even with
primitive microcontrollers.
Today, we mostly use them when power or complexity is critical, like:
​ IoT devices
Low-end DSP chips
Embedded voice/speech coders

Final Takeaways

These Sign LMS variants are all about approximation for efficiency.
Sign-error is crude but ultra-simple.
Sign-data is the best compromise (keeps sensitivity, avoids multiplies).
 Sign-sign is the most hardware-friendly but least accurate.
All were essential historically, and still useful in ultra-low-power embedded
systems today.

LMS Variants
3. LMS Variants

1. Least Mean Absolute Value (LMAV) Algorithm

We’re used to LMS minimizing mean squared error (MSE). But LMAV takes a different
approach:

Instead of minimizing E[e 2

, we minimize:
(n)]

E[|e(n)|]

This changes the way we compute the gradient (because the derivative of absolute
value is not defined at 0, and is discontinuous).
If e(n) > 0, the gradient is −x(n)
If e(n) < 0, the gradient is +x(n)
If e(n) = 0, we just ignore the update (gradient = 0)
Therefore, the update rule looks like:

w(n + 1) = w(n) + μ ⋅ sign(e(n)) ⋅ x(n)

Which is… exactly the same as the Sign-Error LMS algorithm!

Trying to minimize the absolute error instead of squared error brings us right back to
the Sign-Error LMS — so nothing new here, but a neat connection!

2. LMS Variations

There are tons of variants of LMS. The following ones help in different practical
situations:

A. Block Adaptation

Problem: LMS updates are noisy and vary too much between samples.

Solution:
 Instead of updating weights every time, average the quantities used in the update
over several samples before updating.
For example, instead of updating on every e(n) ⋅ x(n), wait for 10 samples and
average.
This makes the learning smoother, although:
It doesn’t improve convergence speed
Might slightly slow down convergence
But reduces jumpiness and instability

B. Delayed Update (for Pipelining)

Problem: On some hardware (like pipelined processors), computing the output and
updating weights can’t happen at the same time.

Solution:

Compute the filter output for input x(n)

But delay the update by 1 or more steps, i.e. update weights using older errors
This is called the delayed LMS update:

w(n + 1) = w(n) + μ ⋅ e(n − d) ⋅ x(n − d)

As long as the delay d is small, performance is similar to standard LMS

C. Partial Update

Problem: In a long filter (e.g. 100 coefficients), updating every weight is computationally
heavy.

Solution:

Update only a few weights at a time, like 4 out of 16

On the next sample, update another set of weights
This reduces computation per sample but:
Slightly worsens performance
Is useful when hardware or power is constrained

D. Momentum LMS
Motivation:

In regular LMS:

You have a fixed step size μ.

You want fast learning when far from optimal weights.
But also fine, small updates when you're close.

Momentum LMS tries to simulate acceleration like in physics — building "speed" in a

direction when the updates are consistently going that way.

Core Idea:

You add a momentum term to the usual LMS update:

w(n + 1) = w(n) + μe(n)x(n) + α [w(n) − w(n − 1)]

where:

α is the momentum coefficient (typically 0 < α < 1)

w(n) − w(n − 1) is the previous weight change

Intuition:

When your weight updates keep going in the same direction, the difference
w(n) − w(n − 1) is large → the momentum amplifies your step → faster

convergence early on.

Once you’re close to optimal weights, the error changes direction more → this
momentum starts canceling out, naturally slowing down the updates.

So:

It accelerates learning early

It slows down near convergence
Without adjusting μ manually like in variable step size LMS

Performance Notes:

You can use a slightly larger μ than in basic LMS if α > 0

But too large α or μ → instability
It converges in the mean (i.e., expected value of weights converges)
But misadjustment (how close weights stay to optimal on average) may be slightly
worse
You can reduce μ by a factor 1

1+α
to fix that
E. P-Vector LMS

Motivation:

All previous LMS-type algorithms need:

An error signal: e(n) = d(n) − y(n)

^

And therefore the desired signal d(n)

But what if:

You don’t have d(n) available at every time instant?

Yet you still want to learn something about the underlying system?

Core Idea:

Use expected correlations instead of per-sample updates.

You replace:

d(n)x(n) with its expected value: r dx = E[d(n)x(n)]

And update weights like:

w(n + 1) = w(n) + μ (r dx − R x w(n))

Where:

T
R x = E[x(n)x (n)]

r dx = E[d(n)x(n)]

This is like applying the Wiener-Hopf solution incrementally, when true data is
unavailable, but statistics are known.

Example Case:

If:

x(n) = d(n) + v(n) , where v(n) is uncorrelated noise

And you know the autocorrelation of d(n)

Then:

You can compute r dx and use that in the update

Even if you don’t observe d(n) directly
 Caveat:

You must know or estimate the second-order statistics (correlations)

This method doesn’t work well in real-time if the environment is nonstationary

Variable Step-Size LMS (VSSLMS)

4. Variable Step-Size LMS

Variable step-size LMS (VSSLMS) in echo cancellation applications.

Note: This is only for LMS as NLMS already solves a lot of LMS's issues out of the
box.

Why Variable Step-Size?

In traditional LMS, we pick a fixed learning rate μ. But there's always a trade-off:

Large μ → fast learning, but noisy and unstable once close to the solution.
Small μ → stable and accurate, but slow to adapt.

Variable step-size LMS (VSSLMS) tries to give you both:

Adapt quickly when needed, and then slow down to maintain precision.

Basic Variable Step Size Formulas

We can define μ(n) to shrink over time:

Simple form:

1
μ(n) =
C + n

More flexible:

1
μ(n) =
C1 + C2 n

This lets you control how fast it shrinks. You can also clamp it with:

1
μ(n) = max ( , μ min )
C1 + C2 n
So μ doesn’t become too small to adapt.
This strategy is great when the system is stationary, i.e., the optimal solution doesn’t
change.

But What If the System Changes?

In non-stationary systems (like real-world environments), the echo path or signal might
change. Then:

We must increase μ again to adapt.

Example: if you move a phone during a call, the echo path changes — the filter must
re-learn fast.

Resetting μ

To do this, we monitor the error:

If the error suddenly jumps, we reset μ to a large value to adapt quickly.

After converging again, we let μ shrink as before.

The Double Talk Problem

Here’s the catch:

Error spikes could mean the echo path changed (OK to adapt) or
Someone started talking (❗Don’t adapt — that’s not error, that’s valid speech!)

This is called double talk — when both near-end and far-end users are talking at once.

If you adapt during double talk, the filter can misadjust, thinking speech is error.

Echo Cancellation Application (Visualized)

Imagine:

Speaker signal → goes out, echoes in the room

Microphone hears echo + someone speaking
We want to cancel just the echo
The LMS filter learns the room’s impulse response (speaker-to-mic path). When the
environment changes, we need fast adaptation → hence VSSLMS.

But we don’t want to learn someone’s speech as if it's the echo — that’s where double
talk detection becomes crucial.

Practical Trick: Parallel Adaptive Filters

To solve this problem:

Use two filters:

​ 1. Frozen filter – doesn’t adapt; produces output
2. Adaptive filter – always updates weights
If the adaptive filter performs better, we copy its weights over
Otherwise, we ignore its updates

✅ Ensures continuous learning but prevents damage from bad updates

Smarter VSSLMS: Using Sign Changes

Another strategy:

Instead of tracking time or errors, monitor sign changes in the gradient:

e(n) ⋅ x(n)

If sign stays the same over many steps:

→ we're still far from optimal → increase μ
If sign keeps flipping:
→ we're near the solution → decrease μ

This approach adapts the learning rate dynamically, without needing explicit error
monitoring or double talk detection.

Per-Tap Step Size: μ k (n)

Even cooler: assign a separate μ for each tap (weight) in the filter.
k

If one tap is far off → let it adapt faster

If another is stable → slow it down
 This fine-tuning makes adaptation even more precise and efficient.

Illustration Summary

At first, weights are far from optimal → quick updates

As error shrinks → step size shrinks
If something changes → error spikes → step size resets → fast re-learning
Optional: use sign-based dynamic μ for smoother behavior

Pitfall: Overshoot

One issue: if μ becomes large (e.g. after a reset), it may take time to shrink back. This
could cause overshoot — where weights go too far and take time to stabilize again.

This is where explicit error detection (vs. sign tracking) has an edge: it lets you reset
immediately and precisely.

Takeaway

Variable step-size LMS gives the best of both worlds:

Fast adaptation when needed (changing environments)

Low error once converged (stable conditions)

But… you must manage:

How you adjust μ

When to reset it
Whether it's safe to adapt (e.g., in double talk)

Regularized LMS
5. Regularized LMS

Problem: Real-World Systems Have DC-Blocked Inputs

In practice, most input signals to an adaptive filter (like LMS) go through blocking
capacitors and biasing circuits before entering an ADC (Analog-to-Digital
Converter). These circuits:
 Remove DC (zero frequency) components.
Act like high-pass filters, cutting out low-frequency energy.

Because of this, the input x(n) lacks low-frequency components — especially the DC
component.

Why This Matters: Eigenvalues of Rx

Remember that the convergence behavior of LMS depends on the eigenvalues of the
input autocorrelation matrix R . x

If R is not full rank (because we’re missing DC or low-frequency content), some

x

eigenvalues are 0.
In these directions, weights don't converge — they just "float" or stay fixed.
Worse, in finite-precision arithmetic, small rounding errors in the weights
accumulate unbounded DC offsets.

What Happens in Practice

When a real system has:

DC-blocked input x(n),

finite precision (fixed-point or limited floating-point),

Then:

1. Random rounding errors introduce small DC offsets into the weights.

2. Since x(n) has no DC content, these offsets are never corrected.
3. Over time, these grow and corrupt the filter.
4. System might work for minutes… then suddenly break → filter "blows up".
5. Eventually, the weights swing back and the cycle repeats.

This is a real-world bug often seen in practical deployments.

Solution 1: Leaky LMS

Add a "leak" term to the weight update:

w(n + 1) = (1 − μγ)w(n) + μe(n)x(n)

Here:

γ is a small positive constant (e.g. 2 −14

).
The term (1 − μγ)w(n) slowly shrinks the weights, preventing DC offset buildup.

📌 Interpretation:
It’s like applying regularization to penalize large weights.
Even if DC energy is missing in x(n), the leaky term ensures weights don’t drift
uncontrollably.

How to Implement Easily

If using fixed-point hardware:

Multiplying by (1 − μγ) can be done by a bit shift, making it efficient.

Effect on Convergence

The leak modifies the effective R : eigenvalues become λ

x i + γ .
So previously zero eigenvalues now become non-zero.
This restores convergence in all directions.
But: the final weights will be close to, but not exactly equal to the Wiener optimal
solution — a small tradeoff.

Solution 2: Add White Noise to Input

Another way to ensure all eigenvalues are > 0:

Add white noise n(n) to x(n):

~
x(n) = x(n) + n(n)

This makes R ~
x
= R x + γI , just like in Leaky LMS.

🎯 But: This introduces noise into your output, which is undesirable.

Hybrid Solution
 Use the noisy signal x(n)
~
only for adaptation.
For final output, use a clean version of x(n) passed through the same filter weights.
This way, you get robust adaptation with clean output.

Frequency Domain LMS

6. Frequency Domain LMS

The Idea

We want to speed up LMS adaptation and handle colored signals better. So instead
of doing the LMS adaptation in the time domain, we move everything into the
frequency domain using the Fast Fourier Transform (FFT).

Why? Because in DSP:

Time-domain convolution = Frequency-domain multiplication (which is much

faster using FFTs).

How it works

1. Take a block of input samples x(n) and apply an FFT → move to frequency
domain.
2. Use a separate (very short) adaptive filter for each frequency bin.
​ Each filter has length 1 (only 1 complex coefficient per frequency).
This speeds up adaptation because shorter filters converge faster.
Also avoids issues with eigenvalue spread that slow LMS down when input is
colored.
3. Multiply in the frequency domain → gives you the filter output.
4. Inverse FFT to bring it back to time domain.

But there’s a catch:

In frequency domain, basic convolution = circular convolution, not the linear

convolution we usually want.

What’s circular convolution?

If input length is N , and filter length is N , then:

Output should be of length 2N - 1 .

 But FFT returns only N points.
The extra N-1 points wrap around and corrupt the valid output.

Fixing the circular convolution issue

Method: Zero-padding & Overlap-Add

1. Zero-pad input and filter to length 2N .

2. Now FFT of length 2N → avoids wrapping (circular convolution).
3. After inverse FFT, still get some overlap between blocks.
4. Use windowing (e.g., Hamming window) and overlap-add:
​ Apply a smooth window to the input block.
Shift the next block by N/2 (half overlap).
The raised cosine shape of the window ensures blocks sum up smoothly without
distortion.

⚠️ This slightly increases complexity but restores correct linear convolution

behavior.

Advantages

Much faster adaptation, since each filter is of length 1.

No eigenvalue spread issues, because you're only working within narrow frequency
bands.
Works great for colored signals, where traditional LMS struggles.
FFT is computationally efficient, especially for long filters.

Why not always use it?

More complex implementation.

Needs careful windowing and overlap-add to avoid artifacts.
May not be necessary for all applications (e.g., if signals are short or white).

Affine Projection Algorithm (APA)

7. Affine Projection Algorithm (APA)

Affine Projection Algorithm (APA) acts as a bridge between LMS and RLS filters
1. From LMS to APA: The Shift in Focus

LMS filters try to minimize the expected error between the desired output and the
filter output, using a simple update rule based on the latest data sample.
Affine Projection filters, instead of just minimizing the error, minimize how much
the weights change, under the constraint that the filter perfectly predicts not just
the current desired value, but the last P desired values.

Intuition Behind APA (Beyond the Math):

LMS takes one step at a time using only the latest sample.
APA says: “Let me consider a batch of the past P inputs and desired outputs.
What’s the smallest adjustment I can make to my weights so I explain all of them
perfectly?”
If the new data is similar to the old data, APA doesn't waste effort changing
weights unnecessarily—it moves only when new meaningful information arrives.

2. Formulating the Problem Mathematically

The filter collects the last P input vectors into a matrix A and the corresponding P
desired values into a vector d.
The update rule is derived by minimizing the norm of the change in weights (Δw),
subject to the constraint that Aw = [Link]

This is solved using Lagrange multipliers, a standard optimization trick when you
have constraints.

3. The Weight Update Rule

The update boils down to:

T T −1
w n+1 = w n + μA (AA ) en

where:

A : matrix of recent input vectors

en : the error vector between the desired and current predicted outputs over the last
P samples
μ: step size (like LMS), helps control how fast we adapt
The key difference from LMS: we project the error onto a higher-dimensional
subspace (spanned by the last P inputs), hence “affine projection”.
4. Regularization (to prevent problems)

If the matrix AA is not invertible (say, due to correlated inputs), we regularize it by

T

adding a small constant times the identity:

T −1
(AA + ϵI )

This ensures numerical stability.

5. Summary of APA Algorithm Steps

1. Form the input matrix A using last P input vectors.

2. Form the desired output vector d.
3. Compute the error vector e n = d − Aw n .
4. Update weights using the formula above.

6. Advantages and Caveats

APA adapts faster than LMS in environments with colored inputs (i.e., input
signals with correlation).
It becomes LMS when P = 1 .
APA is more computationally expensive because it involves a matrix inverse. A
faster version (Fast APA) reduces this cost.
APA intelligently uses past data, which makes its updates more informed than LMS.