一種改進的批處理常模算法?

潘子宇，酆廣增，孔媛媛（.南京工程學(xué)院通信工程學(xué)院，南京67；.南京郵電大學(xué)通信與信息工程學(xué)院，南京0003）

一種改進的批處理常模算法?

潘子宇1，酆廣增2，孔媛媛2
（1.南京工程學(xué)院通信工程學(xué)院，南京211167；2.南京郵電大學(xué)通信與信息工程學(xué)院，南京210003）

分析了傳統(tǒng)批處理常模算法的缺點，提出了一種新的批處理常模算法——基于共軛梯度方向的批處理常模算法（CG-BPCMA）。新算法采用共軛梯度方向作為下降方向，推導(dǎo)出共軛梯度方向的解析形式。在平坦瑞利衰落信道環(huán)境下的MIMO盲均衡系統(tǒng)中的仿真結(jié)果表明，新算法有效地克服了SD-BPCMA和NT-BPCMA的缺點，不僅獲得了較低的算法復(fù)雜度，而且能快速收斂到常模代價函數(shù)的最小值點。

MIMO；盲均衡系統(tǒng)；批處理算法；常模算法；共軛梯度

1 引言

常模（CM）算法在盲信道估計、盲多用戶檢測、盲信源分離等領(lǐng)域有廣泛的應(yīng)用［1］。一般而言，常模算法基于最陡下降算法，算法簡單且具有全局收斂性，但收斂速度很慢，從而限制了其在信號處理中的應(yīng)用。

文獻［2］提出了一種最優(yōu)化方法——批處理常模算法（BPCMA）。作為一種線性搜索迭代算法，BPCMA包含三方面因素，即搜索方向、步長和初始值?；谂ｎD方向的BPCMA（NT-BPCMA）有效克服了傳統(tǒng)最陡下降算法（SD-BPCMA）收斂慢的缺點，實現(xiàn)了算法的快速收斂，經(jīng)幾步迭代即可收斂到極小值點。然而，牛頓法具有以下幾點缺陷［3］：第一，牛頓法并不是全局收斂的；第二，由于信號和信道的隨機性，代價函數(shù)J（g）的Hessian矩陣▽2J（g）有時候是奇異或病態(tài)的。在這種情況下，下降方向?qū)o法確定；第三，牛頓法收斂于鞍點或極大值點的可能性并不小于最小值點；第四，牛頓法需要進行矩陣求逆運算，而這是最優(yōu)化方法力求避免的問題。

綜合考慮到最陡下降法和牛頓法的各種利弊，本文提出了基于共軛梯度法的批處理常模算法，稱之為CG-BPCMA。本文研究了新算法的收斂性和復(fù)雜度，與SD-BPCMA和NT-BPCMA作了仿真比較。結(jié)果表明，本文提出的算法有效地兼顧了算法復(fù)雜度、收斂性兩方面的矛盾，取得了較好的均衡效果。

2 信號模型和常模估計器

考慮如下的信號模型，其接收信號為

其中，s（n）=［s1（n），…，sK（n）］T是K維的發(fā)送信號，每根發(fā)送天線發(fā)送相同的信號；y（n）是P維的經(jīng)過信道后的接收天線的接收信號；hk是長度為P的信道矢量；H=［h1，…，hK］則是P×K信道矩陣；w（n）是加性噪聲分量。系統(tǒng)模型如圖1所示。

為了討論問題方便起見，我們對信道模型做如下假設(shè)。

（1）sk（n）是零均值非高斯的信號，

若sk（n）為復(fù)變量，則E｛sk（n=0，說明發(fā)送信號為均勻?qū)ΨQ。

（3）信道轉(zhuǎn)移矩陣H是滿秩矩陣。

其中，J（g）=E｛（｜z（n）｜2-γ）2｝為常模代價函數(shù)，γ為輸出信號的期望模值。

3 CG-BPCMA算法

本節(jié)將給出我們提出的線性搜索批處理常模算法的算法原理。我們知道，線性搜索算法首先確定一個搜索方向，繼而以降低代價函數(shù)值為目標(biāo)由本次迭代走向下一步迭代［4］。迭代過程的數(shù)學(xué)表達式如下：

式中，正參數(shù)μ為迭代步長。為了討論問題簡便，本文采用定步長的方法。因此，我們僅需要討論其余兩點因素——搜索方向和初始權(quán)值。

3.1 搜索方向

本文中我們將采用共軛梯度方向代替牛頓方向進行迭代。共軛梯度法是共軛方向法的一種，共軛方向法可表示如下［5］：

其中，▽iJ為常模代價函數(shù)的梯度，βi-1為修正系數(shù)且由下式確定：

在式（5）中，G是代價函數(shù)J的Hessian矩陣。在每一步迭代時計算G是比較麻煩的，因此我們必須尋求βi-1不顯含G的表達形式。

注意到

由于式（6）中βi-1完全由代價函數(shù)的梯度▽J確定，我們稱之為共軛梯度法。若βi-1=0，共軛梯度法便退化為最陡下降法（SD-BPCMA），牛頓法（NTBPCMA）的下降方向為pi=-G-1i▽J（gi）。

