CH4 LMS Algorithm Remarkably simple A simple one line updating algorithm Not more than roughly 2N Multiply-Add per time update May be derived from the RLS algorithm Remarkably complex Convergence/stability analysis
CH4 LMS Algorithm Remarkably simple A simple one line updating algorithm Not more than roughly 2N Multiply-Add per time update May be derived from the RLS algorithm Remarkably complex Convergence/stability analysis
Content o Steepest-descent algorithm o LMS algorithm o LMS for time-varying set-ups o LMS variants o Normalized LMS (NLMS) o LMS versus RLS convergence 2020-01-18 2
2020-01-18 2 Content Steepest-descent algorithm LMS algorithm LMS for time-varying set-ups LMS variants Normalized LMS (NLMS) LMS versus RLS convergence
S1.Steepest-descent algorithm o Update formula o Convergence condition o Transient behavion ●The learning curve WC 2020-01-18
2020-01-18 3 S1. Steepest-descent algorithm Update formula Convergence condition Transient behavior The learning curve
Solving the Wiener-Hopf equations o Solving the Wiener-Hopf equations .Direct method (e.g.,Gauss elimination) Iterative method:Avoid matrix inverse and find optimal solution recursively maw0生2e Jw-w(n) 2020-01-18 4
2020-01-18 4 Solving the Wiener-Hopf equations Solving the Wiener-Hopf equations Direct method (e.g., Gauss elimination) Iterative method: Avoid matrix inverse and find optimal solution recursively ( ) ( ) ( 1) ( ) 2 MSE n J n n w w w w w w
(1)Update formula JuSE(w)=od+w"RW-wRd-Rw Jssw）=2Rmw-2Rd Ow w(n+1)=w(n)+u(Rd-RmW(n)) 2020-01-18 5
2020-01-18 5 (1) Update formula ( ) 2 2 MSE uu ud J w R w R w 2 ( ) H H H MSE d uu ud ud J w w R w w R R w w w R R w ( 1) ( ) ( ) n n n ud uu
u:step-size o How far one moves in the steepest- descent direction. Moving too far in that direction might actually overshoot the minimum and result in instability. o Bounds on u w(n+1)-wgp=w(n）-Wp+A(RuWp-Rmw(n)） =(I-jiR,)(w(n)-wop) =(I-Rm)'(w(O)-w） 2020-01-18 6
2020-01-18 6 μ: step-size How far one moves in the steepestdescent direction. Moving too far in that direction might actually overshoot the minimum and result in instability. Bounds on μ 1 ( 1) ( ) ( ) ( ) (0) opt opt uu opt uu uu opt n uu opt n n n n w w w w R w R w I R w w I R w w
(2)Convergence condition (I-uR)=(I-MQAQ") =Q(1-A)Q1 > 0 -以1 0<4< The weight error reduce in each step! 2020-01-18 7
2020-01-18 7 (2) Convergence condition 1 1 1 n n H uu n H I R I QΛQ Q I Λ Q 0 1 1 k max 2 0 The weight error reduce in each step!
Conservative choice 2 0<4< 2 2 k=1 2 2 2 0<U<M tr(R)Mo2 k=1 2020-01-18 8
2020-01-18 8 Conservative choice max 2 0 max 1 2 2 M k k 2 u 1 2 2 2 0 tr( ) M uu k k M R
(3)Transient behavior(1) o the weight vectors Q(w(n+1)-wop)=(I-jiA)""Q"(w(O)-wop) The smallest eigenvalue of the correlation matrix defines the slowest decay,corresponding to (1-以n)m1 ill-conditioned:Amax>>Amin. The large入max then results in a smallμso that 1-UAmin≈1. 2020-01-18 9
2020-01-18 9 (3) Transient behavior (1) the weight vectors The smallest eigenvalue of the correlation matrix defines the slowest decay, corresponding to ill-conditioned: λmax>>λmin. The large λmax then results in a small μ so that 1−μλmin ≈ 1. 1 ( 1) (0) n H opt opt n Q w w I Λ Q w w 1 min 1 n
Optimal choice for convergence 2 u= nax+入nim 冬以 nx一人nmm Whenever Amax >Amin convergence is going to be very slow (u will be small and hence many iterations will be required)! 2020-01-18 10
2020-01-18 10 Optimal choice for convergence max m 2 im max m max m max m max m 1 im im k im im Whenever λmax >> λmin , convergence is going to be very slow (μ will be small and hence many iterations will be required) !