李霄劍 王 永 陳紹青 付志浩

?

一種方向優(yōu)化最小均方算法

李霄劍 王 永*陳紹青 付志浩

(中國科學(xué)與技術(shù)大學(xué)自動化系 合肥 230027)

最小均方(Least Mean Square, LMS)算法的更新方向是對最速下降方向的估計(jì)，其收斂速度也受到最速下降法的約束。為了擺脫該約束，該文在對LMS算法分析的基礎(chǔ)上，提出一種針對LMS算法的分塊方向優(yōu)化方法。該方法通過分析誤差信號來選擇更新向量，使得算法的更新方向盡可能接近Newton方向?；诖朔椒?，給出一種方向優(yōu)化LMS(Direction Optimization LMS, DOLMS)算法，并推廣到變步長DOLMS算法。理論分析與仿真結(jié)果表明，該方法與傳統(tǒng)分塊LMS算法相比，有更快的收斂速度和更小的計(jì)算復(fù)雜度。

自適應(yīng)濾波；最小均方算法；方向優(yōu)化；最小均方球；方向優(yōu)化最小均方算法

1 引言

為了優(yōu)化算法的收斂路徑，人們提出了以Newton方向?yàn)樗惴ü烙?jì)方向的LMS-Newton算法[15,16]。對于基本FIR(Finite Impulse Response)濾波器而言，自適應(yīng)算法的梯度函數(shù)為二階函數(shù)，此時Newton方向就是一步最優(yōu)方向(由當(dāng)前濾波器參數(shù)直接指向最優(yōu)濾波器參數(shù)的向量方向)。LMS- Newton算法具有較快的收斂速度，但同時因算法更新時含有矩陣求逆運(yùn)算，具有算法計(jì)算量大、結(jié)構(gòu)復(fù)雜等缺點(diǎn)。

本文分析了LMS收斂原理，提出了新的LMS分塊計(jì)算方法。新方法選擇數(shù)據(jù)塊中最接近Newton方向的更新向量進(jìn)行更新，無論是收斂速度還是計(jì)算量都遠(yuǎn)優(yōu)于BLMS的分塊方法。基于此方法提出了一種方向優(yōu)化LMS(Direction Optimization LMS, DOLMS)算法及其相應(yīng)的變步長算法。DOLMS算法不受最速下降法自身收斂速度的限制，能夠更快地收斂到最優(yōu)點(diǎn)。該算法更新向量的計(jì)算公式形式與NLMS完全相同，因此適用于NLMS的變步長優(yōu)化方法對該算法同樣適用。DOLMS算法只是選擇其中一個更新向量進(jìn)行算法更新，省去了求取平均值的過程，因此算法復(fù)雜度較BLMS算法而言有了極大的簡化。通過仿真分析了DOLMS算法的特性，而后與其它算法進(jìn)行了比較，仿真結(jié)果說明該算法對變步長LMS算法能起到同樣的優(yōu)化作用。

2 LMS算法及其收斂特性分析

2.1 LMS算法及分塊LMS算法簡介

LMS算法是一種隨機(jī)梯度算法。它以系統(tǒng)均方誤差為代價函數(shù)，利用隨機(jī)估計(jì)值代替最速下降法中的梯度向量，在統(tǒng)計(jì)意義上以最速下降方向收斂到Wiener解。算法結(jié)構(gòu)如圖1所示。

圖1 LMS算法結(jié)構(gòu)圖

LMS算法權(quán)值更新向量為

LMS更新公式為

為了優(yōu)化算法步長，NLMS算法被提出，更新向量為

為了更加準(zhǔn)確地對最速下降方向進(jìn)行估計(jì)，BLMS算法被提出，更新向量為

其中，為分塊長度。

BLMS算法的基本思想是通過增加樣本數(shù)使得對最速下降方向的估計(jì)更加準(zhǔn)確，因此增加分塊長度只能增加估計(jì)的準(zhǔn)確性，其收斂速度受最速下降法約束不會有明顯加快。