3.2 初始權(quán)值

文獻［6］指出，常模估計器的權(quán)值在由信道轉(zhuǎn)移矩陣H的列向量張成的信號子空間中。因此，我們可以從信號子空間中提取初始權(quán)值g1。信號子空間可以由接收信號的自相關(guān)矩陣做特征值分解（ED）得到［7］：

假設(shè)ps為一P×K矩陣，其列向量張成信號子空間，初始權(quán)值可以簡單取為其中的任意一列g(shù)1= ps，k，k=1，…，K。文獻［2］將矩陣ps的列向量做一線性組合，從而作為初始權(quán)值，即?gk=x1ps，1+x2ps，2+…+xkps，k，其中組合系數(shù)xk由下式確定：

求解式（7）中xk的常規(guī)方法是做線性搜索。然而，我們注意到代價函數(shù)φ（x）=J（?gk-1+x ps，k）是一個四次多項式：

由于期望運算和求導(dǎo)運算可以交換次序，其一階導(dǎo)函數(shù)為

令φ′（x）=0，我們得到一個三次方程。一般而言，求解三次方程需要用數(shù)值分析的方法求解。本文中，我們采用一個比較簡單的方法求解x。上述三次方程可轉(zhuǎn)化為如下形式：

［（g+x p）Ty］3·（pTy）=［（g+x p）Ty］·（pTy）（10）注意，方程（10）是方程φ′（x）=0的充分條件而非充分必要條件。注意到（g+x p）Ty和pTy均為非零值，則方程的解為

最終的組合系數(shù)x由下式確定：

迭代到第K步時得到?gK=x1ps，1+x2ps，2+…+xKps，K，這就是我們要確定的初始權(quán)值g1。

因此，CG-BPCMA的算法步驟如下：

Step 1：初始化g1、μ，令i=1；

Step 2：計算▽iJ=▽J（gi）；

4 算法復(fù)雜度

由于本文算法選取初始權(quán)值的方法和文獻［2］相似，復(fù)雜度相當(dāng)，我們只需比較選取搜索方向部分的算法復(fù)雜度。在共軛梯度算法中，乘法運算的計算量為K2（K為權(quán)向量g的維數(shù)），其余計算量（如加法運算）均為K的線性函數(shù)，因此整個算法的時間復(fù)雜度為O（K2）。在牛頓法中，乘法運算的計算量為1／6K3+O（K2），其余運算量同樣為K的線性函數(shù)，因此整個算法的時間復(fù)雜度為O（K3）。相比之下，本文算法使得算法的時間復(fù)雜度降低了一個數(shù)量級。

5 算法仿真

本節(jié)中，我們用數(shù)值仿真的手段對新算法的收斂性能做進一步分析?？紤]圖1所示的系統(tǒng)模型，信源個數(shù)K=8，接收天線數(shù)P=10，信道采用平坦瑞利衰落信道，且在一幀數(shù)據(jù)內(nèi)不變化，發(fā)送信號為QPSK信號，一幀數(shù)據(jù)長N=500，發(fā)送信噪比為SNR=20 dB，步長μ=10-8。采用均方誤差（MSE）作為衡量算法收斂性能的指標(biāo)，仿真結(jié)果如圖2～3所示?？紤]信號和信道的隨機性，本文采用50次獨立運行的平均。

圖2 是CG-BPCMA和SD-BPCMA、NT-BPCMA的MSE性能比較圖。從圖中可以看出NT-BPCMA出現(xiàn)了發(fā)散現(xiàn)象，不能收斂到極小值點，這是由于信道的隨機選取導(dǎo)致了G-1可能無法計算。若G-1能夠計算，算法向收斂方向迭代；反之，算法將走向發(fā)散（在這50次獨立運行的過程中，NT-BPCMA算法出現(xiàn)了43次發(fā)散，僅有7次是收斂的），這是圖2中牛頓法曲線怪異的根本原因。但是，我們提出的CG-BPCMA則很好地避免了這一問題。從圖2中還可以看出，CG-BPCMA的收斂速度明顯高于SD-BPCMA。此外，在仿真過程中，我們還發(fā)現(xiàn)，一旦步長因子μ≥10-6，算法將走向發(fā)散。

圖3是CG-BPCMA的MSE性能圖，兩條曲線分別對應(yīng)初始權(quán)值隨機選取和由子空間分解法得出。從圖中可以明顯看出，和隨機選取初始權(quán)值的方法相比，利用子空間分解計算初始權(quán)值的方法使得算法收斂速度和穩(wěn)態(tài)性能大大提高。

6 結(jié)論

