李霄劍 王 永 陳紹青 付志浩

?

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

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

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

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

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

1 引言

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

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

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

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

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

圖1 LMS算法結構圖

LMS算法權值更新向量為

LMS更新公式為

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

為了更加準確地對最速下降方向進行估計，BLMS算法被提出，更新向量為

其中，為分塊長度。

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

2.2 LMS單步更新方向與更新向量的關系

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

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

證畢

圖2 2維LMS球示意圖

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

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

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

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

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

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

3.1 算法結構

DOLMS算法結構與分塊LMS算法類似，其結構如圖3所示。

圖3 DOLMS算法結構圖

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

則更新向量為

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

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

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

3.2 算法流程

DOLMS的算法流程如下：

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

3.3 算法特性理論分析

下面對于DOLMS的特點及其原因進行分析。

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

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

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

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

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

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

表1算法復雜度比較

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

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

4 算法比較與仿真

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

4.1 算法特性分析

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

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

4.2 算法仿真比較

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

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

對于輸入信號為有色信號的LMS自適應算法而言，以最速下降方向為收斂方向往往會導致自適應濾波器權值在接近最優(yōu)值時收斂速率會不斷減慢；這種特性在輸入信號為正弦信號時極為明顯?；谶@種現象，設計出了模型2，將上述3種變步長LMS算法應用于模型2，進行仿真實驗，結果如圖8所示。

圖4 塊長度對DOLMS的影響

圖5 步長因子對DOLMS的影響

圖6 定步長算法比較圖

圖7 變步長算法比較圖

圖8 濾波器系數學習曲線

5 結束語

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

[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]. 電子與信息學報, 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]. 通信技術, 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自適應算法[J]. 西南科技大學學報, 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] 曲慶, 金堅, 谷源濤. 用于稀疏系統(tǒng)辨識的改進0-LMS算法[J]. 電子與信息學報, 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年生，碩士生，研究方向為自適應濾波、振動主動控制.

王 永： 男，1962年生，教授，博士生導師，研究方向為振動主動控制、飛行器制導與控制等.

陳紹青： 男，1985年生，博士，研究方向為自適應濾波、振動主動控制等.

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計劃項目(2011AA7034056C)資助課題