电子科技大学：《现代数字信号处理理论与算法 Modern theory and algorithm of digital signal processing》课程教学资源（课件讲稿）04 LMS Algorithm

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 steepest￾descent 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) !