本文分析了傳統(tǒng)批處理常模算法的優(yōu)缺點，針對最陡下降法收斂慢以及牛頓法不能準確收斂的問題，提出了一種基于共軛梯度法的新的批處理常模算法（CG-BPCMA），并將其和傳統(tǒng)批處理常模算法做了仿真比較。結(jié)果表明，本文提出的新算法不僅能克服傳統(tǒng)算法的缺點，且復(fù)雜度低，收斂速度較快。因此，CG-BPCMA有效地兼顧了收斂速度和復(fù)雜度之間的矛盾。此外，利用子空間分解計算初始權(quán)值的方法能夠大大提高算法的收斂速度，使得算法收斂“贏在起點上”，但子空間分解也需要消耗相當(dāng)一部分計算資源，從算法整體收斂所需的CPU絕對時間上看，該方法不比隨機選取初始值節(jié)省時間。如何進一步降低子空間分解的算法復(fù)雜度、實現(xiàn)快速分解將是本批處理常模算法進一步研究的方向之一。

［1］Abrar S，Nandi A K.An Adaptive ConstantModulus Blind E-qualization AlgorithMand Its Stochastic Stability Analysis［J］. IEEE Signal Processing Letters，2010，17（1）：55-58.

［2］Xu Changjiang，Li Jian.A Batch processing ConstantModulus Algorithm［J］.IEEE Communications Letters，2004，8（9）：582-584.

［3］Argyros IK.Newton Method on Lie Groups［J］.Journal of Applied Mathematics and Computing，2009，31（1-2）：217-228.

［4］Wang Jian，WuWei，Zurada JM.Deterministic Convergence of Conjugate Gradient Method for Feedforward Neural Networks［J］.Neurocomputing，2011，74（14）：2368-2376.

［5］Dietl G，Botsch M，Dietrich F A，et al.Robust and reducedrankmatrixWiener filter based on the conjugate gradient algorithm［C］／／Proceedings of 2005 IEEE 6th Workshop on Signal Processing Advances in Wireless Communications.NeWYork：IEEE，2005：555-559.

［6］代松銀，袁嗣杰，董書攀.基于子空間分解的信道階數(shù)估計算法［J］.電子學(xué)報，2010，38（6）：1245-1248. DAISong-yin，YUAN Si-jie，DONG Shu-pan.Effective Channel Order Estimation Based on Subspace Decomposition［J］.Acta Electronic Sinica，2010，38（6）：1245-1248.（in Chinese）

［7］Dong Enqing，Zhu Caihua，Evans L.Blind Multiuser Detector Based on Reduced Rank Subspace and Least Square Constant Modulus Algorithm［C］／／Proceedings of the 8th International Conference on Signal Processing.Beijing：IEEE，2006：1-7.

PAN Zi-yu was born in Jiangyan，Jiangsu Province，in 1984. He received the M.S.degree froMNanjing University of Posts and Telecommunications in 2008.He is noWa lecturer.His research concernsmobile communications and communication signal processing，information processing technology.

Email：panziyu＠sohu.com，panziyu＠njit.edu.cn

酆廣增（1943—），男，江蘇無錫人，教授、博士生導(dǎo)師，主要研究方向為數(shù)字移動通信與通信信號處理；

FENG Guang-zeng was born in Wuxi，Jiangsu Province，in 1943.He is noWa professor and also the Ph.D.supervisor.His research concerns digital mobile communications and communication signal processing.

Email：gzfeng＠njupt.edu.cn

孔媛媛（1982—），女，山東煙臺人，講師，主要研究方向為移動通信與通信信號處理。

KONG Yuan-yuan was born in Yantai，Shandong Province，in 1982.She is noWa lecturer.Her research concerns digitalmobile communications and communication signal processing.

Email：yyk＠njupt.edu.cn

A Modified Batch Processing Constant Modulus Algorithm

PAN Zi-yu1，F(xiàn)ENGGuang-zeng2，KONG Yuan-yuan2
（1.Communication Engineering Institute，Nanjing Institute of Technology，Nanjing 211167，China；2.Communication and Information Engineering Institute，Nanjing University of Posts＆Telecommunications，Nanjing 210003，China）

By analysing the shortages of traditional batch processing algorithm，a neWbatch processing constant modulus algorithMderived by conjugate gradientdirection tominimizing the constantmodulus criterion（CG-BPCMA）is presented.The neWalgorithMuses conjugate gradient direction to choose the search direction and the analytical forMof conjugate gradient direction is deduced.Simulation results shoWthat in flat Rayleigh fading synchronous channelenvironmentblind equalization system，the neWalgorithMovercomes the shortcomings of SDBPCMA and NT-BPCMA effectively，not only has lower complexity，but also can converge to theminima of the constantmodulus criterion quickly.

MIMO；blind equalization system；batch processing algorithm；constantmodulus；conjugate gradient

Youth Fund of Nanjing Institute of Technology（QKJB2010009）

TN911

A

10.3969／j.issn.1001-893x.2012.11.013

潘子宇（1984—），男，江蘇姜堰人，2008年于南京郵電大學(xué)獲工學(xué)碩士學(xué)位，現(xiàn)為講師，主要研究方向為移動通信與通信信號處理、信息處理技術(shù)等；

1001-893X（2012）11-1774-04

2012-03-27；

2012-05-23

南京工程學(xué)院青年基金項目（QKJB2010009）