2.2 LMS單步更新方向與更新向量的關(guān)系

證明 LMS自適應(yīng)濾波器的系統(tǒng)估計(jì)誤差可寫為

將式(7)代入式(2)可得

證畢

圖2 2維LMS球示意圖

2.3 分塊歸一化LMS算法的方向優(yōu)化

將每一組數(shù)據(jù)代入式(4)，可以計(jì)算得出與之對應(yīng)的歸一化更新向量為

其中，等式左邊為系統(tǒng)的歸一化誤差，式(13)還可寫成

顯然，定理2具有遞推性，因此很容易得到如下推論：

3 方向優(yōu)化LMS(DOLMS)算法設(shè)計(jì)

上述分析為比較LMS算法的更新方向提供了依據(jù)，也提供了一種新的LMS分塊計(jì)算的方法。與BLMS不同，新方法是通過選取塊中最優(yōu)的更新向量進(jìn)行更新，因此擺脫了最速下降法收斂速度的約束，具有更快的收斂速度。

3.1 算法結(jié)構(gòu)

DOLMS算法結(jié)構(gòu)與分塊LMS算法類似，其結(jié)構(gòu)如圖3所示。

圖3 DOLMS算法結(jié)構(gòu)圖

根據(jù)定理2推論選取更新所需的誤差和輸入向量：

則更新向量為

算法步長因子的取值范圍與歸一化LMS算法相同。

最優(yōu)步長參數(shù)[1,4]為

為了保證系統(tǒng)穩(wěn)態(tài)誤差，算法還可以采用文獻(xiàn)[8]所提出的變步長方法，形成變步長DOLMS算法。變步長為

3.2 算法流程

DOLMS的算法流程如下：

步驟4 計(jì)數(shù)器加1，判斷是否等于：如不等，則跳轉(zhuǎn)至步驟3；反之，繼續(xù)。

3.3 算法特性理論分析

下面對于DOLMS的特點(diǎn)及其原因進(jìn)行分析。

(2)塊長度與收斂速度的關(guān)系 DOLMS雖然分塊進(jìn)行計(jì)算，但與BLMS算法相比，其分塊的目的并不相同。對于一般分塊LMS算法，分塊是為了更加準(zhǔn)確地估計(jì)最速下降方向，增加塊長度只能使最速下降方向估計(jì)更為準(zhǔn)確，其收斂速度受更新方向約束不會加快。然而DOLMS算法進(jìn)行分塊是為了尋找更加接近一步最優(yōu)方向的更新向量。對于輸入為周期信號[17]而言，當(dāng)塊長度等于信號周期，此時DOLMS算法的收斂速度達(dá)到最大，增加塊長度對算法收斂速度不會有影響。而對于非周期信號而言，隨著塊長度的增加，其最終選取的更新方向會更為接近一步最優(yōu)方向，收斂速度也會越快，此時算法存在通過一步更新達(dá)到最優(yōu)值的可能性。

(3)穩(wěn)態(tài)誤差 由于該算法取歸一化誤差平方值最大項(xiàng)進(jìn)行更新，故當(dāng)系統(tǒng)輸出誤差信號存在測量噪聲時，此種更新方法會放大噪聲對系統(tǒng)更新的影響。特別是在最優(yōu)點(diǎn)附近，此時輸出誤差信號的信噪比低，歸一化誤差的大小更多取決于測量誤差而非更新方向，因此DOLMS算法的穩(wěn)態(tài)誤差會略大于相同變步長的NLMS算法。

(4)算法復(fù)雜度 此處為了展現(xiàn)DOLMS算法復(fù)雜度，將其與分塊歸一化LMS算法、BLMS算法進(jìn)行比較。

