Patently False Assumption

X k X k and X k - i X k - i , X k X k and d k - i d k - i , and d k d k and d k - i d k - i are statistically independent, i≠0 i 0 . This assumption is obviously false, since X k - 1 X k - 1 is the same as X k X k except for shifting down the vector elements one place and adding one new sample. We make this assumption because otherwise it becomes extremely difficult to analyze the LMS algorithm. (First good analysis not making this assumption: Macchi and Eweda) Many simulations and much practical experience has shown that the results one obtains with analyses based on the patently false assumption above are quite accurate in most situations

With the independence assumption, W k W k (which depends only on previous X k - i X k - i , d k - i d k - i ) is statitically independent of X k X k , and we can simplify E W k T X k X k W k X k X k

Now W k T X k X k W k X k X k is a vector, and

where R=E X k X k T R X k X k is the data correlation matrix.

Putting this back into our equation

Now if W k → ∞ ¯ W k → ∞ converges to a vector of finite magnitude ("convergence in the mean"), what does it converge to?

If W k ¯ W k converges, then as k→∞ k , W k + 1 ¯≈ W k ¯ W k + 1 W k , and W ∞ ¯=I−2μR W ∞ ¯+2μP W ∞ I 2 μ R W ∞ 2 μ P 2μR W ∞ ¯=2μP 2 μ R W ∞ 2 μ P R W ∞ ¯=P R W ∞ P or W opt ¯=R-1P W opt R P the Wiener solution!

So the LMS algorithm, if it converges, gives filter coefficients which on average are the Wiener coefficients! This is, of course, a desirable result.

Linear Algebra Fact

Since RR is positive definite, real, and symmetric, all the eigenvalues are real and positive. Also, we can write RR as Q-1ΛQ Λ Q Q , where ΛΛ is a diagonal matrix with diagonal entries λ i λ i equal to the eigenvalues of RR, and QQ is a unitary matrix with rows equal to the eigenvectors corresponding to the eigenvalues of RR.

Using this fact, V k + 1 =I−2μQ-1ΛQ V k V k + 1 I 2 μ Λ Q Q V k multiplying both sides through on the left by QQ: we get Q V k + 1 ¯=Q−2μΛQ V k ¯=1−2μΛQ V k ¯ Q V k + 1 Q 2 μ Λ Q V k 1 2 μ Λ Q V k Let V ' =QV V ' Q V : V ' k + 1 =1−2μΛ V ' k V ' k + 1 1 2 μ Λ V ' k Note that V ' V ' is simply VV in a rotated coordinate set in ℝm ℝ m , so convergence of V ' V ' implies convergence of VV.

Since 1−2μΛ 1 2 μ Λ is diagonal, all elements of V ' V ' evolve independently of each other. Convergence (stability) bolis down to whether all MM of these scalar, first-order difference equations are stable, and thus →0 → 0 . ∀i,i=12…M: V i ' k + 1 =1−2μ λ i V i ' k i i 1 2 … M V i ' k + 1 1 2 μ λ i V i ' k These equations converge to zero if |1−2μ λ i |<1 1 2 μ λ i 1 , or ∀i:|μ λ i |<1 i μ λ i 1 μμ and λ i λ i are positive, so we require ∀i:μ<1 λ i i μ 1 λ i so for convergence in the mean of the LMS adaptive filter, we require

This is an elegant theoretical result, but in practice, we may not know λ max λ max , it may be time-varying, and we certainly won't want to compute it. However, another useful mathematical fact comes to the rescue... trR=∑i=1M r ii =∑i=1M λ i ≥ λ max tr R i 1 M r ii i 1 M λ i λ max Since the eigenvalues are all positive and real.

For a correlation matrix, ∀i,i∈1M: r ii =r0 i i 1 M r ii r 0 . So trR=Mr0=ME x k x k tr R M r 0 M x k x k . We can easily estimate r0 r 0 with O1 O 1 computations/sample, so in practice we might require μ<1M r0 ̂ μ 1 M r 0 as a conservative bound, and perhaps adapt μμ accordingly with time.