首先考察DOLMS算法復(fù)雜度。算法步驟3需要在每個采樣周期計(jì)算歸一化誤差平方，故計(jì)算歸一化誤差的復(fù)雜度為+2。比較歸一化誤差平方時，不需要進(jìn)行乘法運(yùn)算，復(fù)雜度為0。算法步驟5在每一塊只需進(jìn)行一次更新向量的運(yùn)算，如式(17)，其中向量模長平方已經(jīng)在歸一化誤差計(jì)算中求得；故更新向量計(jì)算復(fù)雜度為+2。一個分塊周期內(nèi)算法總體復(fù)雜度為：(+2)++2=(+1)(+2)。

需要注意的是， DOLMS算法計(jì)算量主要用于計(jì)算輸入向量模長平方。該計(jì)算可以通過記錄每次輸入值平方進(jìn)行簡化計(jì)算，這樣每次計(jì)算輸入向量模長平方只需計(jì)算最新的輸入值平方，再與之前記錄數(shù)據(jù)求和即可。因此步驟3的計(jì)算復(fù)雜度可以簡化為3。DOLMS算法的整體復(fù)雜度就能得到了極大的簡化，在一個分塊周期內(nèi)的計(jì)算復(fù)雜度為3++2。

DOLMS與其它算法的復(fù)雜度比較如表1所示。

表1算法復(fù)雜度比較

算法名稱DOLMSDOLMS(簡)分塊歸一化LMSBLMS 復(fù)雜度(L+1)3L+M+2L(2M+1)+M+1(L+1)M+1

從表1可以看出，DOLMS算法的復(fù)雜度低于分塊歸一化LMS算法，略高于BLMS算法。而簡化后的DOLMS算法復(fù)雜度則遠(yuǎn)小于另外兩種算法。

4 算法比較與仿真

為了驗(yàn)證DOLMS算法的有效性，下面對算法進(jìn)行仿真，并與歸一化塊LMS算法[18]，BLMS算法[8]進(jìn)行比較。仿真將采用以下兩種系統(tǒng)模型。

4.1 算法特性分析

DOLMS算法隨著塊長度的增加，所選取的更新方向會更為接近一步最優(yōu)方向，收斂速度會隨著塊長度的增加而變快。分別以=5,=50,=250作為塊長度，利用DOLMS對模型1進(jìn)行仿真試驗(yàn)，統(tǒng)一選取步長因子為=1。重復(fù)試驗(yàn)25次，取塊平均誤差均值的對數(shù)作為縱坐標(biāo)，以更新次數(shù)作為橫坐標(biāo)，如圖4所示。由圖4可以看出，塊長度越長其更新速度越快，但同時穩(wěn)態(tài)誤差也會隨之變大。

同時與大多數(shù)LMS算法相同，在塊長度不變的情況下，步長因子越小，收斂速度越慢但穩(wěn)態(tài)誤差會變小。選取=10作為塊長度，分別以=1.0,= 0.5,=0.1作為步長因子，利用方向優(yōu)化LMS對模型1進(jìn)行仿真試驗(yàn)，其結(jié)果如圖5所示。由圖5可以看出，隨著步長因子的增加，算法的穩(wěn)態(tài)誤差隨之增大，而收斂速度也隨之提高。

4.2 算法仿真比較

統(tǒng)一選取算法步長為10，分別利用方向優(yōu)化LMS，分塊歸一化LMS, BLMS對模型1進(jìn)行仿真試驗(yàn)。其中方向優(yōu)化LMS，分塊歸一化LMS的步長為1.00; BLMS算法步長因子取0.09時，算法收斂不平穩(wěn)會出現(xiàn)大量尖峰，因此選取0.08作為BLMS算法最優(yōu)步長進(jìn)行比較。所得結(jié)果如圖6所示。由圖6可以看出DOLMS的收斂速度快于分塊NLMS算法和BLMS算法，但其穩(wěn)態(tài)誤差有明顯增大。

通過上述比較可知，DOLMS算法的收斂速度明顯快于分塊歸一化LMS算法和BLMS算法，其穩(wěn)態(tài)誤差經(jīng)過變步長優(yōu)化后與同樣經(jīng)過變步長優(yōu)化后的分塊NLMS和BLMS基本相同。由此可看出，對于當(dāng)前存在大量的變步長LMS算法，DOLMS算法可直接對其進(jìn)行再次優(yōu)化。優(yōu)化后的變步長DOLMS的收斂速度較之原變步長LMS算法而言，其收斂速度有較大提升同時穩(wěn)態(tài)誤差有輕微的增大。

對于輸入信號為有色信號的LMS自適應(yīng)算法而言，以最速下降方向?yàn)槭諗糠较蛲鶗?dǎo)致自適應(yīng)濾波器權(quán)值在接近最優(yōu)值時收斂速率會不斷減慢；這種特性在輸入信號為正弦信號時極為明顯。基于這種現(xiàn)象，設(shè)計(jì)出了模型2，將上述3種變步長LMS算法應(yīng)用于模型2，進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖8所示。

圖4 塊長度對DOLMS的影響

圖5 步長因子對DOLMS的影響

圖6 定步長算法比較圖

圖7 變步長算法比較圖

圖8 濾波器系數(shù)學(xué)習(xí)曲線

5 結(jié)束語

當(dāng)LMS算法及其改進(jìn)算法以有色信號作為輸入時，其收斂方向?yàn)閷ψ钏傧陆捣较虻墓烙?jì)這一特性，不僅限制了算法步長的選擇，同時也限制了算法的收斂速度。本文提出了一種針對分塊LMS算法的方向優(yōu)化方法，并給出了該方法的理論依據(jù)。該方法通過分析誤差信號選擇最接近一步最優(yōu)方向的更新向量進(jìn)行算法更新，擺脫了最速下降法的約束。以此方法為基礎(chǔ)提出了DOLMS算法，將DOLMS算法與分塊NLMS, BLMS算法進(jìn)行了比較。比較結(jié)果表明，DOLMS算法有更快的收斂速度和更小的計(jì)算復(fù)雜度。且DOLMS算法可以與LMS算法的變步長方法同時使用，在保證收斂速度的基礎(chǔ)上優(yōu)化穩(wěn)態(tài)誤差。同時，算法塊長度越長收斂速度越快的特點(diǎn)適用于自適應(yīng)濾波器系數(shù)不方便頻繁變動的情況，使得每次更新更加有效。

[1] Hayin S. Adaptive Filter Theory[M]. 北京: 電子工業(yè)出版社, 2003: 70-267.

[2] Butterweck H J. Steady-state analysis of the long LMS adaptive filter[J]., 2011, 91(4): 690-701.

[3] Duttweiler D L. Proportionate normalized least-mean- squares adaptation in echo cancelers[J]., 2000, 8(5): 508-518.

[4] 曾召華, 劉貴忠, 趙建平. LMS和歸一化LMS算法收斂門限與步長的確定[J]. 電子與信息學(xué)報(bào), 2003, 25(11): 1469-1474.

Zeng Zhao-hua, Liu Gui-zhong, and Zhao Jian-ping. Determining of convergent threshold and step-size for LMS and normalized LMS algorithm[J]., 2003, 25(11): 1469-1474.

[5] Borisagar K R, Sedani B S, and Kulkarni G R. Simulation and performance analysis of LMS and NLMS adaptive filters in non-stationary noisy environment[C]. International Conference on Computational Intelligence and Communication Systems, Gwalior, 2011:682-686.

[6] Feuer A. Performance analysis of the block least mean square algorithm[J]., 1985, CAS-32(9): 960-963.

[7] 呂春英, 敖偉, 張洪順. 一種新的變步長LMS算法[J]. 通信技術(shù), 2011, 44(3): 11-14.

Lü Chun-ying, Ao Wei, and Zhang Hong-shun. A new variable step-size LMS algorithm[J]., 2011, 44(3): 11-14.

[8] 肖海英, 何方白. 一種時域變步長BLMS自適應(yīng)算法[J]. 西南科技大學(xué)學(xué)報(bào), 2006, 21(2): 30-35.

Xiao Hai-ying and He Fang-bai. A variable step size BLMS adaptive algorithm in time domain[J]., 2006, 21(2): 30-35.

[9] 曲慶, 金堅(jiān), 谷源濤. 用于稀疏系統(tǒng)辨識的改進(jìn)0-LMS算法[J]. 電子與信息學(xué)報(bào), 2011, 33(3): 604-609.

Qu Qing, Jin Jian, and Gu Yuan-tao. An improved0-LMS algorithm for sparse system identification[J]., 2011, 33(3): 604-609.

[10] Bismor D. LMS algorithm step size adjustment for fast convergence[J]., 2012, 37(1): 31-40.

[11] Mayyas K. A variable step-size selective partial update LMS algorithm[J]., 2013, 23(1): 75-85.

[12] Cai Wei-ju. A new variable step size LMS adaptive filtering algorithm and its analysis[J]., 2013, 605(2013): 2193-2196.

[13] Ao Wei, Xiang Wan-qin, Zhang You-peng,. A new variable step size LMS adaptive filtering algorithm[C]. International Conference on Computer Science and Electronics Engineering ICCSEE, Hangzhou, 2012, 2: 265-268.

[14] Mayyas K and Momani F. An LMS adaptive algorithm with a new step-size control equation[J]., 2011, 348(4):589-605.

[15] Diniz P S R, de Campos M L R, and Antoniou A. Analysis of LMS-Newton adaptive filtering algorithms with variable convergence factor[J]., 1995, 43(3): 617-627.

[16] Lian Rui-mei. An improved LMS-Newton algorithm and its analysis[C]. International Conference on Mechanical and Electronics Engineering,Hefei, 2011: 458-462.

[17] Parra I E, Hernandez W, and Fernandez E. On the convergence of LMS filters under periodic signals[J].:, 2013, 23(3):808-816.

[18] 魏璀璨, 王永, 陳紹青, 等. 磁懸浮隔振器分塊歸一化LMS算法控制研究[J]. 振動與沖擊, 2012, 31(18): 100-103.

Wei Cui-can, Wang Yong, Chen Shao-qing,. Control of an electromagnetic suspension vibration isolator based on block normalized LMS algorithm[J]., 2012, 31(18): 100-103.

李霄劍： 男，1990年生，碩士生，研究方向?yàn)樽赃m應(yīng)濾波、振動主動控制.

王 永： 男，1962年生，教授，博士生導(dǎo)師，研究方向?yàn)檎駝又鲃涌刂?、飛行器制導(dǎo)與控制等.

陳紹青： 男，1985年生，博士，研究方向?yàn)樽赃m應(yīng)濾波、振動主動控制等.

A Direction Optimization Least Mean Square Algorithm

Li Xiao-jian Wang Yong Chen Shao-qing Fu Zhi-hao

(,,230027,)

The update vector of Least Mean Square (LMS) algorithm is an estimation of the gradient vector, thus its convergence rate is limited by the method of steepest descent. Based on the discussion of basic LMS, a direction optimization method of LMS algorithm is proposed in order to get rid of this speed constraint. In the proposed method, the closest update vector to the Newton direction is chosen based on the analysis of the error signal. Based on the method, a Direction Optimization LMS (DOLMS) algorithm is proposed,and it is extended to the variable step-size DOLMS algorithm.The theoretical analysis and the simulation results show that the proposed method has higher speed of convergence and less computational complexity than traditional block LMS algorithm.

Adaptive filter; Least Mean Square (LMS) algorithm; Direction optimization; Least Mean Square (LMS) ball; Direction Optimization Least Mean Square (DOLMS) algorithm

TN911.72

A

1009-5896(2014)06-1348-07

10.3724/SP.J.1146.2013.01038

王永 yongwang@ustc.edu.cn

2013-07-16收到，2014-01-17改回

國家863計(jì)劃項(xiàng)目(2011AA7034056C)資